**Description**

Catamorphisms are generalizations of the concept of a fold in functional programming. A

*catamorphism*deconstructs a data structure with an F-algebra for its underlying functor.

**History**

The name catamorphism appears to have been chosen by Lambert Meertens [1]. The category theoretic machinery behind these was resolved by Grant Malcolm [2][3], and they were popularized by Meijer, Fokkinga and Paterson[4][5]. The name comes from the Greek 'κατα-' meaning "downward or according to". A useful mnemonic is to think of a catastrophe destroying something.

**Notation**

A catamorphism for some F-algebra (X,f) is denoted (| f |)

_{F}. When the functor F can be determined unambiguously, it is usually written (|φ|) or

**cata**φ. Due to this choice of notation, a catamorphism is sometimes called a banana and the (|.|) notation is sometimes referred to as banana brackets.

**Haskell Implementation**

type Algebra f a = f a -> anewtype Mu f = InF { outF :: f (Mu f) }cata :: Functor f => Algebra f a -> Mu f -> acata f = f . fmap (cata f) . outF

**Alternate Definitions**

cata f = hylo f outFcata f = para (f . fmap fst)

**Duality**

A catamorphism is the categorical dual of an anamorphism.

**Derivation**

If (μF,in

_{F}) is the initial F-algebra for some endofunctor F and (X,φ) is an F-algebra, then there is a unique F-algebra homomorphism from (μF,in

_{F}) to (X,φ), which we denote (| φ |)

_{F}.

That is to say, the following diagram commutes:

**Laws**

Rule | Haskell |
---|---|

cata-cancel | cata phi . InF = phi . fmap (cata phi) |

cata-refl | cata InF = id |

cata-fusion | f . phi = phi . fmap f => f . cata phi = cata phi |

cata-compose | eps :: f :~> g => cata phi . cata (In . eps) = cata (phi . eps) |

Examples

Examples

The underlying functor for a string of Chars and its fixed point

data StrF x = Cons Char x | Niltype Str = Mu StrF

instance Functor StrF wherefmap f (Cons a as) = Cons a (f as)fmap f Nil = Nil

length :: Str -> Intlength = cata phi wherephi (Cons a b) = 1 + bphi Nil = 0

data NatF a = S a | Z deriving (Eq,Show)type Nat = Mu NatFinstance Functor NatF wherefmap f Z = Zfmap f (S z) = S (f z)

plus :: Nat -> Nat -> Natplus n = cata phi wherephi Z = nphi (S m) = s m

times :: Nat -> Nat -> Nattimes n = cata phi wherephi Z = zphi (S m) = plus n mz :: Natz = InF Zs :: Nat -> Nats = InF . S

**Mendler Style**

A somewhat less common variation on the theme of a catamorphism is a catamorphism as a recursion scheme a la Mendler, which removes the dependency on the underlying type being an instance of Haskell's Functor typeclass [6].

`type MendlerAlgebra f c = forall a. (a -> c) -> f a -> c [8]`

From which we can derive the original notion of a catamorphism:mcata :: MendlerAlgebra f c -> Mu f -> cmcata phi = phi (mcata phi) . outF

This can be seen to be equivalent to the original definition of cata by expanding the definition of mcata.cata :: Functor f => Algebra f c -> Mu f -> ccata phi = mcata (\f -> phi . fmap f)

The principal advantage of using Mendler-style is it is independent of the definition of the Functor definition for f.

**Mendler and the Contravariant Yoneda Lemma**

The definition of a Mendler-style algebra above can be seen as the application of the contravariant version of the Yoneda lemma to the functor in question.

In type theoretic terms, the contravariant Yoneda lemma states that there is an isomorphism between (f a) and ∃b. (b -> a, f b), which can be witnessed by the following definitions.

Note that in Haskell using an existential requires the use ofdata CoYoneda f a = forall b. CoYoneda (b -> a) (f b)toCoYoneda :: f a -> CoYoneda f atoCoYoneda = CoYoneda idfromCoYoneda :: Functor f => CoYoneda f a -> f afromCoYoneda (CoYoneda f v) = fmap f v

**data**, so there is an extra bottom that can inhabit this type that prevents this from being a true isomorphism.

However, when used in the context of a (CoYoneda f)-Algebra, we can rewrite this to use universal quantification because the functor f only occurs in negative position, eliminating the spurious bottom.

Algebra (CoYoneda f) a

= (by definition) CoYoneda f a -> a

~ (by definition) (exists b. (b -> a, f b)) -> a

~ (lifting the existential) forall b. (b -> a, f b) -> a

~ (by currying) forall b. (b -> a) -> f b -> a

= (by definition) MendlerAlgebra f a

**Generalized Catamorphisms**

Most more advanced recursion schemes for folding structures, such as paramorphisms and zygomorphisms can be seen in a common framework as "generalized" catamorphisms[7]. A generalized catamorphism is defined in terms of an F-W-algebra and a distributive law for the comonad W over the functor F which preserves the structure of the comonad W.

type Dist f w = forall a. f (w a) -> w (f a)type FWAlgebra f w a = f (w a) -> a

However, a generalized catamorphism can be shown to add no more expressive power to the concept of a catamorphism. That said the separation of a number of the "book keeping" concerns by isolating them in a reusable distributive law can ease the development of F-W-algebras.g_cata :: (Functor f, Comonad w) =>

Dist f w -> FWAlgebra f w a -> Mu f -> ag_cata k g = extract . c where

c = liftW g . k . fmap (duplicate . c) . outF

We can transform an F-W-algebra into an F-algebra by including the comonad in the carrier for the algebra and then extracting after we perform this somewhat more stylized catamorphism:

lowerAlgebra :: (Functor f, Comonad w) =>

Dist f w -> FWAlgebra f w a -> Algebra f (w a)lowerAlgebra k phi = liftW phi . k . fmap duplicate

g_cata :: (Functor f, Comonad w) =>

Dist f w -> FWAlgebra f w a -> Mu f -> ag_cata k phi = extract . cata (lowerAlgebra k phi)

and we can trivially transform an Algebra into an F-W-Algebra by mapping the counit of the comonad over F. Then using the trivial identity functor, we can represent every catamorphism as a generalized-catamorphism.

Between these two definitions we can see that a generalized catamorphism does not increase the scope of a catamorphism to encompass any more operations, it simply further stylizes the pattern of recursion.liftAlgebra :: (Functor f, Comonad w) =>`Algebra f a -> FWAlgebra f w a`

liftAlgebra phi = phi . fmap extract

cata :: Functor f => Algebra f a -> Mu f -> a

cata f = g_cata (Identity . fmap runIdentity) (liftAlgebra f)

## Erratum

Great article.

Max Bolingbroke - Mar 2, 2011One very small correction: I think the single occurence of lowerGAlgebra in the code should be lowerAlgebra instead.

Great article

Anonymous - Mar 2, 2011