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 to deal with a form which “eats its argument and keeps it too”, 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

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 to deal with a form which “eats its argument and keeps it too”, 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== Talks: * [https://hackage.haskell.org/package/recursion-schemes-5.0.1/docs/Data-Functor-Foldable.html Recursion schemes Haskell package

Text derived from https://en.wikipedia.org/w/index.php?oldid=1249728862 under CC BY-SA 4.0; modifications have been made.