Catamorphisms and Anamorphisms over Recursive Functors

A list is not primitive. It is what remains when the operation “an element and a list” is iterated to its least fixed point, and the same description fits a binary tree, a rose tree, and an expression syntax. Once a recursive type is written as a fixed point, the fold over it stops being a family of ad hoc definitions and becomes one function, parameterized by the shape of the layer. The fold in one direction and the unfold in the other are the two halves of that observation, and their composition is where the interesting algorithms live.

Separating the layer from the recursion

The first step is to write the recursive occurrence as a type parameter, which turns a recursive type into a functor applied to itself:

data ListF a r = NilF | ConsF a r

newtype Fix f = Fix { unFix :: f (Fix f) }

type List a = Fix (ListF a)

ListF a r is one layer of the list: either an empty layer or an element paired with a continuation. It is a functor in r, and that is the only property the machinery needs:

instance Functor (ListF a) where
  fmap _ NilF        = NilF
  fmap f (ConsF a r) = ConsF a (f r)

The Fix wrapper ties the knot. Fix NilF is the empty list; Fix (ConsF 1 (Fix NilF)) is a singleton. Every recursive datatype in a functional language’s standard repertoire has such a one-layer description: a binary tree’s layer is LeafF | NodeF r r or LeafF a | NodeF r r depending on whether the payload sits in the leaves or the nodes, a rose tree’s layer is a payload plus a list of subtrees, and an expression syntax’s layer has one constructor per syntactic form with recursive positions as r.

The reason to do this rather than work with the recursive type directly is that the functor parameterizes exactly the recursion, and the recursion is the part that folds and unfolds are about. The payload types stay concrete.

The catamorphism as the unique algebra homomorphism

An algebra for a functor f is a carrier type b together with a function f b -> b. For ListF a, an algebra is a choice of b, a value for the nil case, and a function from a and b to b; that is exactly the pair a fold takes. A homomorphism from the initial algebra Fix f to an algebra (b, φ) is a function h satisfying h . Fix = φ . fmap h.

The catamorphism is that unique homomorphism:

cata :: Functor f => (f b -> b) -> Fix f -> b
cata φ = φ . fmap (cata φ) . unFix

One line. For lists, cata φ (Fix NilF) = φ NilF and cata φ (Fix (ConsF a r)) = φ (ConsF a (cata φ r)), which is the two-equation definition of foldr with the two cases merged into one function on the layer. The generality is not decoration: the same cata works for any functor, and the compiler needs only the Functor instance to typecheck it.

Uniqueness is the property that makes the abstraction useful, and it is a theorem about initial algebras: for any algebra, there is exactly one homomorphism from the initial one. The proof is induction on the structure, and the content is that the equations h . Fix = φ . fmap h determine h completely. This is the same universal property that the list fold has, stated once for all functors.

Anamorphisms build, and the seed is the state

The dual of an algebra is a coalgebra: a carrier s and a function s -> f s. A coalgebra describes how to produce one layer from a state. The anamorphism is a coalgebra homomorphism, and when the functor is polynomial and the structures are allowed to be infinite, it is the unique one into the final coalgebra. It has the type:

ana :: Functor f => (s -> f s) -> s -> Fix f
ana ψ = Fix . fmap (ana ψ) . ψ

For lists, a coalgebra is a function from a seed to either “stop” or “an element and a new seed”:

countdown :: Int -> ListF Int Int
countdown 0 = NilF
countdown n = ConsF n (n - 1)

-- the generated structure, converted back to an ordinary list
toList :: List Int -> [Int]
toList = cata step
  where
    step NilF        = []
    step (ConsF a r) = a : r

toList (ana countdown 3) produces [3, 2, 1]. The seed is the state of the generator, and the coalgebra is its step function. Every generator, every parser that produces a structure, and every unfolding of a recurrence is an anamorphism, whether or not it is written that way.

The asymmetry with cata is the important part. cata consumes a structure that already exists; ana produces one that does not. cata on an infinite structure diverges unless the algebra is lazy in the recursive position; ana can produce an infinite structure lazily, and the consumer decides how much of it to demand. The two are not interchangeable: a fold cannot create structure that was not there, and an unfold cannot summarize structure it has not built.

