Anamorphism

In computer programming, an anamorphism is a function that generates a sequence by repeated application of the function to its previous result. You begin with some value A and apply a function f to it to get B. Then you apply f to B to get C, and so on until some terminating condition is reached. The anamorphism is the function that generates the list of A, B, C, etc. You can think of the anamorphism as unfolding the initial value into a sequence.
The above layman's description can be stated more formally in category theory: the anamorphism of a coinductive type denotes the assignment of a coalgebra to its unique morphism to the final coalgebra of an endofunctor. These objects are used in functional programming as "unfolds".
The categorical dual (aka opposite) of the anamorphism is the catamorphism.
Anamorphisms in functional programming.
In functional programming, an anamorphism is a generalization of the concept of "unfolds" on coinductive lists. Formally, anamorphisms are generic functions that can corecursively construct a result of a certain type and which is parameterized by functions that determine the next single step of the construction.
The data type in question is defined as the greatest fixed point "ν X . F X" of a functor "F". By the universal property of final coalgebras, there is a unique coalgebra morphism "A → ν X . F X" for any other "F"-coalgebra "a : A → F A". Thus, one can define functions from a type "A" _into_ a coinductive datatype by specifying a coalgebra structure "a" on "A".
Example: Potentially infinite lists.
As an example, the type of potentially infinite lists (with elements of a fixed type "value") is given as the fixpoint "[value] = ν X . value × X + 1", i.e. a list consists either of a "value" and a further list, or it is empty. A (pseudo-)Haskell-Definition might look like this:
data [value] = (value:[value]) | []
It is the fixed point of the functor codice_1, where:
data Maybe a = Just a | Nothing
data F value x = Maybe (value, x)
One can easily check that indeed the type codice_2 is isomorphic to codice_3, and thus codice_2 is the fixed point.
The "anamorphism" for lists (then usually known as "unfold") would build a (potentially infinite) list from a state value. Typically, the unfold takes a state value codice_5 and a function codice_6 that yields either a pair of a value and a new state, or a singleton to mark the end of the list. The anamorphism would then begin with a first seed, compute whether the list continues or ends, and in case of a nonempty list, prepend the computed value to the recursive call to the anamorphism.
A Haskell definition of an unfold, or anamorphism for lists, called codice_7, is as follows:
ana :: (state -> Maybe (value, state)) -> state -> [value]
ana f stateOld = case f stateOld of
 Nothing -> []
 Just (value, stateNew) -> value : ana f stateNew
We can now implement quite general functions using "ana", for example a countdown:
f :: Int -> Maybe (Int, Int)
f current = let oneSmaller = current - 1
 in if oneSmaller < 0
 then Nothing
 else Just (oneSmaller, oneSmaller)
This function will decrement an integer and output it at the same time, until it is negative, at which point it will mark the end of the list. Correspondingly, codice_8 will compute the list codice_9.
Anamorphisms on other data structures.
An anamorphism can be defined for any recursive type, according to a generic pattern, generalizing the second version of "ana" for lists.
For example, the unfold for the tree data structure
 data Tree a = Leaf a | Branch (Tree a) a (Tree a)
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)
To better see the relationship between the recursive type and its anamorphism, note that codice_10 and codice_11 can be defined thus:
The analogy with codice_7 appears by renaming codice_13 in its type:
 anaList :: (list_a -> Maybe (a, list_a)) -> (list_a -> List a)
 anaTree :: (tree_a -> Either a (tree_a, a, tree_a)) -> (tree_a -> Tree a)
With these definitions, the argument to the constructor of the type has the same type as the return type of the first argument of codice_7, with the recursive mentions of the type replaced with codice_13.
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", by Erik Meijer "et al.", which was in the context of the Squiggol programming language.
Applications.
Functions like codice_16 and codice_17 are examples of anamorphisms. codice_16 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)]. codice_19 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 (f x))
To prove this, we can implement both using our generic unfold, codice_7, using a simple recursive routine:
 zip2 = ana unsp fin
 where
 fin (as,bs) = (as==[]) || (bs ==[]) 
 unsp ((a:as), (b:bs)) = ((a,b),(as,bs))
 iterate2 f = ana (\a->(a,f a)) (\x->False) 
In a language like Haskell, even the abstract functions codice_21, codice_22 and codice_7 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 (and catamorphisms are the categorical dual of anamorphisms).
That means the following. 
Suppose ("A", "fin") is a final "F"-coalgebra for some endofunctor "F" of some category into itself.
Thus, "fin" is a morphism from "A" to "FA", and since it is assumed to be final we know that whenever ("X", "f") is another "F"-coalgebra (a morphism "f" from "X" to "FX"), there will be a unique homomorphism "h" from ("X", "f") to ("A", "fin"), that is a morphism "h" from "X" to "A" such that "fin . h = Fh . f".
Then for each such "f" we denote by ana f that uniquely specified morphism "h".
In other words, we have the following defining relationship, given some fixed "F", "A", and "fin" as above:
Notation.
A notation for ana "f" found in the literature is formula_3. The brackets used are known as lens brackets, after which anamorphisms are sometimes referred to as "lenses".