In
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
, the concept of catamorphism (from the
Ancient Greek
Ancient Greek includes the forms of the Greek language used in ancient Greece and the ancient world from around 1500 BC to 300 BC. It is often roughly divided into the following periods: Mycenaean Greek (), Dark Ages (), the Archaic pe ...
: "downwards" and "form, shape") denotes the unique
homomorphism
In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...
from an
initial algebra
In mathematics, an initial algebra is an initial object in the category of -algebras for a given endofunctor . This initiality provides a general framework for induction and recursion.
Examples
Functor
Consider the endofunctor sending ...
into some other algebra.
In
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions tha ...
, catamorphisms provide generalizations of ''
folds'' of
lists
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby union ...
to arbitrary
algebraic data type
In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite type, i.e., a type formed by combining other types.
Two common classes of algebraic types are product types (i.e., ...
s, which can be described as
initial algebra
In mathematics, an initial algebra is an initial object in the category of -algebras for a given endofunctor . This initiality provides a general framework for induction and recursion.
Examples
Functor
Consider the endofunctor sending ...
s.
The dual concept is that of
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 ...
that generalize ''unfolds''. A
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 re ...
is the composition of an anamorphism followed by a catamorphism.
Definition
Consider an
initial
In a written or published work, an initial capital, also referred to as a drop capital or simply an initial cap, initial, initcapital, initcap or init or a drop cap or drop, is a letter at the beginning of a word, a chapter, or a paragraph tha ...
-algebra for some
endofunctor of some
category
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
* Category of being
* ''Categories'' (Aristotle)
* Category (Kant)
* Categories (Peirce) ...
into itself. Here
is a
morphism
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
from
to
. Since it is initial, we know that whenever
is another
-algebra, i.e. a morphism
from
to
, there is a unique
homomorphism
In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...
from
to
. By the definition of the category of
-algebra, this
corresponds to a morphism from
to
, conventionally also denoted
, such that
. In the context of
-algebra, the uniquely specified morphism from the initial object is denoted by
and hence characterized by the following relationship:
*
*
Terminology and history
Another notation found in the literature is
. The open brackets used are known as banana brackets, after which catamorphisms are sometimes referred to as ''bananas'', as mentioned in
Erik Meijer ''et al''.
One of the first publications to introduce the notion of a catamorphism in the context of programming was the paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, by
Erik Meijer ''et al.'',
which was in the context of the
Squiggol formalism.
The general categorical definition was given by
Grant Malcolm
Grant or Grants may refer to:
Places
*Grant County (disambiguation)
Australia
* Grant, Queensland, a locality in the Barcaldine Region, Queensland, Australia
United Kingdom
*Castle Grant
United States
* Grant, Alabama
* Grant, Inyo County, ...
.
[.]
Examples
We give a series of examples, and then a more global approach to catamorphisms, in the
Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
programming language.
Iteration
Iteration-step prescriptions lead to natural numbers as initial object.
Consider the functor
fmaybe
mapping a data type
b
to a data type
fmaybe b
, which contains a copy of each term from
b
as well as one additional term
Nothing
(in Haskell, this is what
Maybe
does). This can be encoded using one term and one function. So let an instance of a ''StepAlgebra'' also include a function from
fmaybe b
to
b
, which maps
Nothing
to a fixed term
nil
of
b
, and where the actions on the copied terms will be called
next
.
type StepAlgebra b = (b, b->b) -- the algebras, which we encode as pairs (nil, next)
data Nat = Zero , Succ Nat -- which is the initial algebra for the functor described above
foldSteps :: StepAlgebra b -> (Nat -> b) -- the catamorphisms map from Nat to b
foldSteps (nil, next) Zero = nil
foldSteps (nil, next) (Succ nat) = next $ foldSteps (nil, next) nat
As a silly example, consider the algebra on strings encoded as
("go!", \s -> "wait.. " ++ s)
, for which
Nothing
is mapped to
"go!"
and otherwise
"wait.. "
is prepended. As
(Succ . Succ . Succ . Succ $ Zero)
denotes the number four in
Nat
, the following will evaluate to "wait.. wait.. wait.. wait.. go!":
foldSteps ("go!", \s -> "wait.. " ++ s) (Succ . Succ . Succ . Succ $ Zero). We can easily change the code to a more useful operation, say repeated operation of an algebraic operation on numbers, just by changing the F-algebra
(nil, next)
, which is passed to
foldSteps
List fold
For a fixed type
a
, consider the functor mapping types
b
to the product type of those two types. We moreover also add a term
Nil
to this resulting type. An f-algebra shall now map
Nil
to some special term
nil
of
b
or "merge" a pair (any other term of the constructed type) into a term of
b
. This merging of a pair can be encoded as a function of type
a -> b -> b
.
type ContainerAlgebra a b = (b, a -> b -> b) -- f-algebra encoded as (nil, merge)
data List a = Nil , Cons a (List a) -- which turns out to be the initial algebra
foldrList :: ContainerAlgebra a b -> (List a -> b) -- catamorphisms map from (List a) to b
foldrList (nil, merge) Nil = nil
foldrList (nil, merge) (Cons x xs) = merge x $ foldrList (nil, merge) xs
As an example, consider the algebra on numbers types encoded as
(3, \x-> \y-> x*y)
, for which the number from
a
acts on the number from
b
by plain multiplication. Then the following will evaluate to 3.000.000:
foldrList (3, \x-> \y-> x*y) (Cons 10 $ Cons 100 $ Cons 1000 Nil)
Tree fold
For a fixed type
a
, consider the functor mapping types
b
to a type that contains a copy of each term of
a
as well as all pairs of
b
's (terms of the product type of two instances of the type
b
). An algebra consists of a function to
b
, which either acts on an
a
term or two
b
terms. This merging of a pair can be encoded as two functions of type
a -> b
resp.
b -> b -> b
.
type TreeAlgebra a b = (a -> b, b -> b -> b) -- the "two cases" function is encoded as (f, g)
data Tree a = Leaf a , Branch (Tree a) (Tree a) -- which turns out to be the initial algebra
foldTree :: TreeAlgebra a b -> (Tree a -> b) -- catamorphisms map from (Tree a) to b
foldTree (f, g) (Leaf x) = f x
foldTree (f, g) (Branch left right) = g (foldTree (f, g) left) (foldTree (f, g) right)
treeDepth :: TreeAlgebra a Integer -- an f-algebra to numbers, which works for any input type
treeDepth = (const 1, \i j -> 1 + max i j)
treeSum :: (Num a) => TreeAlgebra a a -- an f-algebra, which works for any number type
treeSum = (id, (+))
General case
Deeper category theoretical studies of initial algebras reveal that the F-algebra obtained from applying the functor to its own initial algebra is isomorphic to it.
Strong type systems enable us to abstractly specify the initial algebra of a functor
f
as its fixed point ''a = f a''. The recursively defined catamorphisms can now be coded in single line, where the case analysis (like in the different examples above) is encapsulated by the fmap. Since the domain of the latter are objects in the image of
f
, the evaluation of the catamorphisms jumps back and forth between
a
and
f a
.
type Algebra f a = f a -> a -- the generic f-algebras
newtype Fix f = Iso -- gives us the initial algebra for the functor f
cata :: Functor f => Algebra f a -> (Fix f -> a) -- catamorphism from Fix f to a
cata alg = alg . fmap (cata alg) . invIso -- note that invIso and alg map in opposite directions
Now again the first example, but now via passing the Maybe functor to Fix. Repeated application of the Maybe functor generates a chain of types, which, however, can be united by the isomorphism from the fixed point theorem. We introduce the term
zero
, which arises from Maybe's
Nothing
and identify a successor function with repeated application of the
Just
. This way the natural numbers arise.
type Nat = Fix Maybe
zero :: Nat
zero = Iso Nothing -- every 'Maybe a' has a term Nothing, and Iso maps it into a
successor :: Nat -> Nat
successor = Iso . Just -- Just maps a to 'Maybe a' and Iso maps back to a new term
pleaseWait :: Algebra Maybe String -- again the silly f-algebra example from above
pleaseWait (Just string) = "wait.. " ++ string
pleaseWait Nothing = "go!"
Again, the following will evaluate to "wait.. wait.. wait.. wait.. go!":
cata pleaseWait (successor.successor.successor.successor $ zero)
And now again the tree example. For this we must provide the tree container data type so that we can set up the
fmap
(we didn't have to do it for the
Maybe
functor, as it's part of the standard prelude).
data Tcon a b = TconL a , TconR b b
instance Functor (Tcon a) where
fmap f (TconL x) = TconL x
fmap f (TconR y z) = TconR (f y) (f z)
type Tree a = Fix (Tcon a) -- the initial algebra
end :: a -> Tree a
end = Iso . TconL
meet :: Tree a -> Tree a -> Tree a
meet l r = Iso $ TconR l r
treeDepth :: Algebra (Tcon a) Integer -- again, the treeDepth f-algebra example
treeDepth (TconL x) = 1
treeDepth (TconR y z) = 1 + max y z
The following will evaluate to 4:
cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))
See also
*
Morphism
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
* Morphisms of
F-algebras
** 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 re ...
** Extension of the idea of catamorphisms:
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 kee ...
** 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 recurs ...
References
Further reading
*
{{refend
External links
Catamorphismsat HaskellWiki
Catamorphismsby Edward Kmett
* Catamorphisms in
F# (Par
1234567 by Brian McNamara
Catamorphisms in Haskell
Category theory
Recursion schemes
Functional programming
Morphisms
Iteration in programming