Hylomorphisms and the intermediate structure

Composing the two gives the hylomorphism:

hylo :: Functor f => (f b -> b) -> (s -> f s) -> s -> b
hylo φ ψ = φ . fmap (hylo φ ψ) . ψ

hylo φ ψ unfolds from a seed and folds the result in one pass, and in a lazy language the intermediate Fix f is never fully materialized: each layer is produced, consumed, and dropped. A quicksort written this way, a parser that consumes its own output, and a compiler pass that expands a core form into a simpler one and then folds it are all hylomorphisms. The definition above is the fused form; writing cata φ . ana ψ allocates the intermediate structure and is the version that fusion rules try to recover.

The fused form is not always available. If the algebra needs to inspect more than one layer at a time, or if the coalgebra’s output is shared, the composition has to materialize. The trade is the same one as in list fusion: one traversal and no allocation against the ability to look at the whole structure.

The stack problem, and why cata is not tail recursive

cata as written recurses on the functor’s recursive positions, and the recursion is not in tail position: the algebra is applied after the recursive calls return. For a list of length n, the evaluation consumes n stack frames. A hand-written strict fold can be tail recursive and run in constant stack; cata cannot, because the algebra’s shape is unknown until the layer is reached.

Two resolutions exist. The first is to use the monadic or accumulating variant, which threads a state through the traversal and can be strict in it. The second is to note that in a lazy language the stack usage is governed by the demand pattern rather than by the definition: cata producing a lazy result consumes stack in proportion to the depth that is actually demanded, and a consumer that forces the whole result forces the whole depth. A cata that builds a lazy list from a lazy list runs in constant stack per element demanded.

There is a deeper reason the naive definition cannot be made tail recursive in general: the catamorphism for a functor with two recursive positions, such as a binary tree, has a genuinely tree-shaped call graph, and no accumulator can flatten it without an explicit stack. The continuation-based encoding in continuation-passing style can, because the pending algebra application is passed as a continuation; the result is a defunctionalized stack and the same asymptotics, with the frames on the heap.

Least and greatest fixed points are not the same type

Fix f was introduced as a single type, and for polynomial functors it denotes the least fixed point: the values built by finitely many applications of the layer constructor, which is the domain on which structural induction is the valid proof principle. Codata is the greatest fixed point, the one that also admits infinite depth, and it is a different object even when both are written with the same Fix type constructor. Reasoning about it uses coinduction: two values are equal when no finite observation distinguishes them.

In a lazy language the distinction is invisible in the type and visible in the operations. cata on an infinite structure diverges unless the algebra is lazy in the recursive position, and ana can produce an infinite structure that a consumer takes a prefix of. The language does not distinguish data from codata; the same Fix serves both, and the guarantee that a fold terminates is lost. A strict language must distinguish them, because it has no way to represent the infinite value without a suspension.

The practical consequence is that the universal property of cata is a statement about the least fixed point: for every algebra there is exactly one homomorphism from Fix f, and its induction principle is structural induction on a finite value. Applied to a greatest fixed point the property no longer holds, and the fold that terminates on finite structures is only defined on the productive prefix of an infinite one.

What the abstraction does not buy

Encoding every datatype as Fix f has costs that are easy to overlook. The Fix wrapper adds a constructor and an indirection per layer, which a compiler may or may not erase; a pattern match on the encoded type is a match on Fix followed by a match on the layer, where the native type needs one match. Deriving instances requires the functor to be written out by hand or generated, and recursive functions that do not follow the layer structure, such as a fold that skips levels, cannot be expressed as a single cata at all.

The abstraction is therefore a specification device more than an implementation technique. It says which recursions are structural and gives them a name and a law; it does not make them faster. The practical use is in libraries where the same traversal must work over many syntaxes, and in proofs where the universal property replaces induction. Where a datatype is used for its performance characteristics rather than its shape, the native recursive definition with a hand-written fold is the better engineering choice, and the two can coexist in one program.