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.