Every Day Recursion Schemes
Recursion schemes can have quite a steep learning curve but common patterns can be used without deep understanding.
There is a lot of excellent literature out there explaining recursion schemes but it all starts off with the fundamentals and builds up from basic concepts. An alternative way of learning is to see a real-world example and once you are comfortable using it you can see where it comes from. In this post I want to present a simple pattern that I have started seeing quite often, I think it’s reasonably easy (and useful) to start using without really knowing what’s going on underneath.
Recently I have been working on a DSL interpreter written in Purescript, this involves much manipulation of simple but recursive data types. In this situation there are some quick wins where recursion schemes can neaten up the code. Take a look at the following example which is loosely based on some real-world code that I was working on last week.
Here we have a DSL to represent some type of contract and one thing we want to do is extract a set of all people involved in a contract. This looks simple enough however things can get messy quickly as we add more constructors. Recursion schemes can help neaten things up with a catamorphism.
First we need to functorize the data type:
data ContractF f
We add a parameter
f and we replace all points of recursion with
f. Now, in order to make refactoring easier we create conversion functions.
import Matryoshka.Class.Recursive (class Recursive)
These type classes are built in to the Purescript recursion schemes library matryoshka. This makes things a touch simpler later on as we don’t need to think about converting anything ourselves.
With the boilerplate out of the way we are free to take our original pattern and convert it into a catamorphism:
-- Notice that the type of `allPeople` remains unchanged
The pattern here is that we take any point that was previously a recursive
(allPeople contract) and remove the recursion,
cata will take care of dealing with that for us. Now we can look at
algebra and think about it without recursion, much simpler for the brain. Wherever we previously had a
Contract we have already got a
Set Person. In the type
ContractF f, the
f has magically become a
This example is a bit contrived as we have massively increased the number of lines of code due to the boilerplate needed for the functorized version of
Contract. In reality you start with
Corecursive instances to enable you to refactor existing code to use the functorized type however in the end you may end up using the functorized version everywhere at which time you can get rid of the original
Contract data type and the
Corecursive instances and end up with zero boilerplate.
Additionally this example doesn’t show how much neater this small change can make things but when you have this pattern in many places and with data types that have lots of constructors, it can really make a big difference.