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 generalizations of "folds" of lists to arbitrary algebraic data types, which can be described as initial algebras. 
The dual concept is that of anamorphism that generalize "unfolds". A hylomorphism is the composition of an anamorphism followed by a catamorphism.
Definition.
Consider an initial formula_1-algebra formula_2 for some endofunctor formula_1 of some category into itself. Here formula_4 is a morphism from formula_5 to formula_6. Since it is initial, we know that whenever formula_7 is another formula_1-algebra, i.e. a morphism formula_9 from formula_10 to formula_11, there is a unique homomorphism formula_12 from formula_2 to formula_7. By the definition of the category of formula_1-algebra, this formula_12 corresponds to a morphism from formula_6 to formula_11, conventionally also denoted formula_12, such that formula_20. In the context of formula_1-algebra, the uniquely specified morphism from the initial object is denoted by formula_22 and hence characterized by the following relationship:
Terminology and history.
Another notation found in the literature is formula_25. 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.
Examples.
We give a series of examples, and then a more global approach to catamorphisms, in the Haskell programming language.
Iteration.
Iteration-step prescriptions lead to natural numbers as initial object.
Consider the functor codice_1 mapping a data type codice_2 to a data type codice_3, which contains a copy of each term from codice_2 as well as one additional term codice_5 (in Haskell, this is what codice_6 does). This can be encoded using one term and one function. So let an instance of a "StepAlgebra" also include a function from codice_3 to codice_2, which maps codice_5 to a fixed term codice_10 of codice_2, and where the actions on the copied terms will be called codice_12.
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 codice_13, for which codice_5 is mapped to codice_15 and otherwise codice_16 is prepended. As codice_17 denotes the number four in codice_18, 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 codice_19, which is passed to codice_20
List fold.
For a fixed type codice_21, consider the functor mapping types codice_2 to the product type of those two types. We moreover also add a term codice_23 to this resulting type. An f-algebra shall now map codice_23 to some special term codice_10 of codice_2 or "merge" a pair (any other term of the constructed type) into a term of codice_2. This merging of a pair can be encoded as a function of type codice_28.
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 codice_29, for which the number from codice_21 acts on the number from codice_2 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 codice_21, consider the functor mapping types codice_2 to a type that contains a copy of each term of codice_21 as well as all pairs of codice_2's (terms of the product type of two instances of the type codice_2). An algebra consists of a function to codice_2, which either acts on an codice_21 term or two codice_2 terms. This merging of a pair can be encoded as two functions of type codice_40 resp. codice_41.
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 codice_42 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 codice_42, the evaluation of the catamorphisms jumps back and forth between codice_21 and codice_45.
type Algebra f a = f a -> a -- the generic f-algebras
newtype Fix f = Iso { invIso :: f (Fix f) } -- 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 codice_46, which arises from Maybes's codice_5 and identify a successor function with repeated application of the codice_48. 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!": codice_49
And now again the tree example. For this we must provide the tree container data type so that we can set up the codice_50 (we didn't have to do it for the codice_6 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: codice_52