In functional programming, the concept of catamorphism (from the Ancient Greek: κατά "downwards" and μορφή "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra.
Catamorphisms provide generalizations of folds of lists to arbitrary algebraic data types, which can be described as initial algebras.
The dual concept is that of anamorphism that generalize unfolds.
-algebra, the uniquely specified morphism from the initial object is denoted by
and hence characterized by the following relationship: Another notation found in the literature is
The open brackets used are known as banana brackets, after which catamorphisms are sometimes referred to as bananas, as mentioned in Erik Meijer et al.[1] One of the first publications to introduce the notion of a catamorphism in the context of programming was the paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, by Erik Meijer et al.,[1] which was in the context of the Squiggol formalism.
The general categorical definition was given by Grant Malcolm.
[2][3] We give a series of examples, and then a more global approach to catamorphisms, in the Haskell programming language.
Consider the functor Maybe defined in the below Haskell code: The initial object of the Maybe-Algebra is the set of all objects of natural number type Nat together with the morphism ini defined below:[4][5] The cata map can be defined as follows:[5] As an example consider the following morphism: Then cata g ((Succ.
For a fixed type a consider the functor MaybeProd a defined by the following: The initial algebra of MaybeProd a is given by the lists of elements with type a together with the morphism ini defined below:[6] The cata map can be defined by: Notice also that cata g (Cons s l) = g (Just (s, cata g l)).
As an example consider the following morphism: cata g (Cons 10 EmptyList) evaluates to 30.
The cata map is closely related to the right fold (see Fold (higher-order function)) of lists foldrList.
The morphism lift defined by relates cata to the right fold foldrList of lists via: The definition of cata implies, that foldrList is the right fold and not the left fold.
This merging of a pair can be encoded as two functions of type a -> b resp.
Deeper category theoretical studies of initial algebras reveal that the F-algebra obtained from applying the functor to its own initial algebra is isomorphic to it.
Strong type systems enable us to abstractly specify the initial algebra of a functor f as its fixed point a = f a.
The recursively defined catamorphisms can now be coded in single line, where the case analysis (like in the different examples above) is encapsulated by the fmap.
Since the domain of the latter are objects in the image of f, the evaluation of the catamorphisms jumps back and forth between a and f a.
Repeated application of the Maybe functor generates a chain of types, which, however, can be united by the isomorphism from the fixed point theorem.
We introduce the term zero, which arises from Maybe's Nothing and identify a successor function with repeated application of the Just.
For this we must provide the tree container data type so that we can set up the fmap (we didn't have to do it for the Maybe functor, as it's part of the standard prelude).