*** Welcome to piglix ***

Anamorphism


In category theory, the concept of anamorphism ("ana" from the Greek = upwards; "morphism" from the Greek = form, shape) denotes a morphism from a coalgebra to the final coalgebra for that endofunctor. These objects have been applied to functional programming as unfolds. The categorical dual of the anamorphism is the catamorphism.

In functional programming, an anamorphism is a generalization of the concept of unfolds on 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.

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:


...
Wikipedia

...