How to express this existential type from Haskell in Scala?

Question

I am trying to adapt this Haskell implementation of the type classes based solution of the expression problem to Scala. My current code is below. I'm having problems expressing the existential type Exp in Scala.

How can I achieve the same thing?

object ExpressionProblem {

  // class Eval a where
  //   eval :: a -> Int
  trait Eval[A] {
    def eval(expr: A): Int
  }

  // data Exp = forall t. Eval t => Expr t
  sealed abstract class Exp
  case class Expr[T](val e: T)(implicit ev: Eval[T]) extends Exp

  // instance Eval Exp where
  //   eval (Expr e) = eval e
  implicit val exprInstance = new Eval[Exp] {
    def eval(expr: Exp) = expr match { case Expr(e, ev) => ev.eval(e) }
  }
  //                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  //                                       here is the problem

  // data BaseExp = Const Int | Add Exp Exp | Mul Exp Exp
  sealed abstract class BaseExpr
  case class Const(c: Int) extends BaseExpr
  case class Add(lhs: Exp, rhs: Exp) extends BaseExpr
  case class Mul(lhs: Exp, rhs: Exp) extends BaseExpr

  // instance Eval BaseExp where
  //   eval (Const n) = n
  //   eval (Add a b) = eval a + eval b
  //   eval (Mul a b) = eval a * eval b
  implicit val baseExprInstance = new Eval[BaseExpr] {
    def eval(baseExpr: BaseExpr)(implicit e: Eval[Exp]): Int =
      baseExpr match {
        case Const(c)      => c
        case Add(lhs, rhs) => e.eval(lhs) + e.eval(rhs)
        case Mul(lhs, rhs) => e.eval(lhs) + e.eval(rhs)
      }
  }

  // TODO: Is there an easier way to make all of them implicitly convertible?
  //
  // The following doesn't seem to work:
  //
  //    implicit def baseExprToExp[T <: BaseExpr](t: T): Exp = Expr[BaseExpr](t)
  //
  implicit def constToExp(c: Const): Exp = Expr[BaseExpr](c)
  implicit def addToExp(a: Add): Exp = Expr[BaseExpr](a)
  implicit def mulToExp(m: Mul): Exp = Expr[BaseExpr](m)

  ///////////////////////////////////////////////
  // Possibly in another module/lib.
  ///////////////////////////////////////////////

  // data SubExp = Sub Exp Exp
  case class SubExpr(val lhs: Exp, val rhs: Exp)

  // instance Eval SubExp where
  //   eval (Sub a b) = eval a - eval b
  implicit val subExprInstance = new Eval[SubExpr] {
    def eval(subExpr: SubExpr)(implicit e: Eval[Exp]): Int =
      e.eval(subExpr.lhs) - e.eval(subExpr.rhs)
  }

  // Make it implicitly convertible to Exp.
  implicit def subExprToExp(s: SubExpr): Exp = Expr(s)

  object Test {
    val exprs: List[Exp] = List(
      SubExpr(Const(10), Const(3)),
      Add(Const(1), Const(1))
    )
  }

} // ExpressionProblem

EDIT: Meanwhile I found this relevant StackOverflow answer and I adapted my code to it.

import scala.language.implicitConversions

object ExpressionProblem {

  // class Eval a where
  //   eval :: a -> Int
  trait Eval[A] {
    def eval(expr: A): Int
  }

  //////////////////////////////////////////
  // HERE'S THE MAGIC
  //
  // data Expr = forall t. Eval t => Expr t
  trait Expr {
    type T
    val t: T
    val evalInst: Eval[T]
  }

  object Expr {
    def apply[T0 : Eval](t0: T0) = new Expr {
      type T = T0
      val t = t0
      val evalInst = implicitly[Eval[T]]
    }
  }

  // Default boxing is needed
  implicit def box[T : Eval](t: T) = Expr(t)

  // instance Eval Expr where
  //   eval (Expr e) = eval e
  implicit object exprInstance extends Eval[Expr] {
    def eval(expr: Expr) = expr.evalInst.eval(expr.t)
  }

  // data BaseExpr = Const Int | Add Expr Expr | Mul Expr Exp
  sealed abstract class BaseExpr
  case class Const(c: Int) extends BaseExpr
  case class Add(lhs: Expr, rhs: Expr) extends BaseExpr
  case class Mul(lhs: Expr, rhs: Expr) extends BaseExpr

  // instance Eval BaseExpr where
  //   eval (Const n) = n
  //   eval (Add a b) = eval a + eval b
  //   eval (Mul a b) = eval a * eval b
  implicit object baseExprInstance extends Eval[BaseExpr] {
    def eval(baseExpr: BaseExpr): Int =
      baseExpr match {
        case Const(c)      => c
        case Add(lhs, rhs) => exprInstance.eval(lhs) + exprInstance.eval(rhs)
        case Mul(lhs, rhs) => exprInstance.eval(lhs) + exprInstance.eval(rhs)
      }
  }

  // Implicit conversions for all base expressions
  implicit def baseExprToExpr[T <: BaseExpr](t: T): Expr = Expr[BaseExpr](t)

  ///////////////////////////////////////////////
  // Possibly somewhere else (in the future).
  ///////////////////////////////////////////////

  // data SubExpr = Sub Expr Exp
  case class SubExpr(val lhs: Expr, val rhs: Expr)

  // instance Eval SubExpr where
  //   eval (Sub a b) = eval a - eval b
  implicit object subExprInstance extends Eval[SubExpr] {
    def eval(subExpr: SubExpr): Int =
      exprInstance.eval(subExpr.lhs) - exprInstance.eval(subExpr.rhs)
  }

  // NOTE: We don't have to provide an implicit conversion to Expr as the
  // default `box` one suffices.

  object Test {
    val exprs: List[Expr] = List(
      SubExpr(Const(10), Const(3)),
      Add(Const(1), Const(1))
    )
  }

} // ExpressionProblem

Answer 1

Your problem is that you are using an extractor (unapply), but neglecting the fact that implicits are not by default exposed as part of unapply.

So this line:

def eval(expr: Exp) = expr match { case Expr(e, ev) => ev.eval(e) }

There is no case Expr(e, ev), only case Expr(e), because only e is exposed. Either write a custom extractor or find a different approach.

Scala does offer existential types of the form:

Expr[T] forSome { type T})

That has a shorthand type notation available: Expr[_]

Your code has a few more issues though:

If you define an implicit on eval, all implementors must implement an eval function with that particular signature, you can't override eval with an implementation that doesn't contain the implicit in the signature like you do in.

 implicit val baseExprInstance = new Eval[BaseExpr] {
    def eval(baseExpr: BaseExpr)(implicit e: Eval[Exp]): Int =
      baseExpr match {
        case Const(c)      => c
        case Add(lhs, rhs) => e.eval(lhs) + e.eval(rhs)
        case Mul(lhs, rhs) => e.eval(lhs) + e.eval(rhs)
      }
  }

Next up you are going to need to either make T on Expr contravariant or make SubExpr also extend Exp, you have a problem here:

  // instance Eval SubExp where
  //   eval (Sub a b) = eval a - eval b
  implicit val subExprInstance = new Eval[SubExpr] {
    def eval(subExpr: SubExpr)(implicit e: Eval[SubExpr]): Int =
      e.eval(subExpr.lhs) - e.eval(subExpr.rhs)
  }

If you will try to match the type signature, implicit e: Eval[SubExpr] can eval types that are T >: SubExpr, but what you require is a lower Exp implicit for Eval.