User:Ezrakilty/Draft of Anamorphism as generic function

In functional programming, an anamorphism is a kind of generic function which can (co)recursively construct a result of a certain type and which is parameterized by functions that determining what the next single step of the construction is. The term comes from Greek ἀνά (upwards) + morphism (from Greek μορφή, or form, shape) and the concept has its grounding in Category theory.

The concept of anamorphism generalizes the list-producing unfold functions to arbitrary algebraic data types that can be described as final coalgebras. In fact, the terms 'anamorphism' and "unfold" (as a noun) are often used interchangeably. Anamorphisms, which are co-recursive, are dual to catamorphisms, which are recursive, just as unfolds are dual to folds.

Anamorphisms on Lists

An unfold on lists would build a (potentially infinite) list from a seed value. Typically, the unfold takes a seed value `x`, a one-place operation `unspool` that yields a pairs of such items, and a predicate `finished` which determines when to finish the list (if ever). In the action of unfold, the first application of `unspool`, to the seed `x`, would yield `unspool x = (y,z)`. The list defined by the unfold would then begin with `y` and be followed with the (potentially infinite) list that unfolds from the second term, `z`, with the same operations. So if `unspool z = (u,v)`, then the list will begin `y:u:...`, where `...` is the result of unfolding v with r, and so on.

A Haskell definition of an unfold, or anamorphism for lists, called `ana`, is as follows:

```-- The type signature of 'ana':
ana :: (b->(a,b)) -> (b->Bool)-> b -> [a]
-- Its definition:
ana unspool finished x = if finished x
then []
else a : ana unspool finished y
where (a,y) = unspool x
```

(Here `finished` and `unspool` are parameters of the function, like `x`.) We can now implement quite general functions using ana.

Anamorphisms on other data structures

An anamorphism can be defined for any recursive type, according to a generic pattern. For example, the unfold for the tree data structure

```data Tree a = Leaf a | Branch Tree a Tree
```

is as follows

```ana :: (b->Either a (b,a,b)) -> b -> Tree a
ana unspool x = case unspool x of
Left a -> Leaf a
Right (l,x,r) -> Branch (ana unspool l) x (ana unspool r)
```

History

One of the first publications to introduce the notion of an anamorphism in the context of programming was the paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire,[1] by Erik Meijer et al., which was in the context of the Squiggol programming language.

Applications

Functions like `zip` and `iterate` are examples of anamorphisms. `zip` takes a pair of lists, say ['a','b','c'] and [1,2,3] and returns a list of pairs [('a',1),('b',2),('c',3)]. `Iterate` takes a thing, x, and a function, f, from such things to such things, and returns the infinite list that comes from repeated application of f, i.e. the list [x, (f x), (f (f x)), (f (f (f x))), ...].

``````zip (a:as) (b:bs) = if (as==[]) || (bs ==[])   -- || means 'or'
then [(a,b)]
else (a,b):(zip as bs)

iterate f x = x:(iterate f (fx))```
```

To prove this, we can implement both using our generic unfold, `ana`, using a simple recursive routine:

```zip2 = ana g p
where
p (as,bs) = (as==[]) || (bs ==[])
g ((a:as), (b:bs)) = ((a,b),(as,bs))
```
```iterate2 f = ana (\a->(a,f a)) (\x->False)
```

Ruby comes with an explicit unfold operation; so, for example:

```10.unfold { |n| n-1 unless n == 1 }.inspect
=> [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
```
```10.class.unfold(&:superclass).inspect
=> [Fixnum, Integer, Numeric, Object]
```

In a language like Haskell, by contrast, even the abstract functions `fold`, `unfold` and `ana` are merely defined terms, as we have seen from the definitions given above.

Anamorphisms in category theory

In category theory, anamorphisms are the categorical dual of catamorphisms.

Notation

A notation for ana f found in the literature is $[\!(f)\!]$. The brackets used are known as lens brackets, after which anamorphisms are sometimes referred to as lenses.