Parametrised data type in Scala

Question

While reading the article "Data types a la carte" by Wouter Swierstra, I've got stuck at translating the following Haskell code into Scala:

data Expr f = In (f (Expr f ))

Expr is the data type used for representing arithmetic expressions in the way that specific expressions can be written as follows:

data Val e = Val Int
type IntExpr = Expr Val

data Add e = Add e e
type AddExpr = Expr Add

My problem is in implementing f (which might be thought of as the signature of the constructor) in Scala.

P.S. Defining a coproduct of two signatures, you can later on combine data types, getting an expression of type Expr (Val :+: Add ):

data (f :+: g) e = Inl (f e) | Inr (g e)

addExample :: Expr (Val :+: Add )
addExample = In (Inr (Add (In (Inl (Val 118))) (In (Inl (Val 1219)))))

Answer 1

Perhaps something like

case class Expr[f[_]] (in : f [Expr[f]])

This is not as useful as in Haskell though. Suppose you define

case class Val[e] (v: Int)

Then Val(3) will have a type of Val[Nothing], and you cannot use it with Expr.

scala> val e = Expr(Val(3))               
<console>:9: error: no type parameters for method apply: 
(in: f[Expr[f]])Expr[f] in object Expr exist so that it can be applied 
to arguments (Val[Nothing])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : Val[Nothing]
 required: ?f[ Expr[?f] ]
       val e = Expr(Val(3))

You may still specify the type explicitly

val e = Expr(Val(3):Val[Expr[Val]])

but this is no fun. You of course can define a function of the right type and use it instead of Val.

Note that I'm still a Scala noob and perhaps there's a more elegant method.

Answer 2

I've suddenly found this blogpost that provides some good explanations on translating "Data types a la carte" into Scala. Proposed solution looks as follows:

case class Val[E](i: Int)
case class Add[E](left: E, right: E)

case class Expr[F[X]](e: F[Expr[F]])

sealed trait Sum[F[X], G[X], E]
case class Inl[F[X], G[X], E](l: F[E]) extends Sum[F,G,E]
case class Inr[F[X], G[X], E](r: G[E]) extends Sum[F,G,E]

trait Apply2Of3[F[A[_],B[_],_],A[_],B[_]] {
        type It[C] = F[A,B,C]
}

type Tmp[X] = Apply2Of3[Sum,Val,Add]#It[X]

val addExample: Expr[Tmp] = In[Tmp](Inr(Add(In[Tmp](Inl(Val(118))), In[Tmp](Inl(Val(1219))))))

It is far not as sweet as the original one (made in Haskell), but quite useful in the sense that 1) it demonstrates that it's generally possible to implement the idea in Scala, and 2) brings up some weaknesses of Scala compared to Haskell.