Paramorphism
In formal methods of computer science, a paramorphism (from Greek παρά, meaning "close together") is an extension of the concept of catamorphism first introduced by Lambert Meertens[1] to deal with a form which “eats its argument and keeps it too”,[2][3] as exemplified by the factorial function. Its categorical dual is the 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:
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
See also
- Morphism
- Morphisms of F-algebras
- From an initial algebra to an algebra: Catamorphism
- From a coalgebra to a final coalgebra: Anamorphism
- An anamorphism followed by an catamorphism: Hylomorphism
- Extension of the idea of anamorphisms: Apomorphism
References
- ^ "Paramorphisms" (PDF). 1990. p. 44. CiteSeerX 10.1.1.19.4825.
- ^ 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.
- ^ Meijer, Erik; Fokkinga, Maarten; Paterson, Ross (1991). "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire". CiteSeerX 10.1.1.41.125.
{{cite web}}: Missing or empty|url=(help)
External links
Explanation on StackOverflow: [1], [2], [3]
Blogs: [4]
Talks: [5]
 | This formal methods-related article is a stub. You can help Wikipedia by expanding it. |