Description
Catamorphisms are generalizations of Haskell's foldr. A catamorphism deconstructs a data structure with an F-algebra.

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 $(\!| \varphi |\!)$ or cata $\varphi$.

Implementation

 
cata :: Functor f => Algebra f a -> FixF f -> a
cata f = f . fmap (cata f) . outF
 

Alternate implementations

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

Duality

A catamorphism is the categorical dual of an anamorphism.

Derivation
If $(\mu F,\mathrm{in}_F)$ is the initial $F$-algebra for some endofunctor $F$ and $(X,\varphi)$ is an $F$-algebra, then there is a unique $F$-algebra homomorphism from $(\mu F,\mathrm{in}_F)$ to $(X,\varphi)$ which we denote $(\!| \varphi |\!)_F$.

That is to say, the following diagram commutes:

\bfig \square/>`>`>`>/[F \mu F`\mu F`F X`X;\mathrm{in}_F`F {(}\!{|}\varphi{|}\!{)}`{(}\!{|}\varphi{|}\!{)}`\varphi] \efig

Laws

Rule Categorically Haskell
cata-cancel ${(}\!{|}\varphi{|}\!{)}_F \circ \mathrm{in}_F = \varphi \circ F {(}\!{|}\varphi{|}\!{)}_F$ cata phi . InF = phi . fmap (cata phi)
cata-refl ${(}\!{|}\mathrm{in}_F{|}\!{)}_F = \mathrm{id}_{\mu F}$ cata InF = id
cata-fusion $\inference{f \circ \varphi = \varphi \circ F f}{f \circ {(}\!{|}\varphi{|}\!{)}_F = {(}\!{|}\varphi{|}\!{)}_F}$ f . phi = phi . fmap f =>
f . cata phi = cata phi
cata-compose $\inference{\varepsilon : F \stackrel{\centerdot}{->} G}{(\!| \varphi |\!)_G \circ (\!|\mathrm{in}_G \circ \varepsilon|\!)_F = (\!|\varphi \circ \varepsilon|\!)_F}$ eps :: f :~> g =>
cata phi . cata (In . eps) =
cata (phi . eps)


Examples

 
data StrF x = Cons Char x | Nil
type Str = FixF StrF
 
instance Functor StrF where
    fmap f (Cons a as) = Cons a (f as)
    fmap f Nil = Nil
 
length :: Str -> Int
length = cata phi where
    phi (Cons a b) = 1 + b
    phi Nil = 0
 
data NatF a = S a | Z deriving (Eq,Show)
type Nat = FixF NatF
 
instance Functor NatF where
     fmap f Z = Z
     fmap f (S z) = S (f z)
 
plus :: Nat -> Nat -> Nat
plus n = cata phi where
     phi Z = n
     phi (S m) = s m
 
times :: Nat -> Nat -> Nat
times n = cata phi where
     phi Z = z
     phi (S m) = plus n m
 
z :: Nat
z = InF Z
 
s :: Nat -> Nat
s = InF . S
 

Links
[Haddock] [Source] [Field Guide]

References

[1] L. Meertens. First Steps towards the theory of Rose Trees. Draft Report, CWI, Amsterdam, 1987.
[2] G. Malcolm. PhD Thesis. University of Gronigen, 1990.
[3] G. Malcolm. Data structures and program transformation. Science of Computer Programming, 14:255--279, 1990.
[4] E. Meijer. Calculating Compilers, Ph.D thesis, Utrecht State University 1992.
[5] E. Meijer, M. Fokkinga, R. Paterson, Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Proceedings, 5th ACM Conference on Functional Programming Languages and Computer Architecture.