Cata Morphism

A function on finite data structures having a tree-like data type is a catamorphism if it can be computed bottom-up by replacing the constructors systematically by an evaluation function. For example, the sum of the values of a tree with numbers at the leaves is a catamorphism: replace the leaf constructor by the identity function and the join constructor by + (addition on numbers).

See also: BirdMeertensFormalism.