Tagless final vs tagless initial vs tagged initial

tagless-final.sc

/** This is a summary of this website
  * https://www.foxhound.systems/blog/final-tagless/ with the example written in
  * Scala.
  *
  * This is an example of tagged initial encoding. It is tagged because
  * SqlExprResult is used to streamlined the returned values. It is initial
  * encoding because eval has to perform pattern matching.
  *
  * Use GADT (Generalized Algebraic Data Type) to make it tag-less initial
  * encoding.
  */
sealed trait SqlExprResult
case class BoolResult(v: Boolean) extends SqlExprResult
case class IntResult(v: Int) extends SqlExprResult

sealed trait SqlExpr
case class I(v: Int) extends SqlExpr
case class B(v: Boolean) extends SqlExpr
case class Leq(expr1: SqlExpr, expr2: SqlExpr) extends SqlExpr
case class And(expr1: SqlExpr, expr2: SqlExpr) extends SqlExpr

// will cause runtime exception
def eval(a: SqlExpr): SqlExprResult = a match
  case I(a) => IntResult(a)
  case B(a) => BoolResult(a)
  case Leq(expr1, expr2) =>
    (eval(expr1), eval(expr2)) match
      case (IntResult(i1), IntResult(i2)) => BoolResult(i1 <= i2)
      case _ => throw Exception()
  case And(expr1, expr2) =>
    (eval(expr1), eval(expr2)) match
      case (BoolResult(i1), BoolResult(i2)) => BoolResult(i1 <= i2)
      case _ => throw Exception()

eval(Leq(I(10), I(11))) // BoolResult(true)

/** An example of tag-less initial encoding using GADT.
  *
  * {{{
  * sealed trait SqlExpr[A]
  * case class I(v: Int) extends SqlExpr[Int]
  * case class B(v: Boolean) extends SqlExpr[Boolean]
  * case class Leq(expr1: SqlExpr[Int], expr2: SqlExpr[Int]) extends SqlExpr[Boolean]
  * case class And(expr1: SqlExpr[Boolean], expr2: SqlExpr[Boolean]) extends SqlExpr[Boolean]
  *
  * def eval[A](a: SqlExpr[A]): A = a match
  *   case I(a) => a
  *   case B(a) => a
  *   case Leq(expr1, expr2) => eval(expr1) <= eval(expr2)
  *   case And(expr1, expr2) => eval(expr1) && eval(expr2)
  *
  * eval(Leq(I(10), I(11)))  // true
  * }}}
  */

/** This is an example of tag-less final.
  *
  * There is no tagging and in the final encoding. It is a final encoding
  * because it works in terms of the final representation instead of using an
  * intermediate type during evaluation.
  */
case class Expr[A](value: A)

def bool(b: Boolean) = Expr(b)
def int(i: Int) = Expr(i)
def leq(expr1: Expr[Int], expr2: Expr[Int]): Expr[Boolean] =
  Expr(expr1.value <= expr2.value)
def or(
    expr1: Expr[Boolean],
    expr2: Expr[Boolean]
): Expr[Boolean] = Expr(expr1.value || expr2.value)

def _eval[A](expr: Expr[A]): A = expr.value

_eval(leq(Expr(1), Expr(2))) // true
_eval(leq(Expr(2), Expr(1))) // false