Practical Recursion Schemes at PragPub

Recursion schemes are simple, composable combinators that automate traversing nested data structures. They are a powerful abstraction that can be implemented in any language with first-class functions. Jared explores various schemes and their applications using Haskell, but the lessons here can be applied in Clojure or any true functional language.

The article details a number of recursion scheme examples. One of them is a particularly concise implementation of mergesort and, to wet your whistle for the kind of code you can write using recursion schemes, Jared elaborates on that example below.

Sorting with Style

Mergesort is a famous comparison-based sorting algorithm that starts by first recursively dividing a collection of orderable elements into smaller subcollections, and then finishes by recursively sorting and merging the smaller subcollections together to reconstruct the original (but now sorted) one.

A clear implementation of mergesort should by definition be as faithful to that high-level description as possible. We can get pretty close to that using this whole recursion schemes business.

Start with a collection of orderable elements. We can subdivide the collection into a bunch of smaller collections by using a binary tree:

data TreeF a r =  EmptyF | LeafF a | NodeF r r deriving Functor

The idea is that each node in the tree holds two subtrees, each of which contains half of the remaining elements. We can build a tree like this from a collection—say, a basic Haskell list. The following unfolder function defines what part of a tree to build for any corresponding part of a list:

unfolder [] = EmptyFunfolder [x] = LeafF xunfolder xs = NodeF l r where (l, r) = splitAt (length xs `div` 2) xs

On the other hand, we can collapse an existing tree back into a list. The following folder function defines how to collapse any given part of a tree into the corresponding part of a list:

folder EmptyF   = []folder (LeafF x)  = [x]folder (NodeF l r) = merge l r

Now to sort a list we can just glue these instructions together using what's called a hylomorphism.

mergesort = hylo folder unfolder

And it works just like you'd expect:

mergesort [1,10,3,4,5][1,3,4,5,10]  mergesort "aloha""aahlo"  mergesort [True, False, False, True, False][False, False, False, True, True]

Pretty concise! The code is eminently clean and faithful to the high-level algorithm description: first, recursively divide a collection into smaller subcollections—via a binary tree and unfolder—and then recursively sort and merge the subcollections to reconstruct the (now sorted) original one—via folder.

Recursion schemes are great tools to know about, even if you don't wind up using them often in your day-to-day work. Enjoy the article and feel free to read more at http://jtobin.ca.