# 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!*

*Let’s start!*

*1. Recursive Data Structure:*

*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 traitMatryoshkacase classDoll(name: String, daughter: Matryoshka)extendsMatryoshkacase classTiny(name: String)extendsMatryoshka

### 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 classPerson(name: String, age: Int)

### 2. Preparation to use Matryoshka

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

**a. Remove recursion**

sealed traitMatryoshkacase classDoll(name: String, daughter: ???)extendsMatryoshkacase classTiny(name: String)extendsMatryoshka

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 traitMatryoshka[T]case classDoll[T](name: String, daughter: T)extendsMatryoshka[T]case classTiny[T](name: String)extendsMatryoshka[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 classFix[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:*

valdolls: 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 valdollsFunctorImpl: Functor[Matryoshka] =newFunctor[Matryoshka] {

override defmap[A, B](fa: Matryoshka[A])(f: A => B): Matryoshka[B] = famatch{

caseDoll(n, d) =>Doll(n, f(d))

caseTiny(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[_]`

typeCoalgebra[F[_], A] = A => F[A]

In our case `F[_]`

is `Matryoshka[_]`

and `A`

is `NonEmptyList[String]`

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

!

valcoalgebra: Coalgebra[Matryoshka, NonEmptyList[String]] = {

caseNonEmptyList(h, _: INil[String]) =>Tiny(h)

caseNonEmptyList(h, l) =>

vallist: 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.

defana[A](a: A)(f: Coalgebra[F, A])(implicitF: Functor[F]): F[A]

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

valnames=NonEmptyList("a", "b", "c", "d")valresult=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`

typeAlgebra[F[_], A] = F[A] => A

So, let’s define our `Algebra[Matryoshka, Int]`

, It’s very simple!

valalgebra: Algebra[Matryoshka, Int] = {

caseDoll(_, d) => 1 + d

caseTiny(_) => 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

defcata[A](f: Algebra[F, A])(implicitBF: 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`

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

valresult=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!

valalgebraPerson: Algebra[Matryoshka, List[Person]] = {

caseDoll(n, d) => d :+Person(n, d.last.age + 1)

caseTiny(n) =>Person(n, 6) ::Nil}

Cool, now we can call

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

But for better performance, 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**

*A friendly guide for leveraging the power of recursion schemes in real-world applications …*github.com

**ogirardot/high-perf-privacy-scalaIO2018**

*High performance Privacy By Design using Matryoshka and Spark talk code - ogirardot/high-perf-privacy-scalaIO2018*github.com