Here are some concepts which are used in functional programming (see: Meijer, Erik; Fokkinga, Maarten; Paterson, Ross. "Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire") and these concepts are also used in category theory.

Notation | Functional Programming Term | Category Theory Term | Meaning (from here) |
---|---|---|---|

banana | catamorphism | tears down a structure level by level | |

[( )] | lense | anamorphism | builds up a structure level by level |

envelope | hylomorpism | builds up and tears down a virtual structure | |

barbed wire | paramorphism | tears down a structure with primitive recursion |

### Catamorphism and Anamorphism

If we start with an algebra that has a binary operation (S,S)->S and, instead of supplying interal values we supply a symbolic value to represent a variable or unknown, we might build up a free algebra. |

- Catamorphism - initial algebra -> other algebra.
- Anamorphism

## Catamorphism (banana)

Reduces the data structure to a required value.

#### Functional Programming Examples:

- Generalise the concept of fold.

#### Category:

Tree is a initial object in the category of F-algebras

## Anamorphism (Lenses)

Upwards morphism - Builds an invocation tree as an explicit data structure.

#### Functional Programming Examples:

- Generalise the concept of unfold
- zip and iterate are examples of anamorphisms

A notation for ana(f) found in the literature is [(f)]. The brackets used are known as lens brackets.

In programming 'lenses' can be used as the functional equivalent of a 'reference' and they allow a functional (non-mutable) data structure to be used like an imperative (mutable) data structure. They do this by duplicating the data rather than using references to the same stucture. This allows functional programs to act on imperitive structures like databases in a purely functional way. Unlike other ways of doing this lenses are composable, that is, we can nest these structures to any debth (subject to memory constraints because of this duplication).

#### Laws

get-put | P(S,G (S))=S |

put-get | G(P(S,V))=V |

Where:

- P( , ) = put
- G( ) = get

#### Haskell Example

case class Lense[A,B] { g: A => B s: (B,A) => A | { DEF get (a:A):B=g(a) DEF set(b:B,a:A): A=s(b,a)

#### References

## Hylomorphism

Composition of an anamorphism and a catamorphism. Invocation tree is isomorphic to a function which processes lists.

### Example Monoid

free monoid = list

- Fold is a catamorphism
- Unfold is a anamorphism

Fold Left | |

Fold Right |

So the fold operation takes a list and a monoid and returns a value

Googles MapReduce software framework.

### Example Field

free field = tree?