Lists, trees, ASTs, JSON, expression languages. foldr, tree-sum, expression evaluator, pretty-printer. They look like different problems. They're one pattern — and it has a name. Let's peel it open.
foldr lets you collapse a list into a single value. Define what to do with the empty list, define what to do with a head and a folded tail, done. But here's the thing nobody told you: that same shape — define your two cases — works for trees, ASTs, JSON, every recursive structure you've ever met.
Why? Because every recursive type is the fixed point of a functor, and every foldr-flavoured function is one instance of a single universal pattern. By the end of this chapter you'll see the trick once and then you'll see it everywhere.
foldr was hiding somethingWatch the shape of foldr. You give it two things:
Now ask the same question for a binary tree of integers. To fold it, what do you need?
For a JSON tree: a value for null, a string-handler, a number-handler, a way to combine an array of folded children, a way to combine a map of folded children. Always the same shape: give me one handler per constructor, I'll fold the whole thing.
That's not coincidence. It's a theorem. Every recursive type is built from a non-recursive shape — and once you name that shape, the universal fold writes itself.
A list of A's is either empty, or a head A and a tail that is again a list of A's. That last bit — "a list of A's" mentions itself — is the recursion. Make it explicit. Replace the recursive occurrence with a parameter X standing in for "whatever the recursive type ends up being":
ListF[A, X] = Unit + (A × X)
ListF is not recursive. It's a perfectly ordinary sum-of-products. Either nothing (the Unit branch — that'll be Nil), or a pair of an A and an X (that'll be Cons, with X standing in for the tail).
And ListF is a functor in its second argument — you can map a function X ⇒ Y over the recursive slot.
Now the real recursive list type is what you get when you take ListF and plug it into itself, over and over: an X that satisfies X = ListF[A, X]. The smallest type that does that — the least fixed point — is exactly List[A]:
List[A] = μ X. ListF[A, X]
"μ" is "least fixed point of". Read it as: keep substituting X := ListF[A, X] and that's your list. The same trick works for binary trees:
TreeF[A, X] = A + (A × X × X) ⇒ Tree[A] = μ X. TreeF[A, X]
And for JSON, expression ASTs, rose trees — every recursive ADT is μ F for some functor F. The recursion is no longer baked into the type definition. It's a separate piece you can talk about.
F describes "one layer", and the fixed point μF stacks those layers as tall as you like. Splitting them is the move that unlocks everything below.An F-algebra is just a function
alg : F[A] ⇒ A
for some functor F and some type A. The A is called the carrier. The algebra is a recipe that says: "give me one layer of F-structure filled with A's, and I'll give you back a single A." That's it. One step of consumption.
Now pin this to lists. For ListF[Int, A], an algebra is a function
Unit + (Int × A) ⇒ A
which, by the sum rule, is exactly a pair: a value of type A (for the empty branch) and a function (Int, A) ⇒ A (for the cons branch). Look at that:
ListF-algebra = (zero : A, step : (Int, A) ⇒ A)
That's a foldr in disguise. sum is the algebra (0, _ + _). product is (1, _ × _). length is (0, (_, n) ⇒ n + 1). Every "fold a list" you've ever written is an F-algebra for ListF.
And for trees: a TreeF-algebra is exactly a pair of functions, one per constructor — leaf-handler and branch-handler. Tree-sum, tree-depth, tree-pretty-print — all F-algebras.
Of all possible F-algebras, one is special. Pick the carrier to be the recursive type itself — the fixed point μF — and pick the algebra to be the constructors:
In : F[μF] ⇒ μF
What does In do? It takes one layer of F-structure filled with already-built sub-pieces of μF and wraps it up into a fresh piece of μF. For lists that's Nil and Cons. For trees, Leaf and Branch. It's the algebra that rebuilds the structure as you go.
This one is called the initial F-algebra. "Initial" in the category-theory sense: there's a unique morphism from it to every other F-algebra. That unique morphism is the catamorphism (next section).
And there's a beautiful side-effect, known as Lambek's theorem:
μF ≅ F(μF)
The fixed-point is literal. The initial algebra In is an isomorphism — you can wrap a layer or unwrap a layer. That's exactly the operation that "peels off one layer at a time" depends on.
Here's the punchline. Pick any F-algebra alg : F[A] ⇒ A. There is exactly one function
cata(alg) : μF ⇒ A
that uses alg to consume the whole recursive structure one layer at a time. That function is the catamorphism (Greek kata, "downward"). The recipe:
μF.In — you now have an F[μF]: one layer of structure whose holes are sub-μF's.fmap cata(alg) over the holes, turning each sub-μF into an A. You now have F[A].alg. You now have an A. Done.One picture, one definition, every fold you've ever written. For lists, cata is foldr. For trees, cata is the universal tree fold. For JSON, cata is your pretty-printer. For an expression AST, cata is your evaluator.
If cata tears a recursive structure down to a single value, what does it dually look like to build one up from a seed? That's the anamorphism: ana : A ⇒ μF, driven by a coalgebra A ⇒ F[A]. Generate one layer, then keep generating into the holes. Range-from-N, zip-with-index, Stream unfolds — all anamorphisms.
Run an ana and then a cata straight back-to-back (without ever materialising the intermediate structure) and you've got a hylomorphism: a divide-and-conquer pattern. Quicksort, mergesort, the towers of Hanoi — all hylos. We'll mostly stick to cata here; just know its siblings are sitting right next door.
Pick an algebra, then press step to peel one Cons off the head of the list and feed it through. The accumulator on the right is the running value — by the end it's cata(alg)(list).
Different functor, same pattern. A TreeF-algebra is a pair: one handler for leaves and one for branches. Step folds one leaf-or-branch at a time, bubbling values up from the bottom.
Of every F-algebra for ListF[Int, _], one is the initial one — its carrier is List[Int] itself, and its operation is Nil / Cons (it just rebuilds the list). The catamorphism is the unique arrow from that initial algebra to any other algebra you pick. Click the targets to draw the arrow.
The names are new. The patterns are old. Quick tour:
foldr on a list — the list catamorphism. Two-argument fold = two-constructor algebra.TreeF or ExprF. The Visitor pattern in OO is the same thing wearing a suit.cata, ana, hylo, para, zygo by name — once you spot the pattern, you'll start reaching for them instead of writing the recursion by hand.A fully generic cata. One Fix wrapper, one functor, one universal recursion. sum and length are just F-algebras you hand it.