Параметрированный тип данных в Scala

При чтении статьи "Типы данных a la carte" Wouter Swierstra, я застрял в переводе следующего кода Haskell на Scala:

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

Expr - это тип данных, используемый для представления арифметических выражений таким образом, что конкретные выражения могут быть записаны следующим образом:

data Val e = Val Int
type IntExpr = Expr Val

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

Моя проблема заключается в реализации f (который может считаться сигнатурой конструктора) в Scala.

P.S. Определяя копроизведение двух подписей, вы можете позже комбинировать типы данных, получая выражение типа 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)))))

Ответы

Ответ 1

Возможно, что-то вроде

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

Это не так полезно, как в Haskell. Предположим, вы определили

case class Val[e] (v: Int)

Тогда Val(3) будет иметь тип Val[Nothing], и вы не сможете использовать его с 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 type is not compatible with formal parameter type;
 found   : Val[Nothing]
 required: ?f[ Expr[?f] ]
       val e = Expr(Val(3))

Вы можете указать явно тип

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

но это не весело. Вы, конечно, можете определить функцию правильного типа и использовать его вместо Val.

Обратите внимание, что я все еще Scala noob и, возможно, более элегантный метод.

Ответ 2

Я неожиданно обнаружил это blogpost, в котором содержатся некоторые полезные объяснения по переводу "Типы данных a la carte" в Scala. Предлагаемое решение выглядит следующим образом:

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))))))

Это далеко не так сладко, как оригинал (сделанный в Haskell), но весьма полезный в том смысле, что 1) он демонстрирует, что вообще возможно реализовать идею в Scala и 2) вызывает некоторые недостатки Scala по сравнению с Haskell.