Friday, 12 December 2014

Recursion Schemes: Excursion 2


We're required to implement embed in order to use Unfoldable.
embed puts our base functor into the recursive type.

For a list for example we have:

embed :: Base [a] [a] -> [a]
embed (Cons a l) = a:l
embed Nil = []

And this allows us to infinitely unfold our base functor into the recursive type with an anamorphism.

ana :: Unfoldable t => (a -> Base t a) -> a -> t
ana f = m where m = embed . fmap m . f

The anamorphism is the inverse of the catamorphism. In a catamorphism, we project onto the base functor, then fold the values encased in the functor and then fold the outer. In an anamorphism we unfold once, then use the values inside the functor as seeds for the next unfolds, and then inject it into a recursive type.

The generalized anamorphism is a bit more fun:
gana :: (Unfoldable t, Monad m) => (forall b. m (Base t b) -> Base t (m b))
             -> (a -> Base t (m a)) -> a -> t
Constructing a value for this type follows similarly from the anamorphism except the monad now gives us a bit more trouble. We want something of the form Base t(Base t(Base t ....

We proceed using the same structure as before, first unfurling one layer to get Base t (m a).
Now we need to recursively unfold the inner layers. So we're going to need a function f that does that.
f will eventually need to inject the base functor into the recursive type, so we're going to need a value
Base t t. What the monad does is provide us with an additional little algebra over the 'a'. So our function that collapses the base functor must evaluate the monad and then fold that into the recursive type. So f must have type : Base t (m a) -> Base t t. In order to evaluate the monad we have been provided with a distributive law, that pushes the monad inside the functor.

m : Base t (m a) -> Base t t
m x = fmap (embed . m . fmap join . f . fmap g) x

We first unfurl the inner 'a' one more time to obtain a Base t (m (Base t (m a)). Now we distribute the monad across our base functor to obtain Base t(Base t( m (m a)). We can now evaluate the monad using join to get Base t(Base t(m a)). Now the inner functor is in the exact form we need to unfurl it further using m. Finally we can embed this fixed form of our base functor into our recursive type, and we are done.

gunfold' :: (Unfoldable t, Monad m, Functor m) =>
          (forall b. m (Base t b) -> Base t (m b))
          -> (a -> Base t (m a)) -> a -> t
gunfold' f g a = embed $ m (g a)
      m x = fmap (embed . m . fmap join . f . fmap g) x

No comments:

Post a Comment