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>> 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>> mergesort <span class="hljs-string">"aloha"</span><span class="hljs-string">"aahlo"</span>> 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.