In
formal methods
In computer science, formal methods are mathematically rigorous techniques for the specification, development, and verification of software and hardware systems. The use of formal methods for software and hardware design is motivated by the exp ...
of
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, a paramorphism
(from
Greek
Greek may refer to:
Greece
Anything of, from, or related to Greece, a country in Southern Europe:
*Greeks, an ethnic group.
*Greek language, a branch of the Indo-European language family.
**Proto-Greek language, the assumed last common ancestor ...
''
παρά'', meaning "close together")
is an extension of the concept of
catamorphism
In category theory, the concept of catamorphism (from the Ancient Greek: "downwards" and "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra.
In functional programming, catamorphisms provide generalizat ...
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
In category theory, a branch of mathematics, duality is a correspondence between the properties of a category ''C'' and the dual properties of the opposite category ''C''op. Given a statement regarding the category ''C'', by interchanging the sou ...
is the
apomorphism In formal methods of computer science, an apomorphism (from '' ἀπό'' — Greek for "apart") is the categorical dual of a paramorphism and an extension of the concept of anamorphism (coinduction). Whereas a paramorphism models primitive recursi ...
.
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 -> -> b
para :: (a -> ( b) -> b) -> b -> -> b
ana :: (b -> (a, b)) -> b -> apo :: (b -> (a, Either b)) -> b ->
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-algebra
In mathematics, specifically in category theory, ''F''-algebras generalize the notion of algebraic structure. Rewriting the algebraic laws in terms of morphisms eliminates all references to quantified elements from the axioms, and these algeb ...
s
** From an initial algebra to an algebra:
Catamorphism
In category theory, the concept of catamorphism (from the Ancient Greek: "downwards" and "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra.
In functional programming, catamorphisms provide generalizat ...
** From a coalgebra to a final coalgebra:
Anamorphism
In computer programming, an anamorphism is a function that generates a sequence by repeated application of the function to its previous result. You begin with some value A and apply a function f to it to get B. Then you apply f to B to get C, and ...
** An anamorphism followed by an catamorphism:
Hylomorphism
Hylomorphism (also hylemorphism) is a philosophical theory developed by Aristotle, which conceives every physical entity or being (''ousia'') as a compound of matter (potency) and immaterial form (act), with the generic form as immanently real ...
** Extension of the idea of anamorphisms:
Apomorphism In formal methods of computer science, an apomorphism (from '' ἀπό'' — Greek for "apart") is the categorical dual of a paramorphism and an extension of the concept of anamorphism (coinduction). Whereas a paramorphism models primitive recursi ...
References
External links
Explanation on StackOverflow
Blogs
Talks
Recursion schemes Haskell package
Recursion schemes
{{formalmethods-stub