# User:Ezrakilty/Draft of Anamorphism as pattern of function definition

For other uses, see Anamorphosis (disambiguation).

In functional programming, an anamorphism is a function defined according to a certain pattern, which builds up results of an type one constructor at a time from a seed. 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. 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 anamorphism on lists builds a (potentially infinite) list from a seed value and a construction function.

In terms of a predicate finished :: b -> Bool and a function step :: b -> (a,b), a list anamorphism f has the following definition (in Haskell syntax):

f x | finished x = []
| otherwise = a : f y
where (a, y) = step x


Such a function takes a seed value, x and checks whether it is "finished" in which case it simply returns the empty list. If not, it uses the step operation to generate a "next" list element and a new seed; it generates the rest of the list by recursing with the new seed.

This pattern can be abstracted into a higher-order function definition, as followss:

-- The type signature of 'ana':
ana :: (b->(a,b)) -> (b->Bool)-> b -> [a]
-- Its definition:
ana step finished x = f x
where
f x | finished x = []
| otherwise = a : f y
where (a, y) = step x


## 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.