// Workers AI · dad joke modeWhat did anamorphism say to its date? You distort my view.

For other uses, see Anamorphosis (disambiguation).

Not to be confused with Catamorphism.

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 (the notion most naturally considered the "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 are 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 fixed point [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 F value, where:

data Maybe a = Just a | Nothing
type F value x = Maybe (value, x)

One can easily check that indeed the type [value] is isomorphic to F value [value], and thus [value] is the fixed point. (Also note that in Haskell, least and greatest fixed points of functors coincide, therefore inductive lists are the same as coinductive, potentially infinite lists.)

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 x and a function f that yields either a pair of a value and a new state, or an indication that the list has ended. 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 ana, 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, ana f 3 will compute the list [2,1,0].

Anamorphisms on other data structures

An anamorphism can be defined for any recursive type, according to a generic pattern, generalizing the ana for lists given above.

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, v, r) -> Branch (ana unspool l) v (ana unspool r)

To better see the relationship between the recursive type and its anamorphism, note that Tree and List can be defined thus:

 newtype List a = List {unCons :: Maybe (a, List a)}

 newtype Tree a = Tree {unNode :: Either a (Tree a, a, Tree a)}

The analogy with ana appears by renaming b in its type:

 newtype List a = List {unCons :: Maybe (a, List a)}
 anaList ::       (list_a       -> Maybe (a, list_a)) -> (list_a -> List a)

 newtype Tree a = Tree {unNode :: Either a (Tree a, a, Tree 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 ana, with the recursive mentions of the type replaced with b.

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 Bird–Meertens formalism, informally known as Squiggol.

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)]. The function 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) = (a,b) : zip as bs
 zip _      _      = []

 iterate f x = x : iterate f (f x)

To see this, we can define both in terms of the generic unfold ana given above:

 zip2 :: [a] -> [b] -> [(a, b)]
 zip2 as bs = ana step (as, bs)
   where step (x:xs, y:ys) = Just ((x, y), (xs, ys))
         step _            = Nothing

 iterate2 :: (a -> a) -> a -> [a]
 iterate2 f = ana (\x -> Just (x, f x))

In a language like Haskell, even the abstract functions 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.

That means the following. Suppose (A, fin) is a final F-coalgebra for some endofunctor F on some category. 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:

• $h=\mathrm {ana} \ f$
• $\mathrm {fin} \circ h=Fh\circ f$

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.

See also

• Morphism
• Morphisms of F-algebras and F-coalgebras
  • From an initial algebra to an algebra: Catamorphism
  • An anamorphism followed by a catamorphism: Hylomorphism
  • Extension of the idea of catamorphisms: Paramorphism
  • Extension of the idea of anamorphisms: Apomorphism

External links

• Anamorphisms in Haskell