catamorphisms

Catamorphisms are a general pattern for folds over recursively defined data types in category theory. They arise from the notion of an initial algebra for an endofunctor F on a category. An F-algebra is a pair (A, α: F A → A). A morphism of algebras h: (A, α) → (B, β) satisfies h ∘ α = β ∘ F h. An initial F-algebra is (μF, in: F μF → μF) such that for every F-algebra (X, αX) there exists a unique h: μF → X with h ∘ in = αX ∘ F h. The map h is the catamorphism.

In programming terms, μF is the canonical recursive data type given as the fixed point of F, and a catamorphism cata α: μF → X folds the data structure by supplying an algebra α: F X → X. The catamorphism is the unique fold that respects the recursive structure.

Examples include lists and trees. Lists can be described as the initial algebra for the functor F X = 1 + A × X. The corresponding catamorphism implements a standard list fold (such as foldr or foldl) by supplying an algebra α: 1 + A × X → X. Similarly, other inductive types like trees, options, and more complex structures admit catamorphisms via their defining functors. Catamorphisms are a central concept in recursion schemes, enabling abstract, modular folds that separate data representation from processing logic.