## Description Catamorphisms are generalizations of the concept of a fold in functional programming. A catamorphism deconstructs a data structure with an F-algebra for its underlying functor. ## History The name catamorphism appears to have been chosen by Lambert Meertens . The category theoretic machinery behind these was resolved by Grant Malcolm , and they were popularized by Meijer, Fokkinga and Paterson. The name comes from the Greek 'κατα-' meaning "downward or according to". A useful mnemonic is to think of a catastrophe destroying something.

Notation
A catamorphism for some F-algebra (X,f) is denoted (|f|)F. When the functor F can be determined unambiguously, it is usually written (|φ|) or `cata` φ. Due to this choice of notation, a catamorphism is sometimes called a banana and the (|.|) notation is sometimes referred to as banana brackets. ## Haskell Implementation ```haskell type Algebra f a = f a -> a newtype Mu f = InF { outF :: f (Mu f) } cata :: Functor f => Algebra f a -> Mu f -> a cata f = f . fmap (cata f) . outF ``` ## Alternate Definitions ```haskell cata f = hylo f outF cata f = para (f . fmap fst) ``` ## Duality A catamorphism is the categorical dual of an anamorphism. ## Derivation If (μF,inF) is the initial F-algebra for some endofunctor F and (X,φ) is an F-algebra, then there is a unique F-algebra homomorphism from (μF,inF) to (X,φ), which we denote (|φ|)F. That is to say, the following diagram commutes: ## Laws
cata-cancel
`cata phi . InF = phi . fmap (cata phi)`
cata-refl
`cata InF = id`
cata-fusion
`f . phi = phi . fmap f => f . cata phi = cata phi`
cata-compose
`eps :: forall x. f x -> g x =>cata phi . cata (In . eps) =cata (phi . eps)`