Recursion Schemes

This is a simple and practical introduction to recursion schemes in functional programming.

Recursion schemes are higher order functions (HOF) that can be used as building blocks for composing recursive algorithms. Recursion schemes separates the recursive part of a recursive algorithm from the actual calculation the same way the functions like Array.map separate the the iteration part from the calculation that should be done on each element.

This article will be guiding you through a thought process to understanding recursion schemes by inventing them yourself.

Recap: Higher Order Functions — for vs map

Before we start lets revisit a well known higher order function: map. Originally rooted in function programming, nowadays it is commonly used in imperative and object oriented programming languages. It allows to express an element-wise operation over some container object.

Take a look at the following two examples. The first one iterates over an array to multiply each element by two, collecting the results in a new array.

The next one achieves the same goal but separates the process of iteration and the element-wise calculation into two separte functions. The function doing the interation and collecting the resulting values is called arrayMap, or typically just map.

There are many advantages of separating the iteration from the elementwise calculation. The most obvious one is that the iteration has only to be defined once and can be reused:

Further advantages are: Intentions and invariants are expressed more clearly and the ease of later refactorings. Applying the map function will not change the number of elements in the array and will not change the order of the elements. Abstracting away the specific iteration stragegy allowes for later changes and optimizations. For example the internal iteration order could be reversed or eben even parallelized without effecting the observable result:

The third advantage is that the same concept of applying an element-wise transformation can be implemented for other containers of elements. For example for a binary tree as the one below:

A corresponding map function could be implemented as follows:

Then we coule use the mapTree function, the same way as we did with the mapArray function before, to transform each element in the tree:

So we have seen that abstracting the process of stepping through a data structure by separating the stepping from the work to do at each step is a powerful tool.

Recursive data structures

With the binary tree in the example above we have seen that the corresponding map function allowed us to work with a recursive data structure without re-implementing the recursive part our self each time.

But by the nature of the map function we were limited to modifying each value of the tree separately, having not access to the tree itself. What if we want to do actual tree-related calculations but still abstract away the recursive walking?

Lets take a look at a few typical cases. Say we want to determine the height of the tree, count the leafs of the tree, count the total number of nodes, find the minimum value inside the tree and find the maximum value inside the tree. We also want to serialize our tree into a string, for better readability

Lets first implement one function for each of our goals by hand. Afterwards we will try to find similaries in the recursion structure and come up with a general reusable solution.

All the implementations above look very similar. All of them check if the current node we are looking at is a leaf (i.e. has a value property). If so, a base case result is returned, either a constant or a something based on the value stored in the leaf. If on the other hand the current node is an inner node, two recursive function calls are invoked (one for the left and one for the right branch of the tree) and then their result is combined in a speicific way.

This pattern of similarity between these function is one of the recursion schemes we are after. Lets try to extract this pattern of recursive function calls into a common pattern. We take one of the function definitions above and try to move all the specific calculations into functions parameters to be passed in later:

Instead of hardcoding how the recursive results for the two branches shall be combined and what to do with the leaf nodes, we accept to callback functions: handleLeaf is called with the value stored in each leaf (similar to fn in our treeMap function before) and handleBranch is called with the two results from both of the recursive calls.

Now be can express all of our tree-based calculations from above in terms of our new binaryTreeReduce function:

That worked great! We have successfully abstracted the recursion into a single binaryTreeReduce function. Are we done? Have we mastered the recursion scheme? Almost, but we are not quite done that.

Other recursive data structures

The binaryTreeReduce function does work for our binary tree but what if we have other recursive data structures we want to work with? For example linked lists, trees with other than exactly two branches or trees with values stored on the inner nodes as well?

It would be nice if we could come up with a single recursiveReduce function that works the same for all of these structures, the same way that the interface of a map(fn, collection) functions works for both lists, arrays, trees and other collections (more preciseley functors)

Lets write down some of the recursive data structures we want to work with and start from there:

Next lets try to implement the function to find the minimum element of each of these three structures. Afterwards we try to see a common pattern in each of the three implementations:

We can observe that each function differs in the number of branches, depending on the structure of the recursive data structure. For the linked list we need only two branches, one for the nil case at the end of the list and one for the case of list having a head. For the binary tree with either an inner node with left/right children or an empty node or a leaf node with a single value, the recursive function needs to handle each of the three conditions.

Also the number of arguments of the functions vary. For the tree that contains at least one leaf node with a value we do not need a fallback value. But for the other two structures we need a fallback value to return in case the structure itself does not contain any value.

How could we possibly unify all three of these functions into a common interface? Lets take it slowly and first implement a generic function for each of the structures individually again, as we did with binaryTreeReduce for the simple binary tree above:

Now we can see even more cleary that the number of needed handle-callbacks vary for each reduction and the even the number of argument each handle-callback takes, varies.

But what if we could merge all the callbacks into a single function and leave it for this function to handle each possible case correctly? Lets try:

Did you notice what we did here? We merged all the callback functions into a single handleCases callback that takes only a single value as argument. What what exactly is this argument that we pass to handleCases? It is either an object containing the results of the recusive function calls, or the value store in the leafs of the data structure, in case we hit a base case.

But look again: the value we pass to handleCases reflects the structure of the node we are currently processing. For example when processing an inner node of a binary tree with inner values, we call handleCases({ value, left, right, }) with value containing the value in the current node, but left and right not containing the sub trees of the original tree, but instead the already calculated results of the two recursive calls.

What we pass to the handleCases looks structurally like a node of the the tree but instead of actually containing the recursive structure of the tree it is just a flat container for the the results of the recursive function calls.

So by mirroring the structure of the recursive tree nodes we can capture all the results of our recursive function calls an pass it to to our handler function as a single value. The handler function can then inspect in which case of the structure the recursion is currently working in.

But there is more! Look at the each of the handleCases(...) function calls. For example this one:

Wow! All the cases in binaryTreeWithEmptyNodesReduce (and the other ...Reduce functions respectively) are following exactly the same structure. The just copy the node, replacing the recursive fields and apply the handleCases function to the now flat copy of the node.

Could we extract the make a flat copy of the node and replace the recursive parts into a separate function? Yes we can! Take a look:

Now look at that! The binaryTreeRecursionReplacer looks almost like our map function from the beginning, but instead of applying the provided function (replacer) to the value stored in a node, the function is applied to the recursive fields (left and right). So we can think of it as an alternative way of mapping over the tree node.

Also look at the binaryTreeReduce function now. It is really short now! The handling of all the cases has been moved into the binaryTreeRecursionReplacer function. What is left in binaryTreeReduce is the pure recursion. This is our recursion scheme!

Lets put everything back together:

References

TBD