## 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 [1]. The category theoretic machinery behind these was resolved by Grant Malcolm [2][3], and they were popularized by Meijer, Fokkinga and Paterson[4][5]. 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)`
1. L. Meertens. First Steps towards the theory of Rose Trees. Draft Report, CWI, Amsterdam, 1987.
2. G. Malcolm. PhD. Thesis. University of Gronigen, 1990.
3. G. Malcolm. Data structures and program transformation. Science of Computer Programming, 14:255--279, 1990.
4. E. Meijer. Calculating Compilers, Ph.D Thesis, Utrecht State University, 1992.
http://research.microsoft.com/~emeijer/Papers/Thesis.pdf
5. E. Meijer, M. Fokkinga, R. Paterson, Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire, 5th ACM Conference on Functional Programming Languages and Computer Architecture.
http://research.microsoft.com/~emeijer/Papers/fpca91.pdf
6. T. Uustalu, V. Vene. Coding Recursion a la Mendler. Proceedings 2nd Workshop on Generic Programming, WGP'2000, Ponte de Lima, Portugal, 6 July 2000
http://citeseer.ist.psu.edu/314266.html
7. T. Uustalu, V. Vene, A. Pardo. Recursion schemes from Comonads. Nordic Journal of Computing. Volume 8 , Issue 3 (Fall 2001). 366--390, 2001 ISSN:1236-6064