Getting started with recursion schemes using Matryoshka

Matryoshka is a Scala library that specializes on implementing recursion schemes, it has a mechanism to implicitly do the recursion for us instead of implementing by ourselves the recursive functions, it automates the process of traversing and evaluating the data structures.

So if you have many recursive functions in your code, you have to figure out firstly about your Data Structures design. because Data Structures and algorithms are patterns for solving problems, we are able to come up with more elegant solution, if we have a good design. In order to use Matryoshka we need to deal with recursive Data Structures.

Let’s start!

1. Recursive Data Structure:

We need a recursive Data Structure: An ADT which refers itself.

Let’s take an example of the Russian dolls “Matryoshka dolls”, They are recursive, every doll is a small version of the other, and we have the smallest one (let’s call it Tiny).

this is our ADT

sealed trait Matryoshka
case class Doll(name: String, daughter: Matryoshka) extends Matryoshka
case class Tiny(name: String) extends Matryoshka

Goals:

• Build Matryoshka dolls from a list of names
• Calculate the number of dolls
• Transform List[String] to a List[Person] with its age (the smallest doll should be 6 years old, and each doll is 1 year older)

case class Person(name: String, age: Int)

2. Preparation to use Matryoshka

In order to use matryoshka we need to follow those steps:

a. Remove recursion

sealed trait Matryoshka
case class Doll(name: String, daughter: ???) extends Matryoshka
case class Tiny(name: String) extends Matryoshka

Why?

Matryoshka uses a generic recursion approach, we need to be able to evaluate our Data Structure to other value of any type we want, so we’re going to have a new generic parameter type and we replace the recursive reference with this type:

sealed trait Matryoshka[T]
case class Doll[T](name: String, daughter: T) extends Matryoshka[T]
case class Tiny[T](name: String) extends Matryoshka[T]

T might be Integer, String, Double, Person, Boolean…

b. Recapture Recursion

If we want to build a recursive Data Structure from any value, we need to define: T as Matryoshka[T] where T is another Matryoshka[T] .. If we have 10 dolls: Matryoshka[Matryoshka[Matryoshka[Matryoshka[Matryoshka[Matryoshka[Matryoshka[Matryoshka[Matryoshka[Matryoshka[Nothing]]]]]]]]]] 😳..

How can we generalize this?

We need to define T as another Matryoshka[T] : T = Matryoshka[T]

That remind us about the fixed point of a function is f(x) = x we need a fixed Point of the type Matryoshka[_]

Matryoshka library provides us this Fixed Point type:

case class Fix[F[_]](unFix: F[Fix[F]])

That’s exactly what we need, after we made our Data Structure with kind * -> * like F[_] : Matryoshka[_] we can use Fix[Matryoshka] to define our recursive type and Doll has daughter of type Matryoshka[Fix[Matryoshka]] (because we recapture the recursion and we made T = Fix[Matryoshka] )

Example:

val dolls: Fix[Matryoshka] = Fix(Doll("Anna", Fix(Doll("Lisa", Fix(Tiny("Kate"))))))

c. Functor

Functor is the main thing that makes recursion schemes work. Because matryoshka library requires to define an implicit scalaz Functor instance of our Data Structure to be able to traverse it and to do the recursive calls for us.

The idea is if we have F[A] and we have a function that comes from A => B this will give us F[B]

implicit val dollsFunctorImpl: Functor[Matryoshka] = new Functor[Matryoshka] {
  override def map[A, B](fa: Matryoshka[A])(f: A => B): Matryoshka[B] = fa match {
    case Doll(n, d) => Doll(n, f(d))
    case Tiny(s)    => Tiny(s)
  }
}

3. Recursion schemes using matryoshka

let’s start with the first goal:

a. Build Matryoshka dolls from a list of names (non empty list!)

We need to have a function which comes from NonEmptyList[String] => Matryoshka[_]

Coalgebra[F[_], A] : is a type in matryoshka library that unfold a value A to a structure F[_], we can see it as a function: A => F[_]

type Coalgebra[F[_], A] = A => F[A]

In our case F[_] is Matryoshka[_] and A is NonEmptyList[String]

Let’s define our Coalgebra[Matryoshka, NonEmptyList[String]] !

val coalgebra: Coalgebra[Matryoshka, NonEmptyList[String]] = {
  case NonEmptyList(h, _: INil[String]) => Tiny(h)
  case NonEmptyList(h, l) =>
    val list: List[String] = l.toList
    Doll(h, NonEmptyList(list.head, list.tail : _*))
}

So here we define which operation we perform at each step of the computation. We have a List[String] as an input and we will return Matryoshka[List[String]]

How it works?

Coalgebra will determine the next single step of the construction.

We need to call a recursive function that will go from top to down to build our Data Structure (Matryoshka dolls) from the List at the same time removing the recursive structure that we previously had.

def ana[A](a: A)(f: Coalgebra[F, A])(implicit F: Functor[F]): F[A]

anamorphism: “from the top form” is a generic function that can build a type of shape F[_]

val names = NonEmptyList("a", "b", "c", "d")
val result = names.ana[Fix[Matryoshka]](coalgebra)

Execution:

b. Calculate the number of dolls

We need to have a function which comes from Matryoshka[_] => Int

Algebra[F[_], A] : is a type in matryoshka library that fold a structure F to a value A, we can see it as a function: F[_] => A

type Algebra[F[_], A] = F[A] => A

So, let’s define our Algebra[Matryoshka, Int] , It’s very simple!

val algebra: Algebra[Matryoshka, Int] = {
  case Doll(_, d) => 1 + d
  case Tiny(_) => 1
}

We evaluated in every level the computation.

How it works?

We need to collapse our Data Structure (Matryoshka dolls) down into a single integer value at the same time taking the recursive structure and collapsing it to get a single value

def cata[A](f: Algebra[F, A])(implicit BF: Functor[F]): A

catamorphism: “from the bottom to up form” is a generic function that can fold a value recursively into a single value of type A

val dolls: Fix[Matryoshka] = Fix(Doll("Anna", Fix(Doll("Lisa", Fix[Matryoshka](Tiny("Kate"))))))
val result = dolls.cata[Int](algebra)

Execution:

3. Transform List[String] to a List[Person] with its age (the smallest doll should be 6 years old, and each doll is 1 year older)

We need: List[String] => Matryoshka[_] => List[Person]

We need to define a Coalgebra[Matryoshka, List[String]] and an Algebra[Matryoshka, List[Person]]

We have already implemented our Coalgebra Don’t forget we need to calculate the age of the person in our Algebra let’s do it!

val algebraPerson: Algebra[Matryoshka, List[Person]] = {
  case Doll(n, d) => d :+ Person(n, d.last.age + 1)
  case Tiny(n)    => Person(n, 6) :: Nil
}

Cool, now we can call

names.ana[Fix[Matryoshka]](coalgebra).cata[List[Person]](algebraPerson)

We can use hylo to do that in one pass!

names.hylo(algebraPerson, coalgebra)

I hope you enjoyed reading this blog.

Now you can get started and implement more examples using Matryoshka.

If you’re interested to learn more about Matryoshka library, those are some interesting links:

vil1/recursion-schemes-cookbook

ogirardot/high-perf-privacy-scalaIO2018

tpolecat/cofree

vil1/recursion-schemes-lc2018