Catamorphism

In functional programming, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra.
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 -algebra for some endofunctor of some category into itself. Here is a morphism from to. Since it is initial, we know that whenever is another -algebra, i.e. a morphism from to, there is a unique homomorphism 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.

Examples

We give a series of examples, and then a more global approach to catamorphisms, in the Haskell programming language.

Catamorphism for Maybe-algebra

Consider the functor Maybe defined in the below Haskell code:

data Maybe a = Nothing | Just a -- Maybe type
class Functor f where -- class for functors
fmap :: -> -- action of functor on morphisms
instance Functor Maybe where -- turn Maybe into a functor
fmap g Nothing = Nothing
fmap g = Just

The initial object of the Maybe-Algebra is the set of all objects of natural number type Nat together with the morphism ini defined below:

data Nat = Zero | Succ Nat -- natural number type
ini :: Maybe Nat -> Nat -- initial object of Maybe-algebra
ini Nothing = Zero
ini = Succ n

The cata map can be defined as follows:

cata :: ->
cata g Zero = g -- Notice: fmap Nothing = g Nothing and Zero = ini
cata g = g ) -- Notice: fmap = Just and Succ n = ini

As an example consider the following morphism:

g :: Maybe String -> String
g Nothing = "go!"
g = "wait..." ++ str

Then cata g will evaluate to "wait... wait... wait... go!".

List fold

For a fixed type a consider the functor MaybeProd a defined by the following:

data MaybeProd a b = Nothing | Just -- is the product type of a and b
class Functor f where -- class for functors
fmap :: -> -- action of functor on morphisms
instance Functor where -- turn MaybeProd a into a functor, the functoriality is only in the second type variable
fmap g Nothing = Nothing
fmap g = Just

The initial algebra of MaybeProd a is given by the lists of elements with type a together with the morphism ini defined below:

data List a = EmptyList | Cons a
ini :: MaybeProd a -> List a -- initial algebra of MaybeProd a
ini Nothing = EmptyList
ini = Cons n l

The cata map can be defined by:

cata :: ->
cata g EmptyList = g -- Note: ini Nothing = EmptyList
cata g = g -- Note: Cons s l = ini

Notice also that cata g = g .
As an example consider the following morphism:

g :: MaybeProd Int Int -> Int
g Nothing = 3
g = x*y

cata g evaluates to 30. This can be seen by expanding
cata g = g = 10* = 10* = 10*3.
In the same way it can be shown, that
cata g will evaluate to 10* = 3.000.000.
The cata map is closely related to the right fold of lists foldrList.
The morphism lift defined by

lift :: -> b ->
lift g b0 Nothing = b0
lift g b0 = g x y

relates cata to the right fold foldrList of lists via:

foldrList :: -> b-> List a -> b
foldrList fun b0 = cata

The definition of cata implies, that foldrList is the right fold and not the left fold.
As an example: foldrList 1 will evaluate to 1111 and foldrList 3 (Cons 10 to 3.000.000.

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. 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 = -- the "two cases" function is encoded as
data Tree a = Leaf a | Branch -- which turns out to be the initial algebra
foldTree :: TreeAlgebra a b -> -- catamorphisms map from to b
foldTree = f x
foldTree = g

treeDepth :: TreeAlgebra a Integer -- an f-algebra to numbers, which works for any input type
treeDepth =
treeSum :: => TreeAlgebra a a -- an f-algebra, which works for any number type
treeSum =

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 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 -> -- catamorphism from Fix f to a
cata alg = alg. fmap . 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 = "wait.. " ++ string
pleaseWait Nothing = "go!"

Again, the following will evaluate to "wait.. wait.. wait.. wait.. go!": cata pleaseWait
And now again the tree example. For this we must provide the tree container data type so that we can set up the fmap.

data Tcon a b = TconL a | TconR b b
instance Functor where
fmap f = TconL x
fmap f = TconR

type Tree a = Fix -- 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 Integer -- again, the treeDepth f-algebra example
treeDepth = 1
treeDepth = 1 + max y z

The following will evaluate to 4: cata treeDepth $ meet ) )