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")
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.
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))
}
}
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 ...
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
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):
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 23def 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 ?:
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)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 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))
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)
}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:
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)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:
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 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).
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)
}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:
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 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:
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)
}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
}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)
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)
}
}