Boolean logic with Recusion Schemes and hand-written interpreters.

0-observations.md

Pros for recusion schemes

More fold methods: cata, cataM, gcata, gcataM, hylo, hyloM, ghylo, ghyloM, histo, histoM, ghisto, ghistoM, and more.

Easier to maintain; adding nodes means you just have to update your algebras and your functor instance. With the hand-written ones you’d have to update each of those methods, as well as your algebras.

If you want to mix together/extend the ADT, you can do so using a simple coproduct (like Either)

Tail-rec for free

Scales with complexity more easily.

Pros for hand-written interpreters

Much easier to read, especially before you've studied recursion schemes.

In most business situations you'll only want one, maybe two of the fold methods mentioned above. So maintenance overhead could be negligible

Writing the expressions doesn't require any embed rigamaroll.

Performance, because less boxing.

Other notes

This can all usually be done away with using the Finally Tagless pattern.

For fun

Rewrite cata in the hand-written interpreter to be tail-recursive. You can use the scastie link at the top of the file to mess around with it.

1-Hand-Written.scala

// https://scastie.scala-lang.org/Jacoby6000/KFm89A8bSvy7tf2HyzJgFQ

sealed trait Expr
case class And(l: Expr, r: Expr) extends Expr
case class Not(expr: Expr) extends Expr
case class Equal(l: Symbol, r: Symbol) extends Expr

sealed trait Symbol
case class Ref(ref: String) extends Symbol
case class Literal(literal: String) extends Symbol

object Expr {
  def cata[A](expr: Expr)(
    andFunc: (A, A) => A,
    notFunc: A => A,
    equalFunc: (Symbol, Symbol) => A
  ): A = {
  	def evalSubExpr(subExpr: Expr): A = cata(subExpr)(andFunc, notFunc, equalFunc)
  
    expr match {
      // branches
      case And(lExpr, rExpr) => andFunc(evalSubExpr(lExpr), evalSubExpr(rExpr))
      case Not(expr) => notFunc(evalSubExpr(expr))

      // leaves
      case Equal(l, r) => equalFunc(l, r)

    }
  }
}
                              
val references: Map[String, String] =
  Map(
    "x" -> "Y",
    "a" -> "foo",
    "b" -> "bar"
  )

def evaluateSymbol(sym: Symbol): String =
  sym match {
    case Ref(x) => references.get(x.toLowerCase).getOrElse("") // If a reference doesn't exist, default to empty string
    case Literal(v) => v // just unrap literals.
  }

def solveExpression(expr: Expr): Boolean =
  Expr.cata[Boolean](expr)(
    andFunc = (l, r) => l && r,
    notFunc = bool => !bool,
    equalFunc = (lSym, rSym) => evaluateSymbol(lSym) == evaluateSymbol(rSym)
  )

val expr: Expr =
  And(
    Equal(
      Ref("X"), 
      Literal("Y")
    ), 
    Not(
      Equal(
        Ref("A"), 
        Ref("B")
      )
    )
  )

solveExpression(expr)

2-Recusion-Schemes.scala

// https://scastie.scala-lang.org/Jacoby6000/hIGrMSl2Qsmr2ZZEN4Vltg

import matryoshka._
import matryoshka.implicits._
import matryoshka.data.Mu
import scalaz.Functor

// Set up a system of basic arithmetic
sealed trait Expr[A]
case class And[A](l: A, r: A) extends Expr[A]
case class Not[A](expr: A) extends Expr[A]
case class Equal[A](l: Symbol, r: Symbol) extends Expr[A]

sealed trait Symbol
case class Ref(ref: String) extends Symbol
case class Literal(literal: String) extends Symbol


object Expr {
  // For most of these it's just applying f to the branches. 
  // Leaf nodes are left alone.
  implicit val arithmeticFunctor: Functor[Expr] = new Functor[Expr] {
    def map[A, B](fa: Expr[A])(f: A => B): Expr[B] =
      fa match {
        // Branches
        case And(l, r) => And(f(l), f(r)) 
        case Not(expr) => Not(f(expr))
        
        // Leaves
        case Equal(l, r) => Equal(l, r) // do nothing, since this is a leaf node.
      }
  }
}

                              
val references: Map[String, String] =
  Map(
    "x" -> "Y",
    "a" -> "foo",
    "b" -> "bar"
  )

def evaluateSymbol(sym: Symbol): String =
  sym match {
    case Ref(x) => references.get(x.toLowerCase).getOrElse("") // If a reference doesn't exist, default to empty string
    case Literal(v) => v // just unrap literals.
  }

val solver: Algebra[Expr, Boolean] = { // Expr[Boolean] => Boolean
  // Branches
  case And(leftBool, rightBool) => leftBool && rightBool
  case Not(bool) => !bool
  
  // Leaves
  case Equal(l, r) => evaluateSymbol(l) == evaluateSymbol(r)
}

// Now we just need an expression to solve.  
// Below is just (($X == Y) && ($A != $B))
// Each node of the expression tree must be embedded,
// which looks obnoxious, and scala sucks at type 
// inference, so type annotations have to be added.
// Creating a DSL would make creating expressions much 
// easier.
def expr[T](implicit T: Corecursive.Aux[T, Expr]): T =
  And(
    Equal[T](
      Ref("X"), 
      Literal("Y")
    ).embed, 
    Not[T](
      Equal[T](
        Ref("A"), 
        Ref("B")
      ).embed
    ).embed
  ).embed


// So, using the information above, we can build an expression and evaluate it via catamorphism, applying our algebra.
expr[Mu[Expr]].cata(solver)