anamorphisms

Anamorphism, in category theory and functional programming, is the dual notion of a catamorphism. It is a corecursive process that unfolds a data structure from a seed value according to a functor F, yielding an element of a final coalgebra for F.

In category-theoretic terms, a coalgebra for a functor F is a pair (X, c) with a structure map c: X -> F X. The final coalgebra (Z, z) comes with a structure map z: Z -> F Z and has the universal property that for every coalgebra (X, c), there exists a unique coalgebra morphism h: X -> Z making the diagram commute: z ∘ h = F h ∘ c. This morphism h is called the anamorphism; it unfolds seeds into the final coalgebra along F’s shape.

In functional programming, anamorphisms generalize unfolding. Given a seed value and a step function describing how to generate the next layer, an anamorphism builds a (potentially infinite) data structure of the final coalgebra’s form. The common practical counterpart is unfold, often used to generate streams or lazy trees. Anamorphisms are frequently combined with catamorphisms in hylomorphisms to realize whole computations.

Relation to terminology: the term anamorphism is the dual of the catamorphism (fold). Some sources reserve specific naming for the morphism into a final coalgebra; others loosely refer to unfolding as anamorphisms or unfold operations.

Examples and use: used for corecursive definitions, coinductive data structures, and lazy generation of infinite objects in programming languages with lazy evaluation. They provide a principled way to define how to grow a structure from a seed rather than how to fold one.