Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // The expression problem is a new name for an old problem. The goal is to
- // define a datatype by cases, where one can add new cases to the datatype and
- // new functions over the datatype, without recompiling existing code, and while
- // retaining static type safety (e.g., no casts).
- // (Philip Wadler)
- import scala.language.implicitConversions
- object ExpressionProblem extends App {
- // 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(e: Expr) = e.evalInst.eval(e.t)
- }
- // NOTE: Haskell's name lookup makes this unnecessary; however, in order to
- // avoid explicitly specifying `exprInstance.eval` each time when we call it
- // recursively, simply define an alias.
- def evaluate = exprInstance.eval _
- // 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) => evaluate(lhs) + evaluate(rhs)
- case Mul(lhs, rhs) => evaluate(lhs) + evaluate(rhs)
- }
- }
- // Implicit conversions for all base expressions
- //
- // NOTE: This is only needed because we created a new hierarchy instead of
- // enrolling each type to `Eval` on its own. Otherwise, the boxing function
- // would suffice.
- implicit def baseExprToExpr[T <: BaseExpr](t: T): Expr = Expr[BaseExpr](t)
- ///////////////////////////////////////////////
- // Possibly somewhere else (other module/lib).
- ///////////////////////////////////////////////
- // 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 =
- evaluate(subExpr.lhs) - evaluate(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))
- )
- }
- // Just sanity checking, they are not pretty Show-able.
- println(Test.exprs)
- } // ExpressionProblem
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement