Practical Recursion Schemes at PragPub

Jared Tobin is one of our consultants at fugue.co—he's a programmer and researcher based out of Auckland, New Zealand. Jared's article in this month's issue of PragPub, The Pragmatic Bookshelf's magazine affiliation, is a helpful read if you're interested in functional programming and Haskell in particular. Check out "Practical Recursion Schemes" here.
 

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:

 

<code class="language-haskell"><span class="hljs-typedef"><span class="hljs-keyword">data</span> <span class="hljs-type">TreeF</span> a r =</span>    <span class="hljs-type">EmptyF</span>  | <span class="hljs-type">LeafF</span> a  | <span class="hljs-type">NodeF</span> r r  <span class="hljs-keyword">deriving</span> <span class="hljs-type">Functor</span></code>

 

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:

 

<code class="language-haskell"><span class="hljs-title">unfolder</span> []  = <span class="hljs-type">EmptyF</span><span class="hljs-title">unfolder</span> [x] = <span class="hljs-type">LeafF</span> x<span class="hljs-title">unfolder</span> xs  = <span class="hljs-type">NodeF</span> l r <span class="hljs-keyword">where</span>  (l, r) = splitAt (length xs `div` <span class="hljs-number">2</span>) xs</code>

 

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:

 

<code class="language-haskell">folder EmptyF      = []folder (LeafF x)   = [x]folder (NodeF l r) = merge l r</code>

 

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

 

<code class="language-haskell">mergesort = hylo folder unfolder</code>

 

And it works just like you'd expect:

 

<code>&gt; mergesort <span class="hljs-array">[<span class="hljs-number">1</span>,<span class="hljs-number">10</span>,<span class="hljs-number">3</span>,<span class="hljs-number">4</span>,<span class="hljs-number">5</span>]</span><span class="hljs-array">[<span class="hljs-number">1</span>,<span class="hljs-number">3</span>,<span class="hljs-number">4</span>,<span class="hljs-number">5</span>,<span class="hljs-number">10</span>]</span>&gt; mergesort <span class="hljs-string">"aloha"</span><span class="hljs-string">"aahlo"</span>&gt; mergesort <span class="hljs-array">[T<span class="hljs-variable">rue</span>, F<span class="hljs-variable">alse</span>, F<span class="hljs-variable">alse</span>, T<span class="hljs-variable">rue</span>, F<span class="hljs-variable">alse</span>]</span><span class="hljs-array">[F<span class="hljs-variable">alse</span>, F<span class="hljs-variable">alse</span>, F<span class="hljs-variable">alse</span>, T<span class="hljs-variable">rue</span>, T<span class="hljs-variable">rue</span>]</span></code>

 

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.

 

Categorized Under

Programming

Secure Your Cloud

Find security and compliance violations in your cloud infrastructure and ensure they never happen again.