Description
Anamorphisms are generalizations of Haskell's unfoldr. A anamorphism builds a data structure with an F-coalgebra by recursively unrolling a seed.

History
The name anamorphism comes from the Greek 'ανα-' meaning "upwards". [1,2]

Notation
An anamorphism for some F-coalgebra $(X,\psi)$ is denoted with "lenses" $[\hspace{-.2em}( \psi )\hspace{-.2em}]_F$. When the functor F can be determined unambiguously, it is usually written $[\hspace{-.2em}( \psi )\hspace{-.2em}]$ or ana $\psi$.

Implementation

 
ana :: Functor f => Coalgebra f a -> a -> FixF f
ana g = InF . fmap (ana g) . g
 

Alternate implementations

 
ana g = hylo InF g
 

Duality

An anamorphism is the categorical dual of a catamorphism.

Derivation
If $(\nu F,\mathrm{out}_F)$ is the final $F$-coalgebra for some endofunctor $F$ and $(X,\psi)$ is an $F$-coalgebra, then there is a unique $F$-coalgebra homomorphism from $(X,\psi)$ to $(\nu F,\mathrm{out}_F)$ which we denote $[\!( \psi )\!]_F$.

That is to say, the following diagram commutes:

\bfig \square/>`>`>`>/[X`F X`\nu F`F \nu F;\psi`{[}\!{(}\psi{)}\!{]}`F {[}\!{(}\psi{)}\!{]}`\mathrm{out}_F] \efig

Laws

Rule Haskell
ana-charn fmap x . psi = outF . x $\equiv$ x = ana psi
ana-self fmap (ana psi) . psi = outF . ana psi
ana-id id = ana outF
ana-uniq fmap x . psi = outF . x $\wedge$ fmap y . psi = outF . y => x = y
ana-fusion fmap x . phi = psi . x => ana phi = ana psi . x
ana-compose e :: f :~> g => ana (e . outF) . ana phi = ana (e . phi)

Examples

 
data StreamF a x = a :> x
type Stream a = FixF (StreamF a)
 
instance Functor (StreamF a) where
    fmap f (a :> as) = a :> f as
 
repeat :: a -> Stream a
repeat = ana psi where
    psi n = n :> n
 
from :: Num a => a -> Stream a
from = ana psi where
    psi n = n :> (n + 1)
 

Links
[Haddock] [Source] [Field Guide]

References

[1] E. Meijer, M. Fokkinga, R. Paterson. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Proceedings, 5th ACM Conference on Functional Programming Languages and Computer Architecture.
[2] M. Fokkinga. Law and Order in Algorithmics. PhD Thesis. 1992