Anamorphism

An anamorphism is the generalization of unfold from lists to every recursive data type. It builds a structure from a seed, using a function, called a coalgebra, that produces one layer of the structure together with new seeds for its recursive positions. Generating a range of numbers, the digits of a number, the successive states of a simulation and the tree of recursive calls of a divide-and-conquer algorithm are anamorphisms. It is the categorical dual of the catamorphism: where a catamorphism consumes a structure layer by layer, an anamorphism produces one^[1]. Anamorphisms can produce infinite structures, such as streams, and in total languages they are the principled way to write programs that run forever while producing output^[6].

For lists, the unfold takes a function that, given the current seed, either stops or returns an element and the next seed^[2]:

It is the mirror image of the right fold: a fold replaces the list's constructors with a function and a value, and an unfold decides, at each step, which constructor to produce. The step function is the only part that differs between uses:

(* unfold: a seed, and a function that either stops or produces one
   element and the next seed. *)
let rec unfold step seed = match step seed with None -> [] | Some (x, seed') -> x :: unfold step seed'
 
let range a b = unfold (fun i -> if i >= b then None else Some (i, i + 1)) a
let digits n = List.rev (unfold (fun n -> if n = 0 then None else Some (n mod 10, n / 10)) n)
let collatz n = unfold (fun n -> if n = 0 then None else Some (n, if n = 1 then 0 else if n mod 2 = 0 then n / 2 else 3 * n + 1)) n
 
(* The same step function, but lazily: an infinite sequence, of which
   only the demanded prefix is ever computed. *)
let fibs = Seq.unfold (fun (a, b) -> Some (a, (b, a + b))) (0, 1)
let naturals = Seq.unfold (fun n -> Some (n, n + 1)) 0

range 3 9        [3; 4; 5; 6; 7; 8]
digits 90210     [9; 0; 2; 1; 0]
collatz 27       111 steps, peak 9232
fibs, first 15   [0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377]
squares of naturals that are odd, first 6: [1; 9; 25; 49; 81; 121]

The Fibonacci and natural-number sequences have no end, and are useful only because OCaml's Seq computes elements on demand^[9]: the unfold produces as many elements as Seq.take asks for. A strict list unfold with the same step function would not terminate.

For a functor $F$, a coalgebra is an object $A$ with an arrow $\psi :A\to FA$: a way of observing one layer of structure in each state. A final coalgebra $(\nu F,out)$ has exactly one homomorphism from every coalgebra into it, and that homomorphism is the anamorphism $[(\psi )]$, written with "lens brackets"^[1]:

The square says that observing the result of the anamorphism gives the layer produced by $\psi$, with the anamorphism applied to the new seeds. For lists over $a$, $FX=1+a\times X$ and a coalgebra is exactly the step function of unfold. The final coalgebra of this functor contains the finite and the infinite lists; the initial algebra, the domain of catamorphisms, contains only the finite ones. In a lazy language such as Haskell the two coincide, and a list type contains both^[3].

Codata and coinduction

Types described as final coalgebras are called codata. They are defined by how they are observed, not by how they are built: a stream is anything from which a head and a tail can be observed. The proof principle dual to induction is coinduction: two elements of a final coalgebra are equal if there is a bisimulation relating them, a relation preserved by every observation^[3][4]. Rutten developed coalgebra into a general theory of state-based systems, in which automata, transition systems and streams are all coalgebras^[4].

With the fixed point of a base functor, one anamorphism builds any recursive type. A coalgebra for binary trees takes a seed and either produces a leaf or a node with a value and two new seeds:

(* The base functor of binary trees, an anamorphism that grows a tree from
   a seed, and a catamorphism that consumes it. *)
type ('a, 'r) tree_f = Tip | Bin of 'r * 'a * 'r
type 'a tree = In of ('a, 'a tree) tree_f
 
let map f = function Tip -> Tip | Bin (l, x, r) -> Bin (f l, x, f r)
let rec ana coalg seed = In (map (ana coalg) (coalg seed))
let rec cata alg (In t) = alg (map (cata alg) t)
 
(* Coalgebra: split a list around its first element. *)
let split = function [] -> Tip | p :: xs -> Bin (List.filter (fun x -> x < p) xs, p, List.filter (fun x -> x >= p) xs)
 
(* Algebra: flatten in order. *)
let flatten = function Tip -> [] | Bin (l, x, r) -> l @ (x :: r)
let height = function Tip -> 0 | Bin (l, _, r) -> 1 + max l r
 
(* Fused: the tree is never built. *)
let rec hylo alg coalg seed = alg (map (hylo alg coalg) (coalg seed))
 
(* Streams: an infinite structure produced by an anamorphism, consumed
   only as far as needed. *)
type 'a stream = Cons of 'a * 'a stream Lazy.t
let rec ana_stream step seed = let x, seed' = step seed in Cons (x, lazy (ana_stream step seed'))
let rec take n (Cons (x, rest)) = if n = 0 then [] else x :: take (n - 1) (Lazy.force rest)

ana then cata (quicksort): [1; 2; 3; 5; 7; 8; 9]   tree height 4
hylo, no tree built:       [1; 2; 3; 5; 7; 8; 9]
stream of powers of two:   [1; 2; 4; 8; 16; 32; 64; 128; 256; 512; 1024; 2048]

Quicksort is an anamorphism that builds a binary search tree by splitting the list around a pivot, followed by a catamorphism that flattens the tree in order. The composition of an anamorphism and a catamorphism is a hylomorphism, and it can be computed without building the intermediate tree, by applying the algebra directly to each layer the coalgebra produces^[1]. The tree is then the shape of the recursion, the call tree of the algorithm, and never exists in memory.

A function that produces an infinite structure must still return each part of it in finite time. A corecursive definition is productive if every finite prefix of its result can be computed in finitely many steps. An anamorphism is productive whenever its coalgebra terminates, since each application produces one constructor before recursing, just as a catamorphism terminates whenever its algebra does. Turner proposed a total functional programming discipline with data consumed only by structural recursion and codata produced only by guarded corecursion, so that every program either terminates or is productive^[6]. Proof assistants check the same guardedness condition for corecursive definitions.

An apomorphism, dual to the paramorphism, lets the coalgebra stop early by returning a whole remaining structure instead of a new seed: inserting an element into a sorted list can copy the rest of the list once the insertion point is found^[5]. A futumorphism lets the coalgebra produce several layers at once^[7]. A metamorphism, a catamorphism followed by an anamorphism, changes representation, as in converting a number between bases; Gibbons showed when it can be computed in a streaming fashion, emitting output before all input is consumed^[8].

Haskell's Data.List.unfoldr and OCaml's Seq.unfold are list and sequence anamorphisms, and List.init and Array.init are special cases with an index as seed. Iterators and generators in imperative languages are coalgebras: a state with an operation that yields the next element and the next state. Event loops, servers and simulations that run indefinitely are corecursive, producing an unbounded stream of outputs from a state. Gibbons and Jones argued that unfolds were under-used compared with folds, and that many list-producing functions are clearer as unfolds^[2].

The word is from the Greek ἀνά, "upward". Meijer, Fokkinga and Paterson named anamorphisms together with catamorphisms and hylomorphisms in 1991^[1]. Coalgebra as the dual of algebra, with coinduction as its proof principle, was developed in the 1990s by Jacobs, Rutten and others^[3][4]. Vene and Uustalu introduced apomorphisms and futumorphisms^[5][7], and Gibbons and Jones's "The under-appreciated unfold" of 1998 made the case for unfolds in everyday functional programming^[2].

• CatamorphismA catamorphism is the generalization of fold from lists to any recursive data type: it replaces each constructor of a value with a function and combines the results bottom up. Formally it is the unique homomorphism from the initial algebra of a functor to any other algebra of that functor. Writing a recursive data type as the fixed point of a base functor lets a single cata function fold every such type, with the recursion written once and each computation reduced to an algebra that handles one layer.
• HylomorphismA function that unfolds a seed into a recursive structure and folds that structure into a result, written so the structure is never built: hylo f g = f . fmap (hylo f g) . g. The call tree of the recursion is the intermediate structure.
• FoldableFoldable is the abstraction of a container whose elements can be combined in order: a list, a tree, an option. A fold replaces the constructors of the structure with a function and a starting value, and every summary of the elements, their sum, length, maximum, list of elements or whether any satisfies a predicate, is derived from it. Equivalently, a foldable container maps each element into a monoid and combines the results (foldMap). The universal property of fold characterizes exactly which functions are folds.
• FunctorIn functional programming, a functor is a type constructor f with an operation fmap : (a -> b) -> f a -> f b that applies a function inside the structure without changing its shape, preserving identity and composition. Lists, options, trees and functions out of a fixed type are functors. The notion comes from category theory. In OCaml the word also names parametrised modules such as Map.Make.
• Lazy evaluationLazy evaluation, or call-by-need, delays computing an expression until its value is needed and then remembers the value, so it is computed at most once. It lets programs define infinite structures and consume only part of them, separates generating candidate values from choosing among them, and avoids work whose result is never used. Its costs are the memory held by unevaluated suspensions, which can cause space leaks, and harder reasoning about when work happens. Haskell is lazy by default; OCaml provides it explicitly through Lazy.t and Seq.

1. [1]E. Meijer, M. Fokkinga, R. Paterson, “Functional programming with bananas, lenses, envelopes and barbed wire”, Functional Programming Languages and Computer Architecture (1991).
2. [2]J. Gibbons, G. Jones, “The under-appreciated unfold”, ICFP (1998).
3. [3]B. Jacobs, J. Rutten, “A tutorial on (co)algebras and (co)induction”, Bulletin of the EATCS 62 (1997).
4. [4]J. J. M. M. Rutten, “Universal coalgebra: a theory of systems”, Theoretical Computer Science 249 (2000).
5. [5]V. Vene, T. Uustalu, “Functional programming with apomorphisms (corecursion)”, Proceedings of the Estonian Academy of Sciences: Physics, Mathematics 47 (1998).
6. [6]D. A. Turner, “Total functional programming”, Journal of Universal Computer Science 10 (2004).
7. [7]T. Uustalu, V. Vene, “Primitive (co)recursion and course-of-value (co)iteration, categorically”, Informatica 10 (1999).
8. [8]J. Gibbons, “Streaming representation-changers”, Mathematics of Program Construction, LNCS 3125 (2004).
9. [9]The OCaml manual, standard library module Seq.

last updated 27 September 2026