Editing User:Michiexile/MATH198/Lecture 9 (section)

====Anamorphisms====

An ''anamorphism'' is the categorical dual to the catamorphism. It is the canonical morphism from a coalgebra to the final coalgebra for that endofunctor. 

Here, we start unstructured, and erect a structure, induced by the coalgebra structures involved. 

'''Example''': we can write a recursive function 
<haskell>
first :: Int -> [Int]
first 1 = [1]
first n = n : first (n - 1)
</haskell>
This is an anamorphism from the coalgebra for <math>P_{\mathbb N}(X) = 1 + \mathbb N\times X</math> on <math>\mathbb N</math> generated by the two maps
<haskell>
c 0 = Left ()
c n = Right (n, n-1)
</haskell>
and we observe that we can chase through the diagram
:[[Image:CoalgebraMorphism.png]]
to conclude that therefore
<haskell>
f 0 = []
f n = n : f (n - 1)
</haskell>
which is exactly the recursion we wrote to begin with.

MFP define the anamorphism by a fixpoint as well, namely:
<haskell>
ana :: (b -> F a b) -> b -> T a
ana psi = mu (\x -> inT . fmap x . psi)
</haskell>

We can, again, recast our illustration above into a structural anamorphism, by:
<haskell>
-- Reuse mu, F, T from above
inT :: F a (T a) -> T a
inT Nil = []
inT (Cons a as) = a:as

fpsi :: Int -> F Int Int
fpsi 0 = Nil
fpsi n = Cons n (n-1)
</haskell>

Again, we can note that the implementation of <hask>fpsi</hask> here is exactly the <hask>c</hask> above, and the resulting function will - as we can verify by compiling and running - give us the same kind of reversed list of the n first integers as the <hask>first</hask> function above would.