Recursion Scheme

Catamorphism
Type for fixed-points of F.
Laws
Cata Eval, Cata Cancel
Cata Refl
Cata Fusion
Cata Compose
Example
Base type for natural numbers.
Anamorphism
Laws
Ana Eval
Ana UP (Uniqueness Property)
Ana Fusion
Example
Hylomorphism
Laws
Hylo Split
Hylo Shift
Hylo Fusion (Left)
Hylo Fusion (Right)
Example
Base type for list.
First it expands n into [1..n] by using ana, then calculate through list using cata.
Fix and Base t
Data structure represented as fixed-point of a functor, and type family defining the relation between the data structure and the underlying functor.
Recursion Schemes of Recursion
Catamorphism
Recursion structure of list.
Folds
Paramorphism
Laws
Para Eval
Para Fusion
Example
Zygomorphism
Mutumorphism
Derive para from zygo.
Derive zygo from mutu.
Histomorphism
Example
Unfolds
Apomorphism
Futumorphism
Postpromorphism
Refolds
Jeremy Gibbons' metamorphism
Chronomorphism
Dynamorphism
Elgot Algebra
Monadic Recursion Schemes
Mendler Style
Generalisation
Recursion Schemes from Comonads
Adjoint Folds and Unfolds
References