Recursion Schemes: the high-school introduction
I gave a talk on Thursday the 28th of march 2019 at the 96th Paris Scala User Group session on about this. The slides are here.
Recursion schemes are said to be a tough subject. Articles and presentations often flood the audience with lots of names such as Algebra, CoAlgebra, catamorphisms, anamorhpisms, hylomorphism, etc. Is knowing all these concepts required to understand recursion schemes? I have good news for you: it isn’t! All you need, to see what recursion schemes are and why there are useful, can be presented with just a single basic function, often taught as an introduction to programming: factorial. I’m glad to welcome you to to the high-school introduction to recursion scheme 😉.
Learning Recursion Schemes
Before diving into the subject, let’s take a moment to contextualize. Recursion-schemes, like most of advanced functional programming techniques, is almost never taught in programming courses or books. It means there is a strong chance the subject, and the concepts it relies upon, is totally new to you. I want you to remember you haven’t learnt programming in one day, and you probably did not start learning programming by implementing a distributed steaming application over a spark cluster from scratch. Like most of us, you probably started by coding some sort of Hello, World!. Let’s face it, real business application are a lot more complex than this. Do you imagine what a first introduction to programming would be, if instead of asking people to write a simple Hello, World!, we would ask them to write a real state-of-the-art large-scale business application that meets all the requirements we expect in production nowadays? Learning takes time! Start with toy examples that are indeed far from real-word cases but enables you to grow your understanding, one step at a time.
The examples below are indeed toy examples. When i develop with recursion scheme, like any specialist in any field, i use specialist techniques and vocabulary (you know, the usual vocabulary from category and type theory). But if you’re reading this, it probably means you’re not a recursion-scheme specialist yet. Using complex words flatters our ego, which is very enjoyable, but developing a deep understanding of these notions is far better! So let’s put our ego aside for a moment and accept to start with the basics.
In Recursion Schemes, there is Recursion
First of all, let me present you the famous factorial function. It is defined on non-negative numbers n as the product of all numbers between 1 and n included:
$$fact(n) = 1 \times 2 \times 3 \times \cdots \times n$$To ease the presentation we will take Int as the type of non-negative integers.
Obviously in production code negative values should be handled appropriately
but for simplicity’s sake, we will define fact in Scala and in Haskell as
def fact(n: Int): Int =
if (n == 0) 1
else {
val r = fact(n-1)
n * r
}fact :: Int -> Int
fact 0 = 1
fact n = let r = fact (n - 1)
in n * rFactorial is written here as a recursive function.
As you probably know, it can also be written as an
iterative one (using a for or while loop) but the subject of this article is Recursion
Schemes, not Iterative Schemes, so let’s use recursion. This function computes fact(2) as follows:
fact(2) = 2 * fact(1)so it needs to computefact(1)fact(1) = 1 * fact(0)so it needs to computefact(0)fact(0) = 1- now that the result of
fact(0)is known, it can replace the call offact(0)by its result which givesfact(1) = 1 * fact(0) = 1 * 1 = 1 - now that the result of
fact(1)is known, it can replace the call offact(1)by its result which givesfact(2) = 2 * fact(1) = 2 * 1 = 2.
Look at how fact(n) is calling it-self: if n = 0 then it doesn’t call itself, otherwise
it calls itself on n - 1. Let’s split this definition in two parts: the first one contains all the code
relevant to how fact is calling itself but only it, the second one is made of the rest. There is no clear
rule for what is relevant and what is not. Different splits may work, they will just give rise to different
schemes, which is not a problem at all. You just need to find one that fits your needs.
For fact, the key element to note is it is not calling itself when n = 0 but otherwise calls itself
with n - 1. The constant returned in the n = 0 case and the operation done in the other one have no impact
on how fact recurses. So i choose to split it by taking all code not relevant to recursion out of
its body:
/* Part irrelevant to recursion:
* The real definitions of these variables
* have no impact on how fact is calling itself
*/
val baseCase: Int = 1
def recCase(n: Int, r: Int): Int = n * r
/* Recursion-only part:
* The only implementation details it contains
* are about how fact it calling itself
*/
def fact(n: Int): Int =
if (n == 0) baseCase
else {
val r = fact(n-1)
recCase(n, r)
}{-
Part irrelevant to recursion:
The real definitions of these variables
Have no impact on how fact is calling itself
-}
baseCase :: Int
baseCase = 1
recCase :: Int -> Int -> Int
recCase n r = n * r
{-
Recursion-only part:
The only implementation details it contains
are about how fact it calling itself
-}
fact :: Int -> Int
fact 0 = baseCase
fact n = let r = fact (n-1)
in recCase n rLet me present you another function, also defined on non-negative numbers n, but that computes this time the sum of all numbers between 1 and n included:
$$sum(n) = 1 + 2 + 3 + \cdots + n$$def sum(n: Int): Int =
if (n == 0) 0
else {
val r = sum(n-1)
n + r
}sum :: Int -> Int
sum 0 = 0
sum n = let r = sum (n - 1)
in n + rWe can apply the same technique to sum: splitting the definition into two parts,
one containing all but only recursion-relevant code, and the other the rest. It gives:
/* Part irrelevant to recursion:
* The real definitions of these variables
* have no impact on how sum is recurs
*/
val baseCase: Int = 0
def recCase(n: Int, r: Int): Int = n + r
/* Recursion-only part:
* The only implementation details it contains
* are about how fact it recurs
*/
def sum(n: Int): Int =
if (n == 0) baseCase
else {
val r = sum(n-1)
recCase(n, r)
}{-
Part irrelevant to recursion:
The real definitions of these variables
Have no impact on how fact is calling itself
-}
baseCase :: Int
baseCase = 0
recCase :: Int -> Int -> Int
recCase n r = n + r
{-
Recursion-only part:
The only implementation details it contains
are about how fact it calling itself
-}
sum :: Int -> Int
sum 0 = baseCase
sum n = let r = sum (n-1)
in recCase n rDo you see how similar the recursion-relevant parts of sum and fact are? They are actually identical! It means
fact and sum have the same recursion structure. The recursion-irrelevant part differ:
the constant baseCase which is 1 in fact but 0 in sum and operation recCase which is n * r in fact but
n + r in sum. Note that if we replace, in each case, occurrences of baseRec and recCase by their definition, we
get back the original functions. Look at the common recursive-relevant part:
def commonRecursiveRelevantPart(n: Int): Int =
if (n == 0) baseCase
else {
val r = commonRecursiveRelevantPart(n-1)
recCase(n, r)
}commonRecursiveRelevantPart :: Int -> Int
commonRecursiveRelevantPart 0 = baseCase
commonRecursiveRelevantPart n = let r = commonRecursiveRelevantPart (n-1)
in recCase n rObviously, for this code to be correct, baseCase and recCase have to be defined. Let’s fix this by taking them
as arguments:
def scheme(baseCase: Int, recCase: (Int, Int) => Int): Int => Int = {
def commonRecursiveRelevantPart(n: Int): Int =
if (n == 0) baseCase
else {
val r = commonRecursiveRelevantPart(n-1)
recCase(n, r)
}
commonRecursiveRelevantPart
}scheme :: Int -> (Int -> Int -> Int) -> Int -> Int
scheme baseCase recCase = commonRecursiveRelevantPart
where
commonRecursiveRelevantPart :: Int -> Int
commonRecursiveRelevantPart 0 = baseCase
commonRecursiveRelevantPart n = let r = commonRecursiveRelevantPart (n-1)
in recCase n rIt is then trivial to define both fact and sum by feeding scheme with corresponding definitions for baseCase and recCase:
def fact: Int => Int = scheme(1, (n: Int, r:Int) => n * r)
def sum : Int => Int = scheme(0, (n: Int, r:Int) => n + r)fact :: Int -> Int
fact = scheme 1 (*)
sum :: Int -> Int
sum = scheme 0 (+)We can now give a first answer to how recursion schemes can be useful. They enable to
to write less code which is both easier and safer. But there is more! Recursive calls, like any
function calls, consume the stack. If there are too many recursive calls (i.e. when n is to big),
there is a risk of stack overflow. Some languages like Scala are smart enough to avoid, in some cases,
this problem by transforming tail-recursive functions into iterative loops.
Unfortunately not all recursive functions are tail-recursive. Writing recursive functions as
iterative loops is not the solution either since it is intricate and error-prone.
Fortunately it is enough to only write the recursion scheme once:
def scheme(baseCase: Int, recCase: (Int, Int) => Int)(n: Int): Int = {
var res = baseCase
var i: Int = 1
while (i <= n) {
res = recCase(i, res)
i += 1
}
res
}scheme :: Int -> (Int -> Int -> Int) -> Int -> Int
scheme baseCase recCase n = aux baseCase 1
where
aux res i = if i <= n
then aux (recCase i res) (i + 1)
else resNote that the scheme is usually simpler to write as it only focuses on recursion, not
business logic. Furthermore one scheme may fit many functions thus reducing the complexity
and bugs in writing business functions. Remember that fact and sum are purposely trivial.
They are just toy example to introduce the subject. In practice you will use much more complex
recursive functions. Once you’ve understood this example, you’ll be able to scale this technique
to any recursive one, however complex it is.
Scaling up!
To be sure we have a good understanding of the techniqe, let’s apply it to the fibonacci function we all love. It is defined on non-negative integers by
$$fib(0) = 1$$$$fib(1) = 1$$$$fib(n+2) = fib(n+1) + fib(n)$$def fib(n: Int): Int =
n match {
case 0 => 1
case 1 => 1
case n =>
val r1 = fib(n-1)
val r2 = fib(n-2)
r1 + r2
}fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = r1 + r2
where
r1 = fib (n - 1)
r2 = fib (n - 2)The function fib does not call itself when n is 0 or 1 but calls itself twice, on n-1 and n-2 otherwise.
So we can, like fact and sum, split fib into two pieces: one containing only recursion-relevant code and the
other one the rest. Once again the split is done by taking recursion-irrelevant code out of the function’s body.
Remember they are many ways to split it up. This one is just one of many sensible way of doing so:
/* Part irrelevant to recursion:
* The real definitions of these variables
* have no impact on how fact is calling itself
*/
val baseCase0: Int = 1
val baseCase1: Int = 1
def recCase(r1: Int, r2: Int): Int = r1 + r2
/* Recursion-only part:
* The only implementation details it contains
* are about how fib it calling itself
*/
def fib(n: Int): Int =
n match {
case 0 => baseCase0
case 1 => baseCase1
case n =>
val r1 = fib(n-1)
val r2 = fib(n-2)
recCase(r1, r2)
}{-
Part irrelevant to recursion:
The real definitions of these variables
Have no impact on how fact is calling itself
-}
baseCase0 :: Int
baseCase0 = 1
baseCase1 :: Int
baseCase1 = 1
recCase :: Int -> Int -> Int
recCase n r = n + r
{-
Recursion-only part:
The only implementation details it contains
are about how fact it calling itself
-}
fib :: Int -> Int
fib 0 = baseCase0
fib 1 = baseCase1
fib n = recCase r1 r2
where
r1 = fib (n - 1)
r2 = fib (n - 2)Which leads to the recursion scheme:
def scheme(baseCase0: Int, baseCase1: Int, recCase: (Int, Int) => Int)(n: Int): Int =
n match {
case 0 => baseCase0
case 1 => baseCase1
case n =>
val r1 = fib(n-1)
val r2 = fib(n-2)
recCase(r1, r2)
}scheme :: Int -> Int -> (Int -> Int -> Int) -> Int -> Int
scheme baseCase0 baseCase1 recCase = aux
where
aux 0 = baseCase0
aux 1 = baseCase1
aux n = recCase r1 r2
where
r1 = aux (n - 1)
r2 = aux (n - 2)It is then trivial to define fib by giving appropriate definition to scheme arguments: baseCase0, baseCase1 and
recCase.
def fib: Int => Int = scheme(1, 1, (r1: Int, r2: Int) => r1 + r2)fib :: Int -> Int
fib = scheme 1 1 (+)Once again this implementation is not optimal as each call of fib can make to 2 recursive calls
which leads to an exponential time complexity. While computing fib(5) is fast, computing fib(1000) may
take much longer. As you already probably guessed, writing the recursion scheme as an iterative loop, which
sadly makes it more intricate, solves the problem:
def scheme(baseCase0: Int, baseCase1: Int, recCase: (Int, Int) => Int)(n: Int): Int =
if (n == 0) baseCase0
else {
var b0 = baseCase0
var b1 = baseCase1
var i = 2
while (i <= n) {
val b2 = recCase(b0, b1)
b0 = b1
b1 = b2
i += 1
}
b1
}scheme :: Int -> Int -> (Int -> Int -> Int) -> Int -> Int
scheme baseCase0 baseCase1 recCase 0 = baseCase0
scheme baseCase0 baseCase1 recCase n = aux baseCase0 baseCase1 2
where
aux b0 b1 i = if i <= n
then aux b1 (recCase b0 b1) (i + 1)
else b1By now you should get a good grasp on what recursion schemes are. But we have
only seen a tiny fraction of how useful they are. It’s about time to consider
the real power of fact, sum and fib’s schemes.
Time to take off!
Previously we defined fact and sum’s schemes as
def scheme(baseCase: Int, recCase: (Int, Int) => Int)(n: Int): Int = {
var res = baseCase
var i: Int = 1
while (i <= n) {
res = recCase(i, res)
i += 1
}
res
}scheme :: Int -> (Int -> Int -> Int) -> Int -> Int
scheme baseCase recCase n = aux baseCase 1
where
aux res i = if i <= n
then aux (recCase i res) (i + 1)
else resI have a small exercise for you: find where this code relies on baseCase to be an Int?
It’s important, take the time to figure it out. The answer is simple: it does not! baseCase can actually be
any of type A! We don’t even have to modify the code (only the type signature):
def scheme[A](baseCase: A, recCase: (Int, A) => A)(n: Int): A = {
var res = baseCase
var i: Int = 1
while (i <= n) {
res = recCase(i, res)
i += 1
}
res
}scheme :: a -> (Int -> a -> a) -> Int -> a
scheme baseCase recCase n = aux baseCase 1
where
aux res i = if i <= n
then aux (recCase i res) (i + 1)
else resNot only can we still define fact (and sum) like above but it makes trivial defining
the functions like list which returns the list of integers between n and 1:
def list: Int => List[Int] = scheme[List[Int]](Nil, (n: Int, r: List[Int]) => n :: r)list :: Int -> [Int]
list = scheme [] (:)Unsurprisingly fib’s recursion scheme can also be generalized without changing a single line of code (only type signature):
def scheme[A](baseCase0: A, baseCase1: A, recCase: (A, A) => A)(n: Int): A =
if (n == 0) baseCase0
else {
var b0 = baseCase0
var b1 = baseCase1
var i = 2
while (i <= n) {
val b2 = recCase(b0, b1)
b0 = b1
b1 = b2
i += 1
}
b1
}scheme :: a -> a -> (a -> a -> a) -> Int -> a
scheme baseCase0 baseCase1 recCase 0 = baseCase0
scheme baseCase0 baseCase1 recCase n = aux baseCase0 baseCase1 2
where
aux b0 b1 i = if i <= n
then aux b1 (recCase b0 b1) (i + 1)
else b1While fact’s scheme is related to lists, fib’s one is related to trees:
sealed abstract class Tree[+A]
final case class Leaf[+A](value: A) extends Tree[A]
final case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A]
def tree: Int => Tree[Boolean] =
scheme(
Leaf(false),
Leaf(true),
(r1: Tree[Boolean], r2: Tree[Boolean]) => Node(r1,r2)
)data Tree a = Leaf a | Node (Tree a) (Tree a)
tree :: Int -> Tree Bool
tree = scheme (Leaf False) (Leaf True) NodeI have few real exercises for you this time:
- find in your production code several spots where this scheme could be useful.
- write schemes, as general as possible, for at least 5 recursive functions in our production code.
Obviously I won’t check you did the exercises but you should really do them. Reading is not sufficient to develop your understanding of the technique, you need to experiment! Try things, play with these notions until it clicks. Learning recursion schemes is like going on expeditions: preparation time may seem the easier part but if you did not prepare well enough, you’ll get lost.
Yeah! Buzzwords!
As we have seen, fact’s scheme takes 2 arguments:
def scheme[A](baseCase: A, recCase: (Int, A) => A): Int => Ascheme :: a -> (Int -> a -> a) -> Int -> aWhile this definition is perfectly ok, we can regroup these argument in any structure that can hold both values like a pair, an interface or a trait:
trait FactorialSchemeArguments[A] {
val baseCase: A
def recCase(n: Int, r: A): A
}
def scheme[A](arguments: FactorialSchemeArguments[A]): Int => Aclass FactorialSchemeArguments a where
baseCase :: a
recCase :: Int -> a -> a
scheme :: FactorialSchemeArguments a => Int -> aNote that scheme is still the same: it still takes the same two arguments.
But even if the code didn’t change, this transformation makes us see scheme
from a different perspective. It shows scheme as a functions transforming
an integer to an A provided that we give some structure to A: a constant
baseCase and an operation recCase. Let’s give this structure and the scheme
names: i decide to call the structure a AkolovioaAlgebra (don’t look for
it in literature, i just coined the term) and the scheme an akolovioaMorphism:
trait AkolovioaAlgebra[A] {
val initial: A
def action(n: Int, r: A): A
}
def akolovioaMorphism[A: AkolovioaAlgebra]: Int => Aclass AkolovioaAlgebra a where
initial :: a
action :: Int -> a -> a
akolovioaMorphism :: AkolovioaAlgebra a => Int -> aThis looks smart, doesn’t it? 😉 It is actually very close to a very common structure in programming! Will you find which one? Obviously the same can be done for fibonacci’s scheme. As an exercise, apply this technique to fibonacci’s scheme and give them pretty names.
Where to go from here?
As you know this is not the end of the story: the subject is closely related to pervasive notions such as (co)algebras, inductive types, categories, initial-objects, fixed-points, algebraic data types, etc. Whichever next subject you choose to dive into, the approach this article follows, i.e. experimenting on toy examples, really helps developing a solid understanding. I want you to realize each definition you read in books, articles, talks, etc is the result of people experimenting. The common trap in this field is looking at definitions as sacred pieces of unquestionable truth no mortal can see through. It is actually the exact opposite! Science is by essence experimentation. This is by investigating and trying things you end up figuring out how things work. But, like in science, for your investigation to be productive your tests need to be done in a controlled environment with as few variables as possible so that it is easy for you to see what’s going on. That’s why toy examples are so important: they contain the essence of what makes things work without all the noise real examples have.
Take care and spread recursion schemes around 😉