Tagless final vs tagless initial vs tagged initial

readme.md

Tagless Final Summary

I create this gist to summarize my understanding on tagless final that I read in the article A "quick" introduction to Tagless Final.

Tagless

The first word "Tagless" makes reference to the return types that are not tagged or grouped using GADT, ADT or union types, Int | String. Yet. the return types can be "anything".

Final

Initial encoding uses ADT etc. to encode the expressions, Then use an interpretor to evaluate the expressions. On the other hand, final encoding uses functions to model the expression. With functions, tags and interpretors are not required.

However, there is a catch. The functions accept the same parameter types but the return types are different from case to case even though the intend is the same.

For example, the function add(x: Int, y: Int): Int return type for this case is an Int but in another case it could return String and yet we cannot change the function parameter and return types. Using higher kind type (HKT) is the solution.

The HKT Solution

Hence, the function declaration becomes add[F[_]](x: F[Int], y: F[Int]): F[Int]. Manipulate F[_] to get the required return types, type Pretty[A] = String or type Eval[A] = A, as shown in the worksheet.

Tagged Initial Is ADT And Tagless Initial Is GADT

GADT is tagless because the return type is the final value type. Unlike ADT, further processing using pattern matching is not required. However, it does not solve the expression problem because GADT and ADT cannot accept new types later in the code.

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 a code example of tagless final implementation.
 *
 * There is no tagging using GADT and in the final encoding
 * it uses the functions instead of using an interpreter 
 * with tags. Threfore, there is no intermediate evaluation
 * state
 */

trait Foo[F[_]]:
  def lit(i: Int): F[Int]
  def add(x: F[Int], y: F[Int]): F[Int]
  def isEq(x: F[Int], y: F[Int]): F[Boolean]
  def or(x: F[Boolean], y: F[Boolean]): F[Boolean]

object Foo:
  def apply[F[_]: Foo]: Foo[F] = summon[Foo[F]]
  
object ExampleFooPrettyPrint:
  type Pretty[A] = String

  given Foo[Pretty]:
    override def lit(i: Int): Pretty[Int] = i.toString
    override def add(x: Pretty[Int], y: Pretty[Int]): Pretty[Int] = s"""($x + $y)"""
    override def isEq(x: Pretty[Int], y: Pretty[Int]): Pretty[Boolean] = s"""($x == $y)"""
    override def or(x: Pretty[Boolean], y: Pretty[Boolean]): Pretty[Boolean] = s"""($x or $y)"""

  def apply(): Unit =
    def ppBoolean[F[_]: Foo]: F[Boolean] = {
      val foo = Foo[F]
      import foo.*
      
      isEq(add(lit(0), lit(3)), add(lit(1), lit(2)))
    }

    println(ppBoolean)  // ((0 + 3) == (1 + 2))

  def ppInt[F[_]: Foo]: F[Int] =
    val foo = Foo[F]
    import foo.*

    add(lit(3), add(lit(1), lit(2)))

  println(ppInt)     // (3 + (1 + 2))

ExampleFooPrettyPrint()

object ExampleFooEval:
  type Eval[A] = A

  given Foo[Eval]:
    override def lit(i: Int): Eval[Int] = i
    override def add(x: Eval[Int], y: Eval[Int]): Eval[Int] = x + y
    override def isEq(x: Eval[Int], y: Eval[Int]): Eval[Boolean] = x == y
    override def or(x: Eval[Boolean], y: Eval[Boolean]): Eval[Boolean] = x || y

  def apply(): Unit =
    def evalBool[F[_]: Foo]: F[Boolean] =
      val foo = Foo[F]
      import foo.*

      isEq(add(lit(0), lit(3)), add(lit(1), lit(2)))

    println(evalBool) // true

  def evalInt[F[_]: Foo]: F[Int] =
    val foo = Foo[F]
    import foo.*

    add(lit(3), add(lit(1), lit(2)))

  println(evalInt)  // 6

ExampleFooEval()

// additional function on top of Foo
trait Bar[F[_]]:
  def mul(x: F[Int], y: F[Int]): F[Int]

object Bar:
  def apply[F[_]: Bar]: Bar[F] = summon[Bar[F]]

object ExampleBarEval:
  import ExampleFooEval.*
  import ExampleFooEval.given
  
  given Bar[Eval]:
    override def mul(x: Eval[Int], y: Eval[Int]): Eval[Int] = x * y

  def evalMultAdd[F[_] : {Bar, Foo}]: F[Int] =
    val bar = summon[Bar[F]]
    import bar.*

    val foo = Foo[F]
    import foo.*

    mul(add(lit(1), lit(2)), ExampleFooEval.evalInt)

  def apply(): Unit =
    println(evalMultAdd)  // 18
    
ExampleBarEval() 

TLDR;
tagged initial => Use ADT
tagless initial => Use GADT
tagless final => Use typeclass and HKT