Haskell Language Recursion Schemes Unfolding a structure one layer at a time


Anamorphisms, or unfolds, model primitive corecursion. ana builds up a fixpoint layer by layer, using a coalgebra function (or unfolding function) to produce each new layer. ana requires a Functor instance for the template type f.

ana :: Functor f => (a -> f a) -> a -> Fix f
ana f = Fix . fmap (ana f) . f

-- list example
unfoldr :: (b -> Maybe (a, b)) -> b -> List a
unfoldr f = ana coalg
    where coalg x = case f x of
                         Nothing -> Nil_
                         Just (x, y) -> Cons_ x y

Note that ana and cata are dual. The types and implementations are mirror images of one another.