The concept of a catamorphism is grounded in category theory, and has been applied to functional programming. The term comes from Greek κατα- (downwards, according to) + morphism, the latter from Greek μορφή (form, shape). Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. ... In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ...

Catamorphisms in functional programming

In functional programming, a catamorphism is a generalization of the folds on lists known from functional programming to arbitrary abstract data types that can be described as initial algebras. Look up list in Wiktionary, the free dictionary. ... Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

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 programming language. Squigol is a functional language based on the Bird-Meertens Formalism. ...

Example

Using Haskell notation: Haskell is a standardized pure functional programming language with non-strict semantics, named after the logician Haskell Curry. ...

 data Tree a = Tip a | Join (Tree a) (Tree a) foldTree :: (a -> r, r -> r -> r) -> Tree a -> r foldTree (f1,f2) (Tip x) = f1 x foldTree (f1,f2) (Join b1 b2) = f2 (foldTree (f1,f2) b1) (foldTree (f1,f2) b2) 

Here foldTree (f1,f2) is a catamorphism for the Tree a data type. The function foldTree takes two parameters: f1 :: a -> r and f2 :: r -> r -> r, generalizing the two constructors of the Tree data type, namely Tip :: a -> Tree a and Join :: Tree a -> Tree a -> Tree a.

The usual Haskell style favours currying, but switching to the (isomorphic) uncurried view, the parameters to foldTree are typed as follows: In computer science, currying is the technique of transforming a function taking multiple arguments into a function that takes a single argument (the first of the arguments to the original function) and returns a new function that takes the remainder of the arguments and returns the result. ...

 f1 :: a -> r f2 :: (r, r) -> r 

Catamorphisms in category theory

Category theory provides the necessary concepts to give a generic definition that accounts for all initial data types (using an identification of functions in functional programming with the morphisms of the category Set or some related concrete category). This was done by Grant Malcolm in his Ph.D. Thesis Algebraic Types and Program Transformation (Univ. Groningen, 1990)[2] and the article Data structures and program transformation[3]. In mathematics, a morphism is an abstraction of a function or mapping between two spaces. ... In mathematics, categories allow one to formalize notions involving abstract structure and processes which preserve structure. ...

Specialized to the above example, the formal definition of a catamorphism is as follows: For fixed type a, the pair (r, [f1,f2]) is an F-algebra, where F is the functor sending r to a + r × r. The pair (Tree a, [Tip,Join]) is also an F-algebra, and specifically the initial F-algebra. This means that there is a unique homomorphism to any other F-algebra. That unique homomorphism is called a catamorphism. In mathematics, specifically in category theory, an -coalgebra for an endofunctor is an object of together with a -morphism . In this sense F-coalgebras are dual to F-algebras. ... In abstract algebra, a homomorphism is a structure-preserving map. ...

In the code example above, foldTree is the function that constructs these catamorphisms.

The general case

If (A, in) is the initial F-algebra for some endofunctor F (so in is a morphism from FA to A), and (X, f) is an F-algebra, there is a unique homomorphism from (A, in) to (X, f), which may be denoted cata f (leaving the "carrier" X implicit). (Here "cata" is a generic name for what was called "foldTree" for the specific case from the example.) In category theory, a functor is a special type of mapping between categories. ...

Properties

Let F be given and fixed. Using the definition of homomorphism, the uniqueness property can be expressed as: for all F-algebras (X, f), and all h from A to X, the following two statements are equivalent:

• h = cata f
• h o in = f o Fh

Notation

Another notation for cata f found in the literature is . The open brackets used are known as banana brackets, after which catamorphisms are sometimes referred to as bananas.