Catamorphism

From Wikipedia, the free encyclopedia

In category theory, the concept of catamorphism (from Greek: κατά = downwards or according to; μορφή = form or shape) denotes the unique homomorphism for an initial algebra. The concept has been applied to functional programming.

The dual concept is that of anamorphism.

Contents 1 Catamorphisms in functional programming 1.1 Example 2 Catamorphisms in category theory 2.1 The general case 2.2 Properties 2.3 Notation 3 See also 4 References 5 External links 5.1 Detailed example

[edit] 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.

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.[3], which was in the context of the Squiggol formalism.

The dual concept is of anamorphisms, a generalisation of “unfolds”.

[edit] Example

The following example is in Haskell, assuming a class Group of types supporting an "addition" operation.

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, (+))

Here foldTree (f, g) is a catamorphism for the Tree a datatype; treeDepth and sumTree are called algebras.

[edit] 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 in his Ph.D. Thesis ^[1] and the article ^[2].

Specialized to the above example, the formal definition of a catamorphism is as follows: For fixed type a, the pair (r, [f1,f2]) is an F-algebra, where F is the functor sending r to a + r × r. The pair (Tree a, [Leaf,Branch]) is also an F-algebra, and specifically the initial F-algebra. This means that there is a unique homomorphism to any other F-algebra. That unique homomorphism is called a catamorphism.

In the code example above, foldTree is the function that constructs these catamorphisms.

[edit] The general case

If (A, in) is the initial F-algebra for some endofunctor F (so in is a morphism from FA to A), and (X, f) is an F-algebra, there is a unique homomorphism from (A, in) to (X, f), which may be denoted cata f (leaving the "carrier" X implicit). (Here "cata" is a generic name for what was called "foldTree" for the specific case from the example.)

[edit] Properties

Let F be given and fixed. Using the definition of homomorphism, the uniqueness property can be expressed as: for all F-algebras (X, f), and all h from A to X, the following two statements are equivalent:

• 
• 

[edit] Notation

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.

[edit] See also

• Anamorphism
• Apomorphism
• Hylomorphism
• Paramorphism

[edit] References

• Erik Meijer, Maarten Fokkinga, and Ross Paterson. Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire [4], contains additional definitions and examples

1. ^ Algebraic Types and Program Transformation (Univ. Groningen, 1990)[1]
2. ^ Data structures and program transformation[2]

[edit] External links

• Catamorphisms in Haskell

[edit] Detailed example

Brian McNamara, a developer on the F# team, has created a series of blog posts that describe catamorphisms and their synergy with tail recursion, continuations and monads. An important peculiarity of the series lies in explanation how the concept of catamorphism plays together with other functional tools. From the point of view of one who tries to grasp functional programming it's an invaluable piece of information:

• Catamorphisms, part one (Initial example)
• Catamorphisms, part two (Generalization for arbitrary data structures, example: processing binary trees, application of tail recursion)
• Catamorphisms, part three (Example: processing an AST)
• Catamorphisms, part four (Using catamorphisms to produce new ASTs)
• Catamorphisms, part five (Minimizing memory pressure for AST rewriting task, application of continuations)
• Catamorphisms, part six (Making code from previous article to be tail-recursive)
• Catamorphisms, part seven (Using monads to reduce boilerplate)