Hi stackoverflow.
Having a background in Haskell I am currently trying to get familiar with Scala.
I encountered some problems trying to translate a small, extensible expression language from Haskell into Scala. The underlying issue of writing a data type that is extensible with both new data-variants and operations is commonly known as the expression problem.
My original solution in Haskell uses type classes and instance declarations with constraints. The base of my expression is defined as follows:
module Expr where
class Expr e where
eval :: e -> Integer
data Lit = Lit Integer
instance Expr Lit where
eval (Lit l) = l
data Plus a b = (Expr a, Expr b) => Plus a b
instance (Expr a, Expr b) => Expr (Plus a b) where
eval (Plus x y) = (eval x) + (eval y)
Then, I have one data-extension that adds multiplication:
module ExprWithMul where
import Expr
data Mul a b = (Expr a, Expr b) => Mul a b
instance (Expr a, Expr b) => Expr (Mul a b) where
eval (Mul x y) = (eval x) * (eval y)
Let's take a pretty-printer as an operational extension:
module FormatExpr where
import Expr
class (Expr t) => FormatExpr t where
format :: t -> String
instance FormatExpr Lit where
format (Lit l) = show l
instance (FormatExpr a, FormatExpr b) => FormatExpr (Plus a b) where
format (Plus x y) = "(" ++ (format x) ++ "+" ++ (format y) ++ ")"
And, finally, in the fourth module the two independent extensions can be combined:
module FormatExprWithMult where
import FormatExpr
import ExprWithMul
instance (FormatExpr a, FormatExpr b) => FormatExpr (Mul a b) where
format (Mul x y) = "(" ++ (format x) ++ "*" ++ (format y) ++ ")"
Now for my problem: Usually type classes from haskell are translated to the concept-pattern with implicits in Scala. This is how far I got:
abstract class Expr[A] { // this corresponds to a type class
def eval(e:A): Int;
}
case class Lit(v: Int)
implicit object ExprLit extends Expr[Lit] {
def eval(e: Lit) = x.v;
}
case class Plus[A,B] (e1: A, e2: B) (implicit c1: Expr[A], c2: Expr[B])
Here I am stuck with implementing the implicit object for Plus. How do I declare an implicit object with type parameters and constraints?
I know that there are other solution for the expression problem in Scala, I am however interested in this version in particular.
Thank you all for reading my somewhat lengthy question.