Recursion schemes fundamentals
by Oli Makhasoeva
- •
- January 02, 2020
- •
- scala• recursion schemes• skeuomorph
- |
- 43 minutes to read.

Motivation
Recursive structures appear in many problems, from databases to machine learning, and writing functions to operate over them is not always a simple task. As functional programming tries to abstract as many things as possible, it offers a way to decouple a recursion from the implementation of business rules.
Overview
We will start our discussion with the recursive data structure that everyone uses in every project!
I am talking about a list. We are going to copy-paste two functions—foldRight
and unfold
—from the Scala standard library.
foldRight
applies a binary operator to all elements of a list and a start value, going right to left; it returns a start value if a list is empty.
unfold
produces a collection that uses a function to produce elements and update an internal state.
How do these functions relate to recursion schemes? They are, in fact, mere special cases of more general functions that are named cata
and ana
! To see convincing proof of this, please follow the steps of refactoring we show below.
foldRight
and unfold
definitions
As a starting point, let’s use the definitions of foldRight
and unfold
(op:(A,B)=>B):B)
def foldRight[B](z: B)(op: (A, B) => B): B
def unfold[A, S](init: S)(f: (S) => Option[(A, S)]): List[A]
We need to make some changes to the foldRight
before we get started. It is defined as a function of List[A]
; the following definition is equivalent:
def foldRight[A, B](init: List[A])(z: B)(op: (A, B) => B): B
We just passed a list as a parameter.
foldRight
and unfold
are duals of each other
If you squint hard enough, you will notice that foldRight
and unfold
are duals of each other. It would be instrumental to rename type parameters to make the duality more obvious later.
def foldRight[E, B](init: List[E])(z: B)(op: (E, B) => B): B
def unfold[E, A](init: A)(f: (A) => Option[(E, A)]): List[E]
Here, foldRight
takes a list of E and produces a value, whereas unfold
does the opposite, i.e., it takes a value and produces a list of E.
foldRight
and unfold
implementations
To implement these functions, we are going to use the close-up technique, i.e., we are going to stare at the signatures of the functions until we have an idea for using what we are given step by step. That is possible because we are talking about FP, which means all our functions are pure and we don’t have anything but the input to produce the output.
foldRight
implementation
First, let’s take a look at foldRight
’s parameters.
init: List[A]
z: B
op: (A, B) => B
The return type of the foldRight
is B
, and considering the input, we could, for instance, always return z
.
def foldRight[B](init: List[A])(z: B)(op: (A, B) => B): B = z
Even though it compiles (always a good sign!), our function doesn’t do anything helpful in that case.
At second glance, we notice that we could pattern match on the init
.
def foldRight[B](init: List[A])(z: B)(op: (A, B) => B): B =
init match {
case Nil => ???
case head :: tail => ???
}
The first case case Nil =>
is suggesting that we don’t have a value to apply to op
, so the only thing that we could do is return the z
. But what do we do with the second case where we have the head
and the tail
?
We could mistakenly return op(head, z)
and drop the tail
since it is not type of B
. Unfortunately, the compiler isn’t able to warn us if we forget the recursive call altogether. For example, if we return z
in both cases, for Nil
and head :: tail
.
So we need to think harder; what can we do with the tail
in order to make it be type of B
?
Right, we can recursively call foldRight
on it!
def foldRight[A, B](init: List[A])(z: B)(op: (A, B) => B): B =
init match {
case Nil => z
case head :: tail => op(head, foldRight(tail)(z)(op))
Example
To check the behavior of the function, let’s introduce the prodOp
function, which multiplies two integers.
val prodOp: (Int, Int) => Int = _ * _
foldRight(1 :: 10 :: 20 :: Nil)(1)(prodOp) // 200: Int
Let’s take a closer look at the order of operations.
::
adds an element at the beginning of the list. Let’s rearrange it so that the order in which it executes is clearer.
::(1,
::(10,
::(20,
Nil)))
In this trace, we start with a Nil
, and then prepend other elements step by step. Similarly, we start our computation at the very bottom of the data structure, and then, as we track back, we do evaluation:
prodOp(1,
prodOp(10,
prodOp(20,
1)))
prodOp(1,
prodOp(10,
20))
prodOp(1,
200)
200
Note that foldRight
effectively replaces every ::
with prodOp
.
Implementation of unfold
The implementation of unfold
has similar steps, and it would be a good exercise for you to implement it on your own.
Implementation of unfold
def unfold[E, A](init: A)(f: (A) => Option[(E, A)]): List[E] =
f(init) match {
case None => Nil
case Some((e, a)) => e :: unfold(a)(f)
}
Example
Let’s use a function that generates a list of descending integers starting with the given integer.
val rangeOp: Int => Option[(Int, Int)] =
v => {
if (v <= 0) None
else Some((v, v - 1))
}
unfold(10)(rangeOp) // List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1): List[Int]
Like foldRight
, unfold
goes down in a computation step by step until it can compute the next integer, and then it combines the results into a list.
Changing foldRight
to show the duality better
def foldRight[E, B](init: List[E])(z: B)(op: (E, B) => B): B
def unfold[E, A](init: A)(f: (A) => Option[(E, A)]): List[E]
It’s easy to see that foldRight
takes more parameters than unfold
. Can we do anything about it?
We could think of z
, which gives us a value of type B
, as a function from Unit
to B
.
z ---------> B
() ----z----> B
the op
function also returns a value of B:
(E, B) ----op----> B
We could combine them together, taking a unit or a tuple of (E, B)
, to think of Either
as a representation of such a type in Scala.
Either[(), (E, B)] -----f----> B
Moreover, we could go further and replace Either
with Option
, because it doesn’t make much sense to keep Either
with a unit on the left side, being that Either[Unit, A]
is isomorphic to Option[A]
.
Consequently, the next two definitions are equivalent:
def foldRight[E, B](init: List[E])(z: B)(op: (E, B) => B): B
def foldRight[E, B](init: List[E])(f: Option[(E, B)] => B): B
Let’s reimplement foldRight
:
def foldRight[E, B](init: List[E])(f: Option[(E, B)] => B): B =
init match {
case Nil => f(None)
case head :: tail => f(Some((head, foldRight(tail)(f))))
}
Nothing has changed dramatically except that we call our function f
in both cases now.
We also need to massage the example to satisfy a new signature.
val prodf: Option[(Int, Int)] => Int = {
case None => 1 // Hello, `z`!
case Some((x, y)) => x * y
}
And apply it to our function.
foldRight(1 :: 10 :: 20 :: Nil)(prodf) // still 200: Int
Refactoring 1: pass fewer parameters
We are moving in the right direction, and now is an excellent time to revisit our functions.
What problems do we have?
Unfortunately, in both cases, we are passing our initial values and a function f
on every step of the recursion.
def foldRight[E, B](init: List[E])(f: Option[(E, B)] => B): B =
init match {
case Nil => f(None)
case head :: tail => f(Some((head, foldRight(tail)(f)))) // here `tail` and `f` are passed around
}
def unfold[E, A](init: A)(f: (A) => Option[(E, A)]): List[E] =
f(init) match {
case None => Nil
case Some((e, a)) => e :: unfold(a)(f) // here `a` and `f` are passed around
}
The second concern is that we have curried paramers and, for better readability, we would like to avoid it.
We could get rid of both problems by (1) returning a function instead of a value and (2) introducing a nested function:
(1):
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B
def unfold[E, A](f: (A) => Option[(E, A)]): A => List[E]
Notice, there is a striking resemblance between these two signatures! They mirror each other:
Option[(E, B)] => B => List[E] => B
A => Option[(E, A)] => A => List[E]
Because the function we need to return is recursive, we have to build it using an auxiliary variable.
(2):
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B = {
lazy val kernel: List[E] => B = _ match {
case Nil => f(None)
case head :: tail => f(Some((head, kernel(tail))))
}
kernel
Implementation of unfold
def unfold[E, A](f: (A) => Option[(E, A)]): A => List[E] = {
lazy val kernel: A => List[E] = f(_) match {
case None => Nil
case Some((e, a)) => e :: kernel(a)
}
kernel
That works, but is there a way to handle it without insufficient lazy val? Yes, we could also do it using an anonymous nested function.
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B =
new (List[E] => B) { kernel =>
def apply(init: List[E]): B = init match {
case Nil => f(None)
case head :: tail => f(Some((head, kernel(tail))))
}
}
You are strongly encouraged to venture out and try to write an implementation for the unfold
on your own!
Implementation of unfold
def unfold[E, A](f: (A) => Option[(E, A)]): A => List[E] =
new (A => List[E]) { kernel =>
def apply(init: A): List[E] = f(init) match {
case None => Nil
case Some((e, a)) => e :: kernel(a)
}
}
Refactoring 2: factor out the data structure
So far, our implementation is tightly coupled to a list—our data structure. While we cleaned up the code a bit, we didn’t generalize our functions.
To better understand where the List
type appears, let’s
break down our function into steps. The point here is to illustrate which steps depend on the List
and eliminate them.
Let’s start with foldRight
. The first step it does is pattern matching on a list.
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B =
new (List[E] => B) { kernel =>
def apply(init: List[E]): B = init match {
case Nil => ???
case head :: tail => ???
}
}
We can think of it as unpacking our data structure, or projecting a data structure.
It is proceeding with a recursive call in the case the list is not empty (see kernel
call).
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B =
new (List[E] => B) { kernel =>
def apply(init: List[E]): B = init match {
case Nil => ???
case head :: tail => ??? kernel(tail)
}
}
Finally, we are computing the result using f
.
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B =
new (List[E] => B) { kernel =>
def apply(init: List[E]): B = init match {
case Nil => f(???)
case head :: tail => f(???)
}
}
To summarize it, let’s name the steps:
- Unpacking/projecting data structure
- Recursion: call self for the nested structure
- Computation
How can we reimplement our foldRight
? The idea is simple. Instead of having one function apply
, we will introduce three new functions: one per each step.
This is a slight shift in perspective:
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B = {
new (List[E] => B) { kernel =>
def step1: ??? => ??? // unpack
def step2: ??? => ??? // recurse
def step3: ??? => ??? // compute
def apply(init: List[E]): B = step3(step2(step1(init)))
}
}
As is already apparent, step1
should take List[E]
as a parameter. Given that we can only end up with a Nil
or a head
and a tail
, the most general possible return type could be Option[E, List[E]]
. It forces us to accept it as a parameter for step2
.
It should also be noted that step3
is essentially f
and, therefore, we can state its signature as def step3: Option[(E, B)] => B
. step3
’s parameter certanly gives us the returning type of step2
. Let’s write down functions with the required signatures:
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B = {
new (List[E] => B) { kernel =>
def step1: List[E] => Option[(E, List[E])] // unpack
def step2: Option[(E, List[E])] => Option[(E, B)] // recurse
def step3: Option[(E, B)] => B // compute
def apply(init: List[E]): B = step3(step2(step1(init)))
}
}
It’s now considerably simple to write all functions:
def step1: List[E] => Option[(E, List[E])] = {
_ match {
case Nil => None
case head :: tail => Some((head, tail))
}
}
def step2: Option[(E, List[E])] => Option[(E, B)] = {
_ match {
case None => None
case Some((e, le)) => Some((e, kernel(le)))
}
}
def step3: Option[(E, B)] => B = f
We do not benefit from having step3
because it is identical to f
, so we can remove it and use f
directly instead.
Our goal is to get you accustomed to working with more abstract structures, and develop the ability to recognize them.
In the next code snippet, we’d like to introduce type aliases F[P]
and S
to decrease a distraction and focus on an abstraction.
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B = {
type F[P] = Option[(E, P)]
type S = List[E]
new (S => B) { kernel =>
def step1: S => F[S] = {
_ match {
case Nil => None
case head :: tail => Some((head, tail))
}
}
def step2: F[S] => F[B] = {
_ match {
case None => None
case Some((e, le)) => Some((e, kernel(le)))
}
}
def apply(init: S): B = f(step2(step1(init)))
}
}
The step2
resembles a Functor
; indeed, it’s almost like mapping over an Option
. To be precise, it’s mapping over the second parameter of the tuple that is wrapped in an Option
. Leveraging some functionality from cats
library, we can write quite generic code!
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B = {
type F[P] = Option[(E, P)]
type S = List[E]
implicit val F = Functor[Option].compose[(E, ?)]
new (S => B) { kernel =>
def step1: S => F[S] = {
_ match {
case Nil => None
case head :: tail => Some((head, tail))
}
}
def step2: F[S] => F[B] = _.fmap(kernel)
def apply(init: S): B = f(step2(step1(init))) // or f(step1(init).fmap(kernel)), if we inline the step2
}
}
Now we can claim that the only remaining dependency on the List[E]
is our step1
function. Thus, if we have it outside of the foldRight
, it will make it as abstract as possible. Let’s refactor this further and move everything outside.
The first thing to refactor is our type F[P] = Option[(E, P)]
.
We can use the following pattern (also known as a functor-pattern):
type ListF[A, B] = Option[(A, B)]
.
The second step would be to get rid of List[E]
and E
entirely in the signature and leave S
as a type parameter of foldRight
to represent our data structure.
The functor restriction also migrates to the type parameters.
Now we can factor out the step1
and call it project
, as it is projecting our data structure:
type ListF[A, B] = Option[(A, B)]
implicit def functor[A]: Functor[ListF[A, ?]] = Functor[Option].compose[(A, ?)]
def projectList[E]: List[E] => ListF[E, List[E]] = {
_ match {
case Nil => None
case head :: tail => Some((head, tail))
}
}
def foldRight[F[_]: Functor, S, B](f: F[B] => B)(project: S => F[S]): S => B = {
new (S => B) { kernel =>
def apply(init: S): B = f(project(init).fmap(kernel))
}
}
To help the Scala compiler a little bit, we need to change the types of the prodF
function explicitly.
val prodFlist: ListF[Int, Int] => Int = {
_ match {
case None => 1
case Some((x, y)) => x * y
}
}
We are ready to examine our new brand foldRight
:
foldRight(prodFlist)(projectList).apply(1 :: 10 :: 20 :: Nil) // 200: Int
The result, of course, stays the same. But look how more abstract it is now!
We should do exactly the same thing with the unfold
, right?
Here are a few hints for solving this exercise for unfold
:
- computation
- recursion
- packing/embedding into a data structure
Implementation of unfold
def embedList[E]: ListF[E, List[E]] => List[E] = {
_ match {
case None => Nil
case Some((e, le)) => e :: le
}
}
val range: Int => ListF[Int, Int] =
v => if (v <= 0) None else Some((v, v - 1))
def unfold[F[_]: Functor, S, A](f: (A) => F[A])(embed: F[S] => S): A => S =
new (A => S) { kernel =>
def apply(init: A): S = embed(f(init).fmap(kernel))
}
unfold(range)(embedList).apply(10) // List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1): List[Int]
Refactoring 3: here comes cata and ana
Whenever you generalize functions like this, take a critical look at your generalized function when you have finished. Although the function may have been motivated by some specific use case(List
), the signature and implementation may have a more general meaning. In this case, foldRight
and unfold
are perhaps no longer the most appropriate names for those functions. These functions, which often come up in recursion schemes libraries, could be called cata
and ana
.
def cata[F[_]: Functor, S, B](f: F[B] => B)(project: S => F[S]): S => B =
new (S => B) { kernel =>
def apply(init: S): B = f(project(init).fmap(kernel))
}
def ana[F[_]: Functor, S, A](f: (A) => F[A])(embed: F[S] => S): A => S =
new (A => S) { kernel =>
def apply(init: A): S = embed(f(init).fmap(kernel))
}
cata(prodFlist)(projectList).apply(1 :: 10 :: 20 :: Nil) // 200: Int
ana(range)(embedList).apply(10) // List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1): List[Int]
F[A] => A
is often called Algebra
in the category theory/recursion schemes literature, and its dual A => F[A]
is called Coalgebra
.
Let’s introduce aliases for these types:
type Algebra[F[_], A] = F[A] => A
type Coalgebra[F[_], A] = A => F[A]
Cata and Ana with Algebra & Coalgebra
val productOpA: Algebra[ListF[Int, ?], Int] = {
case None => 1
case Some((x, y)) => x * y
}
val rangeOpC: Coalgebra[ListF[Int, ?], Int] =
n => if (n <= 0) None else Some((n, n - 1))
def cata[F[_]: Functor, S, B](algebra: Algebra[F, B])(project: Coalgebra[F, S]): S => B =
new (S => B) { kernel =>
def apply(input: S): B =
algebra(project(input).fmap(kernel))
}
def ana[F[_]: Functor, S, A](coalgebra: Coalgebra[F, A])(embed: Algebra[F, S]): A => S =
new (A => S) { kernel =>
def apply(init: A): S =
embed(coalgebra(init).fmap(kernel))
}
def projectListC[A]: Coalgebra[ListF[A, ?], List[A]] = {
case Nil => None
case head :: tail => Some((head, tail))
}
def embedListA[A]: Algebra[ListF[A, ?], List[A]] = {
case None => Nil
case Some((head, tail)) => head :: tail
}
cata(productOpA)(projectListC).apply(1 :: 10 :: 20 :: Nil) // 200: Int
ana(rangeOpC)(embedListA).apply(10) // List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1): List[Int]
Use in practice: Skeuomorph
Throughout this post, we’ve used these two examples:
{
val rangeList: Int => List[Int] = ana(rangeOpC)(embedListA)
rangeList(10)
val productList: List[Int] => Int = cata(productOpA)(projectListC)
productList(1 :: 10 :: 20 :: Nil)
}
And if you look at the signatures of cata
and ana
, they look exactly the same, and we can compose them! We can come up with really clean and fun factorial implementation:
{
val rangeList: Int => List[Int] = ana(rangeOpC)(embedListA)
val productList: List[Int] => Int = cata(productOpA)(projectListC)
val factorial: Int => Int = productList compose rangeList
factorial(4)
}
This operation, unfolding a data structure from a seed value (coalgebra), then computing a final result by folding over the data structure (algebra),
is called a hylomorphism (or shorter, hylo
).
def hylo[F[_]: Functor, A, B](algebra: Algebra[F, B], coalgebra: Coalgebra[F, A]): A => B =
new (A => B) { kernel =>
def apply(init: A): B =
algebra(coalgebra(init).fmap(kernel))
}
{
val factorial: Int => Int = hylo(productOpA, rangeOpC)
factorial(4)
}
The canonical example is the factorial function;
however, hylo
, ana
, and cata
are far more useful than another fancy method to compute factorial.
Think of any operation that needs to build, and then collapse, a data structure. One such operation that comes to mind, and that you may encounter in production, is the transformation of different schemas in Scala.
At 47 Degrees, we open-sourced a library called Skeuomorph
, which solves this problem. Let’s discuss how it does it briefly.
Suppose we need to parse a .proto
file and convert it to our internal representation.
Parser as an anamorphism in Skeuomorph
First things first, we need to write a pattern functor for our structure. It can look similar to the following:
sealed trait ProtobufF[A]
object ProtobufF {
final case class TUint64[A]() extends ProtobufF[A]
final case class TBool[A]() extends ProtobufF[A]
final case class TString[A]() extends ProtobufF[A]
final case class TNamedType[A](name: String) extends ProtobufF[A]
final case class TRepeated[A](value: A) extends ProtobufF[A]
final case class TMessage[A](name: String, fields: List[FieldF[A]]) extends ProtobufF[A]
Please, keep in mind, this is a simplified version.
Once we have the pattern functor, we can complete Coalgebra
:
import higherkindness.droste.Coalgebra
def fromFieldTypeCoalgebra(): Coalgebra[ProtobufF, Type] = Coalgebra {
case Type.TYPE_BOOL => TBool()
case Type.TYPE_STRING => TString()
case Type.TYPE_UINT64 => TUint64()
case Type.TYPE_MESSAGE => ???
???
}
Here, on the left-hand side, we can see native protobuf types that correspond to ProtobufF
types on the right-hand side. Therefore, our program now knows how to map types.
As we mentioned before, cata
and ana
are implemented in Droste
library. Let’s borrow scheme.ana
and Embed
from it to implement the parser:
def fromFieldType[A]()(fieldType: Type)(coalg: Coalgebra[ProtobufF, Type])(implicit A: Embed[ProtobufF, A]): A =
scheme.ana(coalg).apply(fieldType)
Transformations with cata
in Skeuomorph
We know we need to have an internal representation of schema:
object SchemaF {
final case class Field[A](name: String, tpe: A)
final case class TLong[A]() extends SchemaF[A]
final case class TBoolean[A]() extends SchemaF[A]
final case class TString[A]() extends SchemaF[A]
final case class TNamedType[A](name: String) extends SchemaF[A]
final case class TList[A](value: A) extends SchemaF[A]
final case class TProduct[A](name: String, fields: List[Field[A]]) extends SchemaF[A]
}
We introduced a new type here, SchemaF. Now we have to determine how to transform from the pattern functor ProtobuF
to that type:
/**
* transform Protobuf schema into SchemaF
*/
def transformProto[A](implicit A: Embed[SchemaF, A]): Trans[ProtobufF, SchemaF, A] = Trans {
case ProtobufF.TUint64() => TLong()
,,,
case ProtobufF.TRepeated(value) => TList(value)
case ProtobufF.TMessage(name, fields) => TProduct(name, fields.map(f => Field(f.name, f.tpe)))
}
And cata
will traverse through the data structure and return the result in SchemaF terms.
scheme.cata(transformProto[U].algebra)
We could implement a parser or a transformation for any other types following the same simple steps, or even more, we can transform from any kind of protocol to any other using SchemaF as an intermediate step! In future blog posts, we will cover the topic in more detail. To play more with it, we invite you to check out the Ersatz project on our Github page. There, you can run an example and see the results. Ersatz is a simplified version of Skeuomorph; experienced readers should proceed to it directly.
Summary
Recursion schemes is a compelling technique that separates the business logic - code that everyone wants to focus on - from the recursion pain: By decoupling how a function recurses over data from what the function actually does, we reduce cognitive overhead and can focus entirely on the core behavior of our recursive functions. Recursion schemes are abstract from data structures. It doesn’t matter whether we work with lists, trees, graphs, database schemes, protocol buffers, or avro. They allow traversing these different structures in the same way.
Acknowledgments
Huge thanks to Andy Scott for his help in preparation and valuable feedback.