如何在 Scala 中从 Haskell 表达这种存在类型？

Question

我正在努力使 this Haskell implementation of the type classes based solution of the expression problem 适应 Scala。我当前的代码如下。我在 Scala 中表达存在类型 Exp 时遇到问题。

我怎样才能达到同样的效果？

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

编辑：与此同时，我找到了这个relevant Whosebug答案，并根据它修改了我的代码。

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

Answer 1

您的问题是您正在使用提取器 (unapply)，但忽略了默认情况下隐式不作为 unapply 的一部分公开的事实。

所以这一行：

def eval(expr: Exp) = expr match { case Expr(e, ev) => ev.eval(e) }

没有case Expr(e, ev)，只有case Expr(e)，因为只暴露了e。编写自定义提取器或寻找不同的方法。

Scala 确实提供以下形式的存在类型：

Expr[T] forSome { type T})

有 shorthand 可用的类型表示法：Expr[_]

您的代码还有一些问题：

如果您在 eval 上定义 implicit，所有实现者都必须使用该特定签名实现 eval 函数，您不能使用实现覆盖 eval不像你在签名中那样包含隐含的签名。

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

接下来你需要在 Expr 上使 T 逆变或者使 SubExpr 也扩展 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[SubExpr]): Int =
      e.eval(subExpr.lhs) - e.eval(subExpr.rhs)
  }

如果您尝试匹配类型签名，implicit e: Eval[SubExpr] 可以评估 T >: SubExpr 类型，但您需要的是 Eval 的较低 Exp 隐式.

如何在 Scala 中从 Haskell 表达这种存在类型？

How to express this existential type from Haskell in Scala?

scala

haskell

typeclass

existential-type