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.

Spotting Catamorphisms

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.

1
2
3
4
5
6
7
8
9
10
11
data Contract
    = Null
    | Pay Person Contract
    | Redeem Person Contract
    | Choice Boolean Contract Contract

allPeople :: Contract -> Set Person
allPeople Null = Set.empty
allPeople (Pay person contract) = Set.insert person (allPeople contract)
allPeople (Redeem person contract) = Set.insert person (allPeople contract)
allPeople (Choice _ c1 c2) = Set.union (allPeople c1) (allPeople c2)

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.

Functorize all the things

First we need to functorize the data type:

1
2
3
4
5
6
7
data ContractF f
    = NullF
    | PayF Person f
    | RedeemF Person f
    | ChoiceF Boolean f f

derive instance functorContract :: Functor ContractF

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import Matryoshka.Class.Recursive (class Recursive)
import Matryoshka.Class.Corecursive (class Corecursive)

instance recursiveContract :: Recursive Contract ContractF where
    project Null = NullF
    project (Pay p c) = PayF p c
    project (Redeem p c) = Redeem p c
    project (Choice p c1 c2) = ChoiceF p c1 c2

instance corecursiveContract :: Corecursive Contract ContractF where
    embed NullF = Null
    embed (PayF p c) = Pay p c
    embed (RedeemF p c) = Redeem p c
    embed (ChoiceF p c1 c2) = Choice p c1 c2

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.

Catamorphisms

With the boilerplate out of the way we are free to take our original pattern and convert it into a catamorphism:

1
2
3
4
5
6
7
8
9
10
-- Notice that the type of `allPeople` remains unchanged
-- matryoshka takes care of the conversion between Contract and ContractF for us
allPeople :: Contract -> Set Person
allPeople = cata algebra
    where
        algebra :: Algebra ContractF (Set Person)
        algebra NullF = Set.empty
        algebra (PayF person s) = Set.insert person s
        algebra (RedeemF person s) = Set.insert person s
        algebra (ChoiceF _ s1 s2) = Set.union s1 s2

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 Set Person.

Overview

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 Recursive and 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 Recursive and 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.