override lazy val

Peregrinations of a developer in Scala land

Nesting in the nest of Nesting Dolls - S01E01

Last time we left our hero just before he began his exciting trip in the strange forests of Recursionland, searching for ways to refactor his recursion-filled code.

Chapter 3 — In the forest of grafted trees

Upon arrival, our hero first stepped into a very strange-looking forest. There was something rather unusual with the trees but oddly enough, he was unable to pinpoint it at first. He wandered for a while among the trees before he met a cheerful young fellow. The lad was going by the name of Master Cobuyin, and he looked like he knew this forest like the back of his hand.

When sharing with him the disturbing feeling these trees were giving him, Master Cobuyin answered :

“The trees that grow in your country might look rather strange to us too. You see, my people finds very disturbing the recursive shape of your trees

sealed trait Schema

case object IntType extends Schema
case object StringType extends Schema
final case class ArrayType(elementType: Schema) extends Schema
final case class StructType(fields: (String, Schema)*) extends Schema

our trees are much more elegant than that” — a statement that let our hero rather skeptical — “check it out :

sealed trait SchemaF[+A]

case object IntTypeF extends SchemaF[Nothing]
case object StringTypeF extends SchemaF[Nothing]
final case class ArrayTypeF[A](elementType: A) extends SchemaF[A]
final case class StructTypeF[A](fields :(String, A)*) extends SchemaF[A]

Where your trees see their branches as smaller trees of the same species, ours have a way more flexible definition. In general though, we call them pattern functor rather than trees.”

“But how do you even name such trees species ?” asked our hero. “I mean, back in my country, both StructType("foo" -> ArrayType(StringType)) and ArrayType(IntType) are trees of the species Schema. But there, StructTypeF("foo" -> ArrayTypeF(StringTypeF)) is of type SchemaF[SchemaF[SchemaF[Nothing]]] while ArrayTypeF(IntTypeF) is of type SchemaF[SchemaF[Nothing]]; both are of incompatible species. So what’s the point ?”

“It’s fixed”, answered Cobuyin in a smirk; but seeing that our hero was rather baffled, he continued, “sorry for that pun, what I meant was that we graft our trees with what we call a fixed-point type. Here is the simplest one :

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

Using that on each branch of a tree, we can break (or rather fix) the recursion in the types :”

val fixStruct: Fix[SchemaF] = Fix(StructTypeF(
  "foo" -> Fix(ArrayTypeF(

“I see”, admitted our hero after a little head scratching, “but that looks rather tedious. And what is it good for ?”

“Well to understand this, you’ll first need to meet our pets”, said Master Cobuyin, and putting two fingers in his mouth, he blown a loud and clear whistle…

Chapter 4 — Petting the cutest recursive beast

Down the nearest tree jumped a cute little animal.

“Meet Cata, my domesticated catamorphism. It has been trained so that, when instructed with very simple orders it’s able to traverse a whole tree down to the leaves, and then apply my orders recursively while getting back to the root. We call these orders algebra and they have the form F[A] => A (some also say f-algebra to distinguish these algebras that apply to pattern functors from the other kinds of algebras).

So for example, what we call an Algebra[F, A] (where F is of kind * → *) is simply a function F[A] => A, check it out :

val toStringAlgebra: Algebra[SchemaF, String] = { // simply a SchemaF[String] => String function
  case IntTypeF            => "int"
  case StringTypeF         => "string"
  case ArrayTypeF(elem)    => s"array<$elem>"
  case StructTypeF(fields) => s"struct<${fields.map{case (n,v) => n + ":" + v}.mkString(",")}>"

And when I say fixStruct.cata(toStringAlgebra) Cata gets back to me with the string struct<foo:array<string>>.

Isn’t that cool ? I don’t have to bother with the traversal myself, all I have to do is to say what needs to be done with each node. Moreover, inside my Algebra, each “level” receives what has been built with the lower levels.

In other words the elem pattern in case ArrayTypeF(elem) above has type String and contains whatever was built by the algebra with what was inside this ArrayTypeF in the first place.”

“Wow! That looks incredibly useful! But seriously, what’s up with these strange names ?”

“These names will make sense eventually”, responded Cobuyin, “if you understand that we consider our grafted trees like Fix[SchemaF] to be superior to other things like String. Thus, when you transform a Fix[SchemaF] to a String, you are going down the scale, which is cata in greek (for unknown reasons, our zoologists use greek rather than latin to name species).

Conversely, an operation that transforms a String to a Fix[SchemaF] goes up the scale, and is therefore named ana-morphism. And since it goes the other way around, what it needs is a Coalgebra.”

Chapter 5 — Training one’s new botanic skills

“There is still a thing bothering me”, our hero mumbled, “There is no way a catamorphism could possibly operate on my trees back home, is it ?”

“Well you’re quite right, you cannot make a cata operate directly on, say, a Schema”, said Cobuyin, “but there is a way to lure it into climbing your trees, by making it believe it’s a grafted tree.

For that to work, you need to know a pattern-functor that can represent your tree, like SchemaF, and you need a Functor[SchemaF] instance for it (to write one should be quite easy, right ?).

Then you need to create an instance of Recursive[Schema] which is a typeclass that witnesses the fact that one can project your recursive Schema into some pattern functor. Such instance would look like this :

implicit val schemaRecursive = new Recursive[Schema] {
    type Base[A] = SchemaF[A]  // the pattern functor into which Schema will be projected

    def project(schema: Schema)(implicit F: Functor[Base]): Base[Schema] = schema match {
        case IntType                => IntTypeF
        case StringType             => StringTypeF
        case ArrayType(elementType) => ArrayTypeF(elementType)
        case StructType(fields)     => StructTypeF(fields)

That’s basically saying that you can project any mundane — sorry for that — Schema into its corresponding SchemaF.

See how the project function treats your recursive Schema one layer at a time. That’s one of the benefits of pattern functors : when you have a SchemaF[A], the A can be anything (obviously). We use that to our advantage when constructing such structures (with project) and when destructing them (in the algebras we pass to cata).”

”Dear Lord! ” exclaimed our hero, “this is so inspiring. I already see how all that can help with my problems back home. I may return there for a while, solving the most urging one. But I’m pretty sure we’ll meet again, for for I feel I’ve still a lot to learn from you.”

And so he went back home to solve some problems using recursion schemes, soon to be seen again it these strange landscapes.

— Credits —

  • Greg Pfeil (@sellout) as Master Cobuyin

The stage was set in the matryoshka landscapes.

No catamorphism was harmed during the making of this post.

comments powered by Disqus


Hi ! I'm Valentin Kasas and this is my programming blog.

I am a happy Scala user since 2012 and here is where I recount some of my wanderings in that vast landscape.

Follow @vil1