droste.md

Droste for the really really impatient

For this tutorial we'll be using a simplified version of our expression tree. Our expressions accept only binary expressions that combine Integers and Strings using plus and minus operators. The rules are simple:

• Adding or subtracting two integers is allowed. The result is the sum/subtraction of both numbers
• Adding two strings or a string and an integer is allowed. The result will be the result of concatenating both operands as if they were strings
• Subtracting a String from an int (or vice versa) is not allowed

Examples:

• 2 + 3 + "foo" = "5foo"
• 2 - 1 = 1
• 2 - 1 + "foo" = "1foo"
• 2 + "foo" - 2 = error(can't evaluate "foo - 2")

---

Step1 Model

In order to implement the previous we'll be using the following model:

import cats.{Applicative, Traverse}
import higherkindness.droste.util.DefaultTraverse
import cats.implicits._
import higherkindness.droste.{Algebra, AlgebraM}
import higherkindness.droste.data.Fix

 type ExpressionTree = Fix[ExpressionF]

  sealed trait Operator
  case object Addition extends Operator
  case object Subtraction extends Operator

  sealed trait ExpressionF[A]
  case class BinaryExpression[A](left: A, operator: Operator, right: A) extends ExpressionF[A]
  case class StringLiteral[A](v: String) extends ExpressionF[A]
  case class IntLiteral[A](v: Int) extends ExpressionF[A]

As far as the "A" parameter goes, we're not gonna address it in this "tutorial", I'll just try to add some resources to look into Fixed point at the end.

Step2 Traverse Instance

In some cases you can get away with implementing a simple Functor but in this case, since we'll later want to be able to wrap our computation in a Monad we have to define a traverse instance.

This instance is essentially defining for each node (fa) how do we traverse it.

A different way of looking at it is that this instance is a way to say for each node, what its descendants are.

E.g: A binary expression has two descendants, the left expr and the right expr, that's why we do f(left) and f(right).

Notice that we don't need to recurse into the expressions themselves (and I'm 90% sure we wouldn't be able to even if we wanted)

  import cats.implicits._
  implicit val traverse: Traverse[ExpressionF] with DefaultTraverse[ExpressionF] = new Traverse[ExpressionF] with DefaultTraverse[ExpressionF] {
    override def traverse[G[_]: Applicative, A, B](fa: ExpressionF[A])(f: A => G[B]): G[ExpressionF[B]] =
      fa match {
        case BinaryExpression(left, operator, right) =>
          (f(left), f(right)).mapN {
            case (l, r) => BinaryExpression(l, operator, r)
          }
        case StringLiteral(v) =>
          Applicative[G].pure(StringLiteral[B](v))
        case IntLiteral(v) =>
          Applicative[G].pure(IntLiteral[B](v))
      }
  }

P.S.: What does it mean to map/traverse a node n ?

Traversing a node means you take an ExpressionF[A] and map each of their direct children getting back an ExpressionF[B] :

    val f: ExpressionF[String] = BinaryExpression("2",Addition, "3")
    println(f.map(s => s + "mapped"))//prints BinaryExpression(2mapped,Addition,3mapped)
    println(f.traverse[List,String](s => List(s + "mapped"))) //prints List(BinaryExpression(2mapped,Addition,3mapped))

What about ExpressionF[ExpressionTree] ?

The same logic applies! You'll be given "access" to each of the direct children :

val f2: ExpressionF[ExpressionTree] = BinaryExpression[ExpressionTree](
    Fix(StringLiteral[ExpressionTree]("2")),
    Addition,
    Fix(StringLiteral[ExpressionTree]("3"))
  )
  println(f2.map(t => t.asInstanceOf[StringLiteral[ExpressionTree]].v)) //BinaryExpression(2,Addition,3)

An additionally (and possibly wrong) way you can also look at this is:

If we traverse a List[Int],we expect to be able to specify a transformation for each element of the list.

If we traverse an ExpressionF[Int] we expect to be specify a transformation for each element of the ExpressionF (aka it's direct descendants).

If we traverse a List[List[Int]] we also expect to be able to specify a transformation for each element of the list (happens to be a List[Int])

If we traverse an ExpressionF[ExpressionTree] the expectation is also to be able to specify a transformation for each element of the ExpressionF (happens to be a ExpressionTree)

In a way, you can see ExpressionF[ExpressionTree] as a collection of ExpressionTree's which contain ExpressionF which contain ExpressionTrees ...

Step3 Recursion schemes

Droste makes recursion schemes (essentially "abstracted recursion behaviour") available through two main packages:

• higherkindness.droste.scheme
• higherkindness.droste.scheme.zoo

Let's look at a couple of them

Catamorphism: higherkindness.droste.scheme.cata/higherkindness.droste.scheme.cataM

This is just a way to take a "tree" and, starting from the leaves collapse it into a single value. E.g: Let's try to quickly create an incomplete evaluator (we're not gonna deal with errors or ints for now):

With recursion schemes

  def evaluate(f: ExpressionTree): String =
    higherkindness.droste.scheme.cata[ExpressionF, ExpressionTree, String]{Algebra {
      case BinaryExpression(leftStr, Addition, rightStr) =>
        (leftStr + rightStr)
      case StringLiteral(v) => v
      case other => ???
    }
  }.apply(f)
  println(evaluate(Fix(f2))) //returns 23

Without recursion schemes

def evaluate(f: ExpressionTree): String =
  f.unfix.map(evaluate) match {
    case BinaryExpression(leftStr, Addition, rightStr) =>
      (leftStr + rightStr)
    case StringLiteral(v) => v
    case other            => ???
  }

Quick tip: I would really recommend trying to implement the above on your own since as soon as the type parameters are filled in for the cata function higherkindness.droste.scheme.cata[ExpressionF, ExpressionTree, String], intellij will be able to infer the argument types and generate the match cases for you, meaning you can essentially do most of it in autopilot

**Soo, what's happening ? **

In a nutshell droste is handling the "recursion"/"traversal" for us (using the traverse instance we previously defined); all we have to do is tell droste how to combine the intermediate results.

What if we want to be able to specify errors ?:

With recursion schemes

  type ErrorOr[A] = Either[String, A]
  def evaluateM(f: ExpressionTree): ErrorOr[String] =
    higherkindness.droste.scheme.cataM[ErrorOr,ExpressionF, ExpressionTree, String]{AlgebraM {
      case BinaryExpression(leftStr, Addition, rightStr) =>
        (leftStr + rightStr).asRight
      case StringLiteral(v) => v.asRight
      case IntLiteral(v) => s"$v is not a string".asLeft
    }}.apply(f) 
  println(evaluate(Fix(f2))) //prints Right(23)

Without recursion schemes

def evaluateM(f: ExpressionTree): ErrorOr[String] =
  f.unfix.traverse(evaluateM).flatMap {
    case BinaryExpression(leftStr, Addition, rightStr) =>
      (leftStr + rightStr).asRight
    case StringLiteral(v) => v.asRight
    case IntLiteral(v)    => s"$v is not a string".asLeft
  }

Soo, what's happening now ?

The gist of it is the same as before, the only difference is that we can now specify our computation within a monad, we also have to use an AlgebraM instead of an Algebra (don't worry, again you don't have to know this by heart, the IDE is there for you!)

Paramorphism

Paramorphism can be seen as a "special" case of "catamorphism" which gives you access to both the children's computed value and the children's node!

E.g: Let's again try to quickly create an evaluator that handles expressions doing addition of either strings or integers

Note: Since the evaluation result can be either an Integer or a String we're going to use an Either[Int,String] as the "result".

(Apologies for the fact that it looks a bit convoluted having things like Right(left))

With recursion schemes

 def evaluateOnlyIntOrString(f: ExpressionTree): Either[Int,String] ={
    higherkindness.droste.scheme.zoo.para[ExpressionF, ExpressionTree, Either[Int,String]]{RAlgebra {
      case BinaryExpression((nodeL, resultL), Addition, (nodeR,resultR)) =>
        (resultL, resultR) match {
          case (Right(left), Right(right)) => (right + left).asRight
          case (Left(left), Left(right)) => (right + left).asLeft
          case oops => ???
        }
      case StringLiteral(v) => v.asRight
      case IntLiteral(v) => v.asLeft
    }}.apply(f)
  }

Without recursion schemes

def evaluateOnlyIntOrString2(f: ExpressionTree): Either[Int, String] = {
  f.unfix.map(child => (child, evaluateOnlyIntOrString2(child))) match {
    case BinaryExpression((nodeL, resultL), Addition, (nodeR, resultR)) =>
      (resultL, resultR) match {
        case (Right(left), Right(right)) => (right + left).asRight
        case (Left(left), Left(right))   => (right + left).asLeft
        case oops => ???
      }
    case StringLiteral(v) => v.asRight
    case IntLiteral(v)    => v.asLeft
  }
}

What's happening ?

Well, pretty much the same as what's happening for the paramorphism, the only differences are:

• we have access to the descendants computation result and the descendant themselves(notice the tuple (nodeL, resultL) instead of a single value )
• we use a RAlgebra (again, no need to commit this to memory, intellij has your back)
• we use an Either[Int, String] (this is just a product of the new requirement)

Why did we do a parmorphism again ?

Good point! We're not really using nodeL nor nodeR so how could we ?
Well, let's say we have a show instance for ExpressionTree:

With recursion schemes

  implicit val show: Show[ExpressionTree] = { tree: ExpressionTree =>
    higherkindness.droste.scheme.cata[ExpressionF,ExpressionTree, String](Algebra {
      case BinaryExpression(left, operator, right) =>
      left +  (if(operator==Addition) "+" else "-") + right
      case StringLiteral(v) =>v
      case IntLiteral(v) =>v.toString
    }).apply(tree)

Without recursion schemes

implicit val show: Show[ExpressionTree] = { tree: ExpressionTree =>
  tree.unfix match {
    case BinaryExpression(left, operator, right) => left.show + (if (operator == Addition) "+" else "-") + right.show
    case StringLiteral(v) => v
    case IntLiteral(v) => v.toString
  }
}

now we can do something like:

With recursion schemes

def evaluateOnlyIntOrString(f: ExpressionTree): Either[Int,String] ={
    higherkindness.droste.scheme.zoo.para[ExpressionF, ExpressionTree, Either[Int,String]]{RAlgebra {
      case BinaryExpression((nodeL, resultL), Addition, (nodeR,resultR)) =>
        (resultL, resultR) match {
          case (Right(left), Right(right)) => (right + left).asRight
          case (Left(left), Left(right)) => (right + left).asLeft
          case _ =>
            throw new RuntimeException(s"""
                                          |Expression ${f.show} can't be evaluated.
                                          |The subexpressions `${nodeL.show}` and `${nodeR.show}` have mismatching types.
                                          |""".stripMargin)
        }
      case StringLiteral(v) => v.asRight
      case IntLiteral(v) => v.asLeft
    }}.apply(f)
  }

Without recursion schemes

def evaluateOnlyIntOrString(f: ExpressionTree): Either[Int, String] = {
  f.unfix.map(child => (child, evaluateOnlyIntOrString(child))) match {
    case BinaryExpression((nodeL, resultL), Addition, (nodeR, resultR)) =>
      (resultL, resultR) match {
        case (Right(left), Right(right)) => (right + left).asRight
        case (Left(left), Left(right))   => (right + left).asLeft
        case _ =>
          throw new RuntimeException(s"""
                                        |Expression ${f.show} can't be evaluated.
                                        |The subexpressions `${nodeL.show}` and `${nodeR.show}` have mismatching types.
                                        |""".stripMargin)
      }
    case StringLiteral(v) => v.asRight
    case IntLiteral(v)    => v.asLeft
  }
}

Notice that we're able to easily get the descendants information and therefore render a nice error message.

Note: As before, a monadic paraM exists which would allow you do use an IO/Either to wrap your computation avoiding throwing an exception and potentially short circuiting the computation (**yet to be confirmed).

Other morphisms

Have a quick look at higherkindness.droste.scheme.zoo. and higherkindness.droste.scheme.

Most of the morphisms have a quick description of what they do which helps.

For some however,I've found that giving them a try (by filling the type parameters in the morphism signature) and then looking at the types you're given helps quite a lot:

  def evaluateOnlyIntOrString(f: ExpressionTree): Int ={
    higherkindness.droste.scheme.zoo.histo[ExpressionF, ExpressionTree, Int]{CVAlgebra {
      case BinaryExpression(left, operator, right) =>
        //we get the current computed result (Int) and the history of the computed results for the descendants
        val l: (Int, ExpressionF[Attr[ExpressionF, Int]]) = Attr.un(left)
        val r: (Int, ExpressionF[Attr[ExpressionF, Int]]) = Attr.un(right)
        ???
      case StringLiteral(v) => ???
      case IntLiteral(v) => ???
    }}.apply(f)
  }

Using the traverse instance

One thing that wasn't used yet is the fact that we can define things in a more succinct and flexible way using our traverse instance. Let's say we want to calculate the biggest number knowing that all the strings can safely be converted to ints!

One simple approach is to, again, use a catamorphism:

With recursion schemes

  def getBiggest(f: ExpressionTree): Int ={
    higherkindness.droste.scheme.cata[ExpressionF, ExpressionTree, Int]{Algebra {
      case BinaryExpression(left, _, right) =>
        Math.max(left, right)
      case StringLiteral(v) => v.toInt
      case IntLiteral(v) => v
    }}.apply(f)
  }

Without recursion schemes

def getBiggest(f: ExpressionTree): Int =
  f.unfix.map(getBiggest) match {
    case BinaryExpression(left, _, right) =>
      Math.max(left, right)
    case StringLiteral(v) => v.toInt
    case IntLiteral(v)    => v
  }

And now let's say we add more expression types, like a new case class TernaryExpression[A](one: A, two: A, three: A) extends ExpressionF[A]

First things first, we have to update our traverse instance with a new branch:

 case TernaryExpression(one, two, three) =>
          (f(one),f(two),f(three)).mapN{
            case (a,b,c) => TernaryExpression(a,b,c)
          }

And now we can do something like :

  def getBiggestWithTernary(f: ExpressionTree): Int ={
    higherkindness.droste.scheme.cata[ExpressionF, ExpressionTree, Int]{Algebra {
      case TernaryExpression(a, b, c) =>
        Math.max(Math.max(a,b),c)
      case BinaryExpression(left, _, right) =>
        Math.max(left, right)
      case StringLiteral(v) => v.toInt
      case IntLiteral(v) => v
    }}.apply(f)
  }

But if we remember the traverse instance discussion, we said that we can "map/fold" any ExpressionF to get access to it's children!

Using that "bit of knowledge" we can now transform the previous example into a more DRY:

With recursion schemes

  def getBiggestWithTernary2(f: ExpressionTree): Int ={
    higherkindness.droste.scheme.cata[ExpressionF, ExpressionTree, Int]{Algebra {
      case a@(_:TernaryExpression[Int] | _: BinaryExpression[Int]) =>
        a.toList.max //you could also use foldMap  
      case StringLiteral(v) => v.toInt
      case IntLiteral(v) => v
    }}.apply(f)
  }

Without recursion schemes

def getBiggestWithTernary2(f: ExpressionTree): Int = 
  f.unfix.map(getBiggestWithTernary2) match {
    case a @ (_: TernaryExpression[Int] | _: BinaryExpression[Int]) =>
      a.toList.max
    case StringLiteral(v) => v.toInt
    case IntLiteral(v)    => v
  }

Hints and "best practices"

Most Droste type parameters share a "naming convention" for type parameters:

• M is the monad (e.g:the ErrorOr we used the evaluateM; can also be IO/Reader/...)
• F is the "type functor", essentially the type you defined the traverse instance for (ExpressionF)
• R is the Fix[FunctorType] aka ExpressionTree
• B is the "output type", in the previous examples it was string 'cause that's what we were returning
• A is used only for anamorphism like schemes (it's essentially the "input" type)

Full example code

package io.lenses.sql.connector.evaluator

import cats.{Applicative, Show, Traverse}
import higherkindness.droste.util.DefaultTraverse
import cats.implicits._
import higherkindness.droste.{Algebra, AlgebraM, RAlgebra}
import higherkindness.droste.data.{Fix}
object Example extends App {
  sealed trait Operator
  case object Addition extends Operator
  case object Subtraction extends Operator

  type ExpressionTree = Fix[ExpressionF]

  sealed trait ExpressionF[A]
  case class BinaryExpression[A](left: A, operator: Operator, right: A) extends ExpressionF[A]
  case class StringLiteral[A](v: String) extends ExpressionF[A]
  case class IntLiteral[A](v: Int) extends ExpressionF[A]
  case class TernaryExpression[A](one: A, two: A, three: A) extends ExpressionF[A]

  implicit val traverse: Traverse[ExpressionF] with DefaultTraverse[ExpressionF] = new Traverse[ExpressionF]
  with DefaultTraverse[ExpressionF] {
    override def traverse[G[_]: Applicative, A, B](fa: ExpressionF[A])(f: A => G[B]): G[ExpressionF[B]] =
      fa match {
        case BinaryExpression(left, operator, right) =>
          (f(left), f(right)).mapN {
            case (l, r) => BinaryExpression(l, operator, r)
          }
        case TernaryExpression(one, two, three) =>
          (f(one),f(two),f(three)).mapN{
            case (a,b,c) => TernaryExpression(a,b,c)
          }
        case StringLiteral(v) =>
          Applicative[G].pure(StringLiteral[B](v))
        case IntLiteral(v) =>
          Applicative[G].pure(IntLiteral[B](v))
      }
  }
  val f: ExpressionF[String] = BinaryExpression("2", Addition, "3")
  println(f.map(s => s + "mapped"))
  println(f.traverse[List, String](s => List(s + "mapped")))
  println("--------------------------")

  val f2: ExpressionF[ExpressionTree] = BinaryExpression[ExpressionTree](
    Fix(StringLiteral[ExpressionTree]("2")),
    Addition,
    Fix(StringLiteral[ExpressionTree]("3"))
  )
  println(f2.map(t => t.asInstanceOf[StringLiteral[ExpressionTree]].v))

  def evaluate(f: ExpressionTree): String =
    higherkindness.droste.scheme.cata[ExpressionF, ExpressionTree, String]{Algebra {
      case BinaryExpression(leftStr, Addition, rightStr) =>
        (leftStr + rightStr)
      case StringLiteral(v) => v
      case other => ???
    }
  }.apply(f)

  println(evaluate(Fix(f2)))


  type ErrorOr[A] = Either[String, A]
  def evaluateM(f: ExpressionTree): ErrorOr[String] =
    higherkindness.droste.scheme.cataM[ErrorOr,ExpressionF, ExpressionTree, String]{AlgebraM {
      case BinaryExpression(leftStr, Addition, rightStr) =>
        (leftStr + rightStr).asRight
      case StringLiteral(v) => v.asRight
      case IntLiteral(v) => s"$v is not a string".asLeft
    }}.apply(f)

  println(evaluateM(Fix(f2)))

  def evaluateOnlyIntOrString(f: ExpressionTree): Either[Int,String] ={
    higherkindness.droste.scheme.zoo.para[ExpressionF, ExpressionTree, Either[Int,String]]{RAlgebra {
      case BinaryExpression((nodeL, resultL), Addition, (nodeR,resultR)) =>
        (resultL, resultR) match {
          case (Right(left), Right(right)) => (right + left).asRight
          case (Left(left), Left(right)) => (right + left).asLeft
          case _ =>
            throw new RuntimeException(s"""
                                          |Expression ${f.show} can't be evaluated.
                                          |The subexpressions `${nodeL.show}` and `${nodeR.show}` have mismatching types.
                                          |""".stripMargin)
        }
      case StringLiteral(v) => v.asRight
      case IntLiteral(v) => v.asLeft
    }}.apply(f)
  }

  def getBiggest(f: ExpressionTree): Int ={
    higherkindness.droste.scheme.cata[ExpressionF, ExpressionTree, Int]{Algebra {
      case BinaryExpression(left, _, right) =>
        Math.max(left, right)
      case StringLiteral(v) => v.toInt
      case IntLiteral(v) => v
    }}.apply(f)
  }

  def getBiggestWithTernary(f: ExpressionTree): Int ={
    higherkindness.droste.scheme.cata[ExpressionF, ExpressionTree, Int]{Algebra {
      case a@(_:TernaryExpression[Int] | _: BinaryExpression[Int]) =>
        a.toList.max
      case StringLiteral(v) => v.toInt
      case IntLiteral(v) => v
    }}.apply(f)
  }


  implicit val show: Show[ExpressionTree] = { tree: ExpressionTree =>
    higherkindness.droste.scheme.cata[ExpressionF,ExpressionTree, String](Algebra {
      case BinaryExpression(left, operator, right) =>
      left +  (if(operator==Addition) "+" else "-") + right
      case StringLiteral(v) =>v
      case IntLiteral(v) =>v.toString
    }).apply(tree)
  }
}