In category theory, the concept of catamorphism (from Greek: κατά = downwards or according to; μορφή = form or shape) denotes the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds.
Catamorphisms in functional programming
In functional programming, a catamorphism is a generalization of the folds on lists, known from functional programming, to arbitrary algebraic data types that can be described as initial algebras.[clarification needed]
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 dual concept is that of anamorphisms, a generalization of unfolds.
The following example is in Haskell:
data Tree a = Leaf a | Branch (Tree a) (Tree a) type TreeAlgebra a r = (a -> r, r -> r -> r) foldTree :: TreeAlgebra a r -> Tree a -> r foldTree (f, g) (Leaf x) = f x foldTree (f, g) (Branch l r) = g (foldTree (f, g) l) (foldTree (f, g) r) treeDepth :: TreeAlgebra a Integer treeDepth = (const 1, \l r -> 1 + max l r) sumTree :: (Num a) => TreeAlgebra a a sumTree = (id, (+))
foldTree (f, g) is a catamorphism for the
Tree a datatype;
sumTree are called algebras.
Catamorphisms in category theory
Category theory provides the necessary concepts to give a generic definition that accounts for all initial data types (using an identification of functions in functional programming with the morphisms of the category Set or some related concrete category). This was done by Grant Malcolm.
Returning to the above example, consider a functor F sending
a + r × r. An F-algebra for this specific case is a pair (
r is an object, and
f2 are two morphisms defined as
f1: a → r, and
f2: r × r → r.
In the category of F-algebras over such F, an initial algebra, if it exists, represents a
Tree, or, in Haskell terms, it is
(Tree a, [Leaf, Branch]).
Tree a being an initial object in the category of F-algebras, there is a unique homomorphism of F-algebras from
Tree a to any given F-algebra. This unique homomorphism is called catamorphism.
The general case
That means the following. Suppose (A, in) is an initial F-algebra for some endofunctor F of some category into itself. Thus, in is a morphism from FA to A, and since it is assumed to be initial we know that whenever (X, f) is another F-algebra (a morphism f from FX to X), there will be a unique homomorphism h from (A, in) to (X, f), that is a morphism h from A to X such that h . in = f . Fh. Then for each such f we denote by cata f that uniquely specified morphism h.
In other words, we have the following defining relationship, given some fixed F, A, and in as above:
Another notation for cata f 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 Meijer 1991.
- Meijer, Erik; Fokkinga, Maarten; Paterson, Ross (1991). "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire". Conference on Functional Programming Languages and Computer Architecture (FPCA). Springer. pp. 124–144. ISBN 3-540-54396-1. CiteSeerX: 10.1.1.41.125.
- Ki Yung Ahn; Sheard, Tim (2011). "A hierarchy of mendler style recursion combinators: taming inductive datatypes with negative occurrences". Proceedings of the 16th ACM SIGPLAN international conference on Functional programming. ICFP '11.