Friday 12 December 2014

Recursion Schemes Excursions

I thought I'd document my excursion into recursion schemes.
For ever and always, recursive patterns have and will pop up, but I had to squash the combinators to fit. I thought I'd finally cut a swathe through the higher dimensional morph-ine like haze recursion schemes induces.

So, to be terse:
Recursion schemes maps our recursive type into its base functor using a type family 'Base'.
In order to use harness the power of its combinators we need to create instances of the classes Foldable and Unfoldable.
An instance of Foldable implies that we can 'project' our recursive type onto the base functor.
An instance of Unfoldable implies we can embed our base functor into the recursive type.
Instances of both mean that the recursive type and the base functor are isomorphic. The base-functor should always be <= the recursive type.

So onto the first of them:
A catamorphism is a fold, it builds up a tower of applications of f and then collapses them from the inside - a right fold. The projection allows us to talk in terms of the base functor which we know how to reach inside of and twiddle around in. The 'fmap m' folds the inner part and provides the folded version to our algebra which simply performs a single step of the fold.

cata :: Foldable t => (Base t a -> a) -> t -> a
cata f = m where m = f . fmap m . project


Next post, para-morphisms.

No comments:

Post a Comment