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
