In
formal methods
In computer science, formal methods are mathematics, mathematically rigorous techniques for the formal specification, specification, development, Program analysis, analysis, and formal verification, verification of software and computer hardware, ...
of
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a paramorphism
(from
Greek
Greek may refer to:
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 of all kno ...
''
παρά'', meaning "close together")
is an extension of the concept of
catamorphism
In functional programming, the concept of catamorphism (from the Ancient Greek: "downwards" and "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra.
Catamorphisms provide generalizations of '' folds'' o ...
first introduced by
Lambert Meertens to deal with a form which “eats its argument and keeps it too”,
as exemplified by the
factorial
In mathematics, the factorial of a non-negative denoted is the Product (mathematics), product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times ...
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 so ...
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 -> -> 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
In mathematics, a morphism is a concept of category theory that generalizes structure-preserving maps such as homomorphism between algebraic structures, functions from a set to another set, and continuous functions between topological spaces. Al ...
* 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 algebrai ...
s
** From an initial algebra to an algebra:
Catamorphism
In functional programming, the concept of catamorphism (from the Ancient Greek: "downwards" and "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra.
Catamorphisms provide generalizations of '' folds'' o ...
** From a coalgebra to a final coalgebra:
Anamorphism
** An anamorphism followed by an catamorphism:
Hylomorphism
Hylomorphism is a philosophical doctrine developed by the Ancient Greek philosopher Aristotle, which conceives every physical entity or being ('' ousia'') as a compound of matter (potency) and immaterial form (act), with the generic form as imm ...
** Extension of the idea of anamorphisms:
Apomorphism
References
External links
* Explanation on StackOverflow
* Blogs
* Talks
Recursion schemes Haskell package
Recursion schemes
{{formalmethods-stub