This article's code snippets come from a runnable example! To run it, execute the following commands:
git clone https://github.com/anatoliykmetyuk/anatoliykmetyuk.github.io.git akmetiuk
cd akmetiuk
git checkout thera
cd src/code/matryoshka-intro
sbt run
Recursion is the GOTO of functional programming - Erik Meijer^{1}
In our daily programming life, we encounter recursive data structures on a regular basis. The best-known examples include linked lists and trees. Often working with such data structures we have a need to evaluate (collapse) them to a value. For example:
2 * 3 + 3
, we can expect it to produce a tree out of that expression - Add(Mult(Num(2), Num(3)), Num(3))
. Such trees often need to be evaluated by actually performing these mathematical operations.
Zero
is such a zero number, and Succ(x)
constructs a natural number following x
, Succ(Succ(Succ(Zero)))
can represent 3
. This is also a recursive structure, and the simplest operation you want to do on it is to actually evaluate it to an Int
: Nat => Int
.
In this article, we shall see how all of these examples involve recursion. Don't Repeat Yourself (DRY) is one of the fundamental principles of programming - so, if we repeat recursion from example to example, we should abstract it away. We shall see how to do that.
But first, let us set the foundation by doing all of the above examples in code.
Here is how an implementation of natural numbers might look like:
// Nat
sealed trait Nat
case class Succ(previous: Nat) extends Nat
case object Zero extends Nat
And here is a visualization of the number 3 represented this way:
This would correspond to Succ(Succ(Succ(Zero)))
. Note the recursive nature of this structure: a smaller substructure of the same type is present in every structure (except the terminal one, Zero
).
Now, let us see how to evaluate a natural number to an Int
. In order to do this for an arbitrary Succ(x)
, we need to evaluate x
and add 1 to the result. Zero
should evaluate to 0:
// Nat to Int
def natToInt(n: Nat): Int = n match {
case Succ(x) => 1 + natToInt(x)
case Zero => 0
}
val nat = Succ(Succ(Succ(Zero)))
val natRes: Int = natToInt(nat)
println(natRes) // 3
Now let us see how to implement a list as a recursive structure:
// List
sealed trait IntList
case class Cons(head: Int, tail: IntList) extends IntList
case object Empty extends IntList
A list is either an empty list or a recursive structure that has a head
element and a tail
- a sublist representing all the elements following the head
. For simplicity, we only consider lists of Int
.
Here is how a list of 1, 2, 3
looks like:
In order to find the sum of all the elements in a list, we should add its head
to the sum of all the elements of its tail
. If the list is Empty
, the result of the summation is 0:
// Sum a list of ints
def sumList(l: IntList): Int = l match {
case Cons(head, tail) => head + sumList(tail)
case Empty => 0
}
val lst = Cons(1, Cons(2, Cons(3, Empty)))
val listRes: Int = sumList(lst)
println(listRes) // 6
Finally, this is a definition of a tree aiming to represent mathematical expression:
// Expr
sealed trait Expr
case class Add (expr1 : Expr, expr2: Expr) extends Expr
case class Mult(expr1 : Expr, expr2: Expr) extends Expr
case class Num (literal: Int ) extends Expr
We have two node types for the summation and the multiplication, and one leaf type for the numbers.
Here is how an expression 2 * 3 + 3
looks like:
How do we evaluate it? If it is a node representing a mathematical operation, first we need to evaluate its children and then do an operation represented by this node. If it is a leaf - a number - it just evaluates that number:
// Evaluate an expression
def eval(e: Expr): Int = e match {
case Add (x1, x2) => eval(x1) + eval(x2)
case Mult(x1, x2) => eval(x1) * eval(x2)
case Num (x) => x
}
val expr = Add(Mult(Num(2), Num(3)), Num(3))
val exprRes: Int = eval(expr)
println(exprRes) // 9
Intuitively, every example above is similar. All of them involve a recursive structure that is collapsed from the "bottom" (the terminal element with no child substructures) to the "top" (the root structure). What is in common between the natToInt
, sumList
and eval
functions? Can we abstract away these common elements, so that every one of these functions can be expressed in the same terms?
natToInt
is called recursively on previous
in order to evaluate Succ(previous)
.
sumList(Cons(head, tail))
, head
is a part of the parent structure. tail
is a substructure that is evaluated recursively via sumList(tail)
and then combined with that head
via addition.
eval
of either Add
or Mult
, we first need to call eval
on the child expressions of these nodes, and then combine them depending on the parent structure - if it is Add
, we do addition, if Mult
- multiplication.
A better way to look at it is as if we were replacing the substructures by their evaluations and then evaluating the resulting structure.
For example, when evaluating a Nat
depicted by the diagram above, the next step of its evaluation would look as follows:
Effectively, we have Succ(previous = 2)
, which is then collapsed into 1 + 2
== 3
. However, previous
is supposed to be a Nat
, not an Int
. In order to be able to write the above statement, we can allow the substructure to have an arbitrary type: SuccA
.
Similarly, the next step for the IntList
depicted above will be:
This is effectively a ConsInt
(again, notice how we introduce a type parameter for the substructure). After that, the head
is added to the new tail
, resulting in 6
Finally, for the Expr
above, the next step is to evaluate both of its two substructures:
This is an AddInt
, and the next step is to collapse it by doing 6 + 3
.
We are dealing with a structure-preserving transformation here. These kind of transformations are well understood in terms of functors.
If we redefine our recursive structures such that they are parameterized by the type of their substructure, their types will have a form F[A]
and we will be able to define functor instances for them.
Ordinarily, A
in these F[A]
is another F[_]
(a substructure, reflecting the recursive nature of the parent structure) or Nothing
(for terminal elements that do not have substructures). In our examples, we first do a map
, turning F[A]
into F[B]
, where B
is the type we are evaluating the structure into (in all our examples, B
is Int
). Next, given F[B]
, we collapse it into a B
. A function F[B] => B
is called an Algebra^{2}^{3}.
Now let us see how this theory can be applied in practice.
In all our data structures, we need to specify the type of the substructures as a type parameter, so that we can then evaluate these substructures in a way that preserves the parent structure, via map
.
The new definitions can go as follows:
// Nat
sealed trait Nat [+A]
case class Succ[ A](previous: A) extends Nat[A ]
case object Zero extends Nat[Nothing]
// List
sealed trait IntList[+A]
case class Cons [ A](head: Int, tail: A) extends IntList[A]
case object Empty extends IntList[Nothing]
// Expr
sealed trait Expr[+A]
case class Add [ A](expr1 : A, expr2: A) extends Expr[A ]
case class Mult[ A](expr1 : A, expr2: A) extends Expr[A ]
case class Num (literal: Int ) extends Expr[Nothing]
If we want to use map
on these data structures, they need functor instances. The definitions below are straightforward (do not forget to import scalaz., Scalaz.
, which is needed to bring functors in scope):
// Functors
implicit val natFunct: Functor[Nat] = new Functor[Nat] {
def map[A, B](fa: Nat[A])(f: A => B): Nat[B] = fa match {
case Succ(x) => Succ(f(x))
case Zero => Zero
}
}
implicit val intListFunct: Functor[IntList] = new Functor[IntList] {
def map[A, B](fa: IntList[A])(f: A => B): IntList[B] = fa match {
case Cons(head, tail) => Cons(head, f(tail))
case Empty => Empty
}
}
implicit val exprFunct: Functor[Expr] = new Functor[Expr] {
def map[A, B](fa: Expr[A])(f: A => B): Expr[B] = fa match {
case Add (x1, x2) => Add (f(x1), f(x2))
case Mult(x1, x2) => Mult(f(x1), f(x2))
case x @ Num (_ ) => x
}
}
As discussed above, all we need to collapse a recursive structure is to map its substructures by the collapse function and then evaluate the resulting structure via an algebra. This recursion scheme is called a catamorphism^{4}. Let us try to define it:
// Catamorphism draft
// WARNING: DOES NOT COMPILE
// def cata[F[_]: Functor, T, A](structure: F[T])(algebra: F[A] => A): A =
// algebra( structure.map(cata(_)(algebra)) )
There is one problem with this code, however. In a recursive structure, T
is supposed to be of the same type as F[T]
by definition. Or else we will not be able to map it by cata
as above, since cata
will need a Functor[T]
. In other words, F[T] == T
. If so, we should also be able to write structure: T
instead of structure: F[T]
in the signature. Obviously, we can not have that in Scala, so what do we do?
A fixed point of a function f(_)
is a value x
such that f(x) == x
. We can think of a higher-order function fix
that computes a fixed point of its argument: fix(f) == x
such that f(x) == x
. By extension, fix(f) == f(fix(f))
holds.
What if we bring the same ideas to the type theory? By analogy, a fixed-point type of a higher-kinded type F[_]
is some type T
such that F[T] == T
- precisely what we need. We can also have a type Fix[F[_]]
, such that Fix[F] == F[Fix[F]]
.
Fixed-point types are interesting, because they can represent a recursive structure of any desired depth as a single type:
Fix[F] == F[Fix[F]] == F[F[Fix[F]]] == ...
I am not aware of a way you can define Fix[F[_]]
so that the above equality holds - the compiler will think F[T] != T
for any F
and T
, as far as I know.
It is possible to think of a workaround, though. In our cata
definition above, we need to know that F[T] == T
so that we can treat T
as if it was F[T]
. So in practice, we do not need to convince the compiler in that equality - a simple function T => F[T]
is enough.
We can emulate the fixed-point type computation as in the theory above as follows:
// Fixed point type
case class Fix[F[_]](unfix: F[Fix[F]])
So we just wrap an F[_]
in this case class. Fix[F] => F[Fix[F]]
can be defined as simply fix => fix.unfix
.
Now we can define the catamorphism on a fixed-point type of a structure F
as follows:
// Catamorphism
def cata[F[_]: Functor, A](structure: Fix[F])(algebra: F[A] => A): A =
algebra(structure.unfix.map(cata(_)(algebra)))
cata
Now we can use the new cata
to define our examples:
// Nat to Int
def natToInt(n: Fix[Nat]): Int = cata[Nat, Int](n) {
case Succ(x) => 1 + x
case Zero => 0
}
val nat: Fix[Nat] =
Fix(Succ( // 3
Fix(Succ( // 2
Fix(Succ( // 1
Fix[Nat](Zero) // 0
))
))
))
val natRes = natToInt(nat)
println(natRes) // 3
// Sum a list of ints
def sumList(l: Fix[IntList]): Int = cata[IntList, Int](l) {
case Cons(head, tail) => head + tail
case Empty => 0
}
val lst: Fix[IntList] =
Fix(Cons(1,
Fix(Cons(2,
Fix(Cons(3,
Fix[IntList](Empty)
))
))
))
val listRes = sumList(lst)
println(listRes) // 6
// Evaluate an expression
def eval(e: Fix[Expr]): Int = cata[Expr, Int](e) {
case Add (x1, x2) => x1 + x2
case Mult(x1, x2) => x1 * x2
case Num (x) => x
}
val expr: Fix[Expr] =
Fix(Add(
Fix(Mult(
Fix[Expr](Num(2)),
Fix[Expr](Num(3))
)),
Fix[Expr](Num(3))
))
val exprRes = eval(expr)
println(exprRes) // 9
First thing that catches the eye, probably, is how we need to embed every layer of the recursive structures into Fix
. This is cumbersome, but fine as for the proof of concept.
Notice how all of the examples are now expressed in terms of one function - cata
. We have successfully abstracted the common parts of the recursive structure collapse task.
Also, notice how we have gotten rid of the recursive calls in all of our examples. The recursion is now abstracted away in cata
, so that the user does not need to deal with it directly.
Catamorphisms are not the only recursion scheme out there. Many more exist. And, of course, you do not need to implement them from scratch. Matryoshka is a library that specializes on implementing recursion schemes on fixed-point types of recursive structures.
The library is centered around the notion of the fixed-point types. In the diagram above, the core type classes are marked with blue "T", and their companion objects - with green "O". These type classes describe what it means for an arbitrary type T
to be a fixed-point type.
The Based[T]
type class captures the idea that a type T
must "know" the type Base[_]
, for which (supposedly) Base[T] == T
. Supposedly, since there's nothing in Based
whatsoever to suggest that equality.
Recursive[T]
has a single abstract method, project
, and a whole lot of methods specifying various schemes of recursion you can run on T
. Our cata
is among them. But obviously project
is of the most interest, since it is the only abstract method and hence its implementation sheds light on what it means for a type T
to be Recursive
.
project
can be interpreted as T => Base[T]
. In the section on practical applications of the fixed-point type we already discussed that it is crucial to be able to extract the type F[T]
from its fixed point representation T
. If T
is Recursive
you can extract F[T]
from T
, where F
is the higher-kinded type T
is a fixed point of. You can specify this F
via a type in the companion object of Recursive
- Recursive.Aux[T, F[_]]
.
The fact that you can extract F[T]
from T
is a necessary condition for the recursion schemes defined in the Recursive[T]
type class. They have one thing in common: they all tear down a recursive structure. Here is an intuition for this:
project
is a "taker" - it is capable of extracting information from T
. Naturally, if you take something from T
, there becomes less of that something in T
. This way, you can "pump" the structure, layer by layer, from T
, and do whatever you want with it, until there is nothing left in T
.
The arrow on the diagram points from F[T]
towards T
to indicate that T
is a member of the structure F[T]
. It does not indicate a direction of the information flow ("who takes from whom") in the project
application.
It follows from the name that Corecursive
is a dual of Recursive
- hence, it must do the opposite thing to what Recursive
does.
Indeed, it mirrors Recursive
in a sense that it also has a single abstract method and a bunch of recursion schemes based on it. This method is embed
and is roughly Base[T] => T
. If project
takes the information out of the structure and hence is good for evaluating them via algebras, embed
places the information into the structure, hence building it up:
An example of a recursion scheme that takes an advantage of such a capability is anamorphism ana: (A, Coalgebra[Base, A]) => T
. Coalgebra
, being a dual of Algebra
, is A => Base[A]
and describes how to build up a single layer of the structure from A
. ana
aims to build deep structures using an initial element A
and a way to build a single layer from it. But this is a bit out of scope of the article, since we were focusing on catamorphisms.
Let us now see how to rewrite our examples from the previous chapters using Matryoshka.
First of all, make sure you apply SI-2712 fix, or else implicits won't resolve correctly and this will spoil you all the fun.
Next, do some Matryoshka imports:
import matryoshka.{ Recursive, Corecursive }
import matryoshka.data.Fix // The fixed-point type similar to the one we implemented ad-hoc, but with Recursive and Corecursive instances.
import matryoshka.implicits._ // Syntax
And here is the code for the examples:
// Nat to Int
def natToInt[T](n: T)(implicit T: Recursive.Aux[T, Nat]): Int = n.cata[Int] {
case Succ(x) => 1 + x
case Zero => 0
}
def nat[T](implicit T: Corecursive.Aux[T, Nat]): T =
Succ(
Succ(
Succ(
Zero.embed
).embed
).embed
).embed
val natRes = natToInt(nat[Fix[Nat]])
println(natRes) // 3
// Sum a list of ints
def sumList[T](l: T)(implicit T: Recursive.Aux[T, IntList]): Int = l.cata[Int] {
case Cons(head, tail) => head + tail
case Empty => 0
}
def lst[T](implicit T: Corecursive.Aux[T, IntList]): T =
Cons(1,
Cons(2,
Cons(3,
Empty.embed
).embed
).embed
).embed
val listRes = sumList(lst[Fix[IntList]])
println(listRes) // 6
// Evaluate an expression
def eval[T](e: T)(implicit T: Recursive.Aux[T, Expr]): Int = e.cata[Int] {
case Add (x1, x2) => x1 + x2
case Mult(x1, x2) => x1 * x2
case Num (x) => x
}
def expr[T](implicit T: Corecursive.Aux[T, Expr]): T =
Add(
Mult(
Num(2).embed,
Num(3).embed
).embed,
Num(3).embed
).embed
val exprRes = eval(expr[Fix[Expr]])
println(exprRes) // 9
Main differences from our ad-hoc solution:
Fix
to either build up or tear down our structures. Instead, we require corresponding behavior via Recursive
and Corecursive
type classes.
cata
: only one type parameter and the convenient OOP-like syntax with the .
- thanks to import matryoshka.implicits._
.
Fix
, now we have an embed
method for it. Less parentheses.
Whenever you use recursion in your code, chances are that what you do is already abstracted in one of the recursion schemes. The benefit from using them instead of bare recursion is similar to the benefit when using for
or while
instead of goto
- more concise, readable and secure code.
Matryoshka is an framework that does a great job introducing someone to these concepts. It has one rather significant drawback, however - at the moment, it is not stack-safe. For larger structures, this becomes a problem.
Nevertheless, in my opinion, every programmer aspiring to perfect their craft would benefit greatly from trying to solve their everyday recursive tasks in a more "literate" way Matryoshka offers.