Recursion Schemes: Catamorphisms, Anamorphisms, and Hylomorphisms

The fixed-point encoding supplied the two operators and their universal properties. This article is about the space between them: the schemes that pass more information to the algebra, the ones that pass a history, and the ones that let an unfold stop early. Each has a universal property, each corresponds to a specific class of recursion, and choosing among them is a matter of matching the information the recursive step needs, not of style.

The two directions, and the asymmetry that matters

cata consumes and ana produces. Their types are duals:

cata :: (f b -> b) -> Fix f -> b
ana  :: (s -> f s) -> s -> Fix f

The duality is exact in the types and inexact in the semantics, and the asymmetry comes from which fixed point Fix f denotes. As the greatest fixed point it contains the infinite structures, so a coalgebra that never returns a stopping layer has a value, and cata over that value diverges unless the algebra is lazy in the recursive position. As the least fixed point it contains only finite depth, so the same coalgebra has no value of that type to produce. In a lazy language the greatest reading is the useful one, and it is how repeat and iterate are defined. In a strict language the same coalgebra loops, and the programmer needs an external bound.

The second asymmetry is in the seed. A fold has no seed; the structure is the input. An unfold has only a seed, and the seed type is the generator’s state. Two unfolds with the same output type and different seed types are different functions, and the seed is where the state of a generator, the remaining input of a parser, or the current value of a recurrence lives.

Paramorphisms: the subtree alongside its folded result

cata hands the algebra the results for the children and nothing else. A para hands it the children themselves alongside their results:

para :: Functor f => (f (Fix f, b) -> b) -> Fix f -> b

The motivating example is the function that computes both a value and a check on that value. A maximum over a tree needs the child’s maximum to combine; a check that the tree is a valid search tree needs the child’s root value as well. cata can compute the first, and a para is required for the second unless the algebra is restructured to carry the extra information in the result type, which is what a zygomorphism does.

The cost of para is retention. Because the algebra receives the subtree, every subtree stays alive until its parent’s algebra application completes, so the peak residency is the whole structure rather than the path from the root. A cata that computes a summary can release each subtree as soon as its result is computed; a para cannot. The difference is invisible in the types and visible in a heap profile.

The general rule that connects the two: a cata whose carrier is a pair of the summary and the subtree is a para written by hand. The scheme exists to avoid that hand-coding, not to enable anything new.

Zygomorphisms: a fold with a helper

A zygomorphism runs two folds at once, one of which may use the other’s result. The classic application is a function that computes a summary and a property of that summary:

zygo :: Functor f => (f b -> b) -> (f (b, c) -> c) -> Fix f -> c

The first algebra is the helper; the second receives, for each child, both the helper’s result and the main result. A use case is a fold that computes a size and simultaneously checks that every subtree’s size is within a bound, where the check needs the child sizes. The helper is a genuine separate traversal in the naive formulation, and zygo fuses it.

zygo is expressible as a cata with a pair carrier, and the scheme’s value is again notational plus the guarantee that both folds share the traversal. The pair carrier version is what a compiler would produce after inlining; the named scheme is what makes the sharing explicit to a reader.

Histomorphisms: the whole history

A histomorphism hands the algebra a summary of all previous results along the path, not just the immediate children’s. The canonical use is dynamic programming on a recursive structure, where the answer for a node depends on answers for a set of ancestors or siblings. The motivating example from the literature is the maximum segment sum and the Fibonacci-like recurrences that need the two previous values: a cata can carry the pair in its carrier, and a histomorphism carries it in the scheme.

The implementation is the interesting part. A histomorphism is a catamorphism whose carrier is a coalgebra of the cofree comonad on the functor, which is a tree of all the results computed so far. In practice this is a lazily-built structure that the algebra indexes into. The practical cost is that the history is retained, so a histomorphism over a deep structure holds every result along the path, where a cata holds only the children’s results.

The Uustalu–Vene result that gives the family its unity is that each recursion scheme is a catamorphism into a particular comonad: cata into the identity comonad, para into the product comonad whose environment is the subtree, zygo into the product comonad whose environment is the helper’s result, histo into the cofree comonad. Once that is established, the schemes stop being a list of tricks and become one construction applied to different comonads. The practical benefit is that a new scheme is designed by choosing a comonad, and the laws come for free.

Apomorphisms: an unfold that can stop early

The dual of para is the apomorphism, an unfold whose coalgebra may return either a layer to continue from or an already-built structure to splice in:

apo :: Functor f => (s -> f (Either (Fix f) s)) -> s -> Fix f
apo ψ = Fix . fmap (either id (apo ψ)) . ψ

The coalgebra returns Left a finished subtree or Right a new seed. The use case is an unfold whose tail is already available. A function that generates the first k elements of a sequence and then appends a pre-existing list is an apomorphism; a cata-based version would have to build the prefix and then traverse it again to append. The scheme lets the prefix be built and the suffix be shared, which matters when the suffix is large.

The same retention caveat applies in reverse: an apomorphism that splices in a large existing structure shares it rather than copying it, so the result may hold the original alive. That is usually the point, and it is a surprise when the original was expected to be garbage.

Hylomorphisms: the composition, and when it fuses

hylo φ ψ = cata φ . ana ψ is the composition, and the fused definition avoids the intermediate structure entirely:

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

The fused form is not merely an optimization. In a lazy language, the composed form builds layers that are immediately consumed, and the garbage collector reclaims them; the fused form never builds them. The difference is the difference between a chain of stages and a loop, and it is the same difference that fold fusion exploits for lists.

The fused form also changes the failure modes. A coalgebra that produces an infinite structure is fine when consumed lazily by a fold that stops early, and the composed version behaves the same way. A coalgebra that produces a structure larger than memory is fine in the composed version only if the fold consumes each layer before the next is produced, which is exactly what the fused version guarantees. The programmer who writes cata φ . ana ψ and expects the same behaviour is relying on the compiler to fuse, and the compiler does not always.

Choosing a scheme

The choice is determined by the information the recursive step needs, and there is a decision order that is worth stating explicitly.

If the step needs only the children’s results, cata is enough and is the cheapest in retention. If it needs the children themselves, para is the direct expression and the retention is the price. If it needs a second summary computed in the same traversal, zygo expresses it without a second pass. If it needs results from further up the path, histo is the scheme, and the retained history is unavoidable. If it produces rather than consumes, ana is the base case; if it produces and may splice an existing tail, apo is the direct form. If it does both, hylo is the composition, and the fused definition is the version to write.

The schemes compose, and the compositions are where the useful programs are. A compiler pass that parses a term into one functor, transforms it, and emits another is a hylomorphism between two functors; a traversal that renames bound variables while checking scoping is a para whose algebra carries a scope. The algebra of these compositions is where the “origami” style gets its name, and Gibbons’s survey is the readable account of how the folds combine.

Where the abstraction stops paying

Every scheme in the family is a structurally recursive traversal of a single functor. A recursion that is not structural, such as an interpreter that recurses on a term and an environment simultaneously, or a unification that recurses on two terms, has no scheme. A recursion whose structure changes between cases, such as an evaluator that sometimes returns a term and sometimes a value, needs a sum of functors and a case analysis that the schemes do not provide.

The second limit is performance. cata as defined cannot be tail recursive in general, because the algebra is applied after the recursive calls return, and the schemes that carry extra information carry it through an extra type constructor that a native recursion does not need. A hand-written fold over a native datatype, with a strict accumulator and a worker-wrapper split, can be faster than the Fix-encoded version, because the compiler sees the constructors directly. The schemes are a specification and a library, not a code-generation strategy.

The third limit is ergonomics. A datatype encoded as Fix f needs its functor written out, its Functor instance derived, and its pattern matches written against the layer rather than the type. Languages with better support, through a deriving mechanism or a compiler plugin, reduce the cost; languages without one make the encoding a deliberate choice for the few types where the laws are worth it.

The scope of this article is the operators above the two base schemes; the encoding they are defined over, including the sense in which a fixed point is initial or final, belongs to the fixed-point encoding itself, which is the prerequisite. What is added here is the middle of the family: the schemes that pass a subtree or a history to the algebra, the unfold that can stop early, and the fused composition.

The reason the family is worth knowing anyway is that it names the recursions. A reviewer who sees para knows the subtrees are retained; a reviewer who sees hylo knows there is no intermediate structure; a reviewer who sees cata knows the traversal is structural and can be fused. That is information a plain recursive definition does not carry, and it is the part of the abstraction that survives the performance objections. The fixed-point encoding itself is the prerequisite, and the fold is the special case that most programmers already know.