Recursion Schemes — Brief ☧
"In whom are hid all the treasures of wisdom and knowledge."
— Colossians 2:3 (KJV)
Deep version → | Back to Category Theory →
Q: Picture a set of Russian nesting dolls (matryoshka). You can do
two things with them: take them apart one layer at a time from the
outside in, or put them together one layer at a time from the inside
out. In programming, we constantly work with nested structures — lists
inside lists, trees inside trees. Are there named
patterns for these "take apart" and "put together" operations?
A: Yes, and they have elegant names:
- Catamorphism (fold): collapse a structure from the bottom up. Like summing every number in a list, or counting the total nodes in a tree. You start at the leaves and work your way to the root.
- Anamorphism (unfold): build a structure from the top down. Like generating the Fibonacci sequence: start with a seed and keep producing the next element.
# For God so loved the world that he gave his only begotten Son, # that whoever believes in him should not perish but have eternal life. # John 3:16 # Catamorphism: fold a list down to a single value def count_items_chirho(items_chirho): """Fold: collapse the list to a count.""" if not items_chirho: return 0 # base case — the smallest doll return 1 + count_items_chirho(items_chirho[1:])Q: I already know about recursion. Why give
these patterns special names?
A: Because recursion schemes **separate the shape of the recursion
from the work you actually want to do**. Normally, when you write a
recursive function, the recursion pattern (how you traverse) is tangled
up with the business logic (what you compute at each step). Recursion
schemes untangle them. You pick a scheme (fold, unfold, refold) and
then supply only the one-step logic. This makes code easier to reason
about, test, and optimize.
Q: You mentioned "refold" — what is that?
A: A hylomorphism: unfold a structure and then immediately fold
it back down, without ever materializing the whole intermediate structure.
Think of building a family tree from a genealogy
record and then immediately counting the generations — you do not need
to keep the entire tree in memory.
Key Recursion Schemes
| Scheme | Direction | Analogy |
|---|---|---|
| Catamorphism (cata) | Bottom-up fold | Sum a list, count tree nodes |
| Anamorphism (ana) | Top-down unfold | Generate a sequence from a seed |
| Hylomorphism (hylo) | Unfold then fold | Build a tree, then count it |
| Paramorphism (para) | Fold with context | Each step sees the full remaining structure |
| Apomorphism (apo) | Unfold with early stop | Generate a list but stop early on a condition |
This table gives you a vocabulary for patterns you have probably already used without naming them. Every time you wrote a function that reduces a list to a single value (sum, count, maximum), you used a catamorphism. Every time you generated a sequence from an initial value (Fibonacci, countdown, pagination), you used an anamorphism. The power of naming these patterns is that you can then write generic code that works for any data structure -- lists, trees, graphs -- by separating the traversal strategy from the per-step computation.
Connection to our project: Our hash-consed term store uses catamorphisms
to walk terms bottom-up during unification: starting at the leaf nodes, each sub-term is matched and unified, and the results are combined as we move toward the root. Anamorphisms generate search
trees from conde branches: starting from a goal, each conde unfolds into multiple sub-goals, each of which may unfold further. The traversal algorithm is
the scheme; the domain-specific logic (unification rules, constraint checks) plugs in at each step. Edward Kmett's
recursion-schemes library provides the generic machinery, and our Rust implementation follows the same design: the recursion structure is factored out into reusable combinators, and the constraint-solving logic is supplied as a parameter. This separation makes it possible to swap between CPU-based lazy evaluation and FPGA-based eager tensor evaluation without changing the high-level algorithm.
Soli Deo Gloria