# Paramorphism

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Paramorphism
> Markdown URL: https://mediated.wiki/source/Paramorphism.md
> Source: https://en.wikipedia.org/wiki/Paramorphism
> Source revision: 1249728862
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [formal methods](/source/formal_methods) of [computer science](/source/computer_science), a '''paramorphism''' 
(from [Greek](/source/Greek_(language)) ''παρά'', meaning "close together") 
is an extension of the concept of [catamorphism](/source/catamorphism) first introduced by [Lambert Meertens](/source/Lambert_Meertens)<ref>{{cite web |year=1990 |title=Paramorphisms |url=https://www.researchgate.net/profile/Lambert-Meertens/publication/256269748_Paramorphisms/links/02e7e52155278d6842000000/Paramorphisms.pdf?origin=publication_detail |pages=44 |language=en |format=PDF |citeseerx=10.1.1.19.4825}}</ref> to deal with a form which “eats its argument and keeps it too”,<ref>[Philip Wadler](/source/Philip_Wadler).''Views: A way for pattern matching to cohabit with data abstraction.'' Technical Report 34, Programming Methodology Group, University of Gothenburg and Chalmers University of Technology, March 1987.</ref><ref>{{cite web|citeseerx = 10.1.1.41.125|title=Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire|first=Erik|last=Meijer|authorlink=Erik Meijer (computer scientist)|author2=Fokkinga, Maarten |author3=Paterson, Ross |year=1991}}</ref> 
as exemplified by the [factorial](/source/factorial) function. Its [categorical dual](/source/categorical_dual) is the [apomorphism](/source/apomorphism).

It is a more convenient version of catamorphism in that it gives the combining step function immediate access not only to the result value recursively computed from each recursive subobject, but the original subobject itself as well.

Example Haskell implementation, for lists:

<syntaxhighlight lang="haskell">
cata :: (a ->       b  -> b) -> b -> [a] ->  b
para :: (a -> ([a], b) -> b) -> b -> [a] ->  b
ana  :: (b -> (a,            b))  ->  b  -> [a]
apo  :: (b -> (a, Either [a] b))  ->  b  -> [a]

cata f b (a:as) = f a     (cata f b as)
cata _ b []     = b

para f b (a:as) = f a (as, para f b as)
para _ b []     = b

ana  u b = case u b of (a,       b') -> a : ana u b'

apo  u b = case u b of (a, Right b') -> a : apo u b'
                       (a, Left  as) -> a : as

</syntaxhighlight>

==See also==
* [Morphism](/source/Morphism)
* Morphisms of [F-algebra](/source/F-algebra)s
** From an initial algebra to an algebra: [Catamorphism](/source/Catamorphism)
** From a coalgebra to a final coalgebra: [Anamorphism](/source/Anamorphism)
** An anamorphism followed by an catamorphism: [Hylomorphism](/source/Hylomorphism_(computer_science))
** Extension of the idea of anamorphisms: [Apomorphism](/source/Apomorphism)

==References==
{{reflist}}

== External links ==
* Explanation on StackOverflow: [https://stackoverflow.com/questions/13317242/what-are-paramorphisms], [https://stackoverflow.com/questions/12767757/how-to-express-a-filter-that-relies-on-adjacent-elements-in-a-list-functionally/12768389#12768389], [https://stackoverflow.com/questions/6941904/recursion-schemes-for-dummies]
* Blogs: [http://fho.f12n.de/posts/2014-05-07-dont-fear-the-cat.html]
* Talks: [https://www.youtube.com/watch?v=PK4SOaAGVfg]
* [https://hackage.haskell.org/package/recursion-schemes-5.0.1/docs/Data-Functor-Foldable.html Recursion schemes Haskell package]

Category:Recursion schemes

{{formalmethods-stub}}

---
Adapted from the Wikipedia article [Paramorphism](https://en.wikipedia.org/wiki/Paramorphism) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Paramorphism?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.