Scala 正确定义抽象数据类型的空值

Question

我有一个ADT，如下所示：

sealed trait Tree[A]
case object EmptyTree extends Tree[Nothing]
case class Leaf[A](value: A) extends Tree[A]
case class Node[A](op: Seq[A] => A, branches: Tree[A]*) extends Tree[A]

当我尝试构建一个函数来随机创建树时，我遇到了 EmptyTree 的问题，类型系统不会通过

def create(acc: Tree[A], currentDepth: Int): Tree[A] = currentDepth match {
case maxDepth => Leaf(terminalSet(r.nextInt(terminalSet.length)))
case 0 => {
val op_pos = r.nextInt(fSetLength)
val branches: Seq[Tree[A]] = for (i <- 0 to r.nextInt(fSetLength)) yield create(EmptyTree, currentDepth+1)
Node(functionSet(op_pos)._1, branches:_*)
}
case _ => {
if (r.nextFloat() <= probF) {
val op_pos = r.nextInt(fSetLength)
val branches = for (i <- 0 to r.nextInt(fSetLength)) yield create(EmptyTree, currentDepth + 1)
Node(functionSet(op_pos)._1, branches:_*)
}
else
Leaf(terminalSet(r.nextInt(terminalSet.length)))
}
}
create(EmptyTree, 0) 

基本上在create(EmptyTree, currentDepth + 1)，它抱怨它期待Tree[A]并正在接受EmptyTree.type

Answer 1

编译器的反对意见是合理的。编译器期望Tree[A]，而您正在传递EmptyTree，其超类型为Tree[Nothing]。先验地，这两种类型之间没有子类型关系。

你想要的是Tree协变：如果X <: Y则Tree[X] <: Tree[Y]。然后，对于任何ANothing <: A，您都会得到EmptyTree.type <: Tree[A]，并且您可以随时通过EmptyTreeTree[A]。

在协变Tree中声明A参数的语法是Tree[+A];更改它，你的代码应该编译。

这是一篇关于 Scala 中协方差和逆变的好文章：与协方差和逆变做朋友

更新在您的提问答案之后，我实际上已经查看了您的构造函数以获取Tree，并且根据定义，您不能使Tree协变。可悲的是，编译器不会抱怨(你看，它实际上应该抱怨更多)。你在Node中的op在Seq[A]上是逆变的，因此你不能使Node协变。此时您可能会想：

谁在乎Node？我只想Tree是协变的！

好吧，通过使其超类型Tree协变节点在实践中变得如此。scalac实际上应该检查协变的所有子类型构造函数是否都是(或可以制作)协变的。无论如何，显示以下内容的代码如下：

// you need a value for EmptyTree! thus default
def evaluateTree[Z](tree: Tree[Z], default: Z): Z =
tree match {
case EmptyTree    => default
case Leaf(value)  => value
// note how you need to essentially cast here
case Node(op: (Seq[Z] => Z), args @ _*) =>
op(args map { branches => evaluateTree(branches, default) })
}
trait A
trait B extends A
val notNice: Tree[A] = Node[B]({ bs: Seq[B] => bs.head }, EmptyTree)
// ClassCastException!
val uhoh = evaluateTree(notNice, new A {})

更新 2回到你原来的问题:)我会保留您的Tree类型不变，并有一个EmptyTree[A]()案例类;遗憾的是没有无参数值类。

sealed trait Tree[A]
case class EmptyTree[A]() extends Tree[A]
case class Leaf[A](value: A) extends Tree[A]
// I wouldn't use varargs here, make a method for that if you want
case class Node[A](op: Seq[A] => A, branches: Tree[A]*) extends Tree[A]
// for convenience, it could be inside `Tree` companion
def emptyTree[A]: EmptyTree[A] = EmptyTree()
def evaluateTree[Z](tree: Tree[Z], default: Z): Z =
tree match {
case EmptyTree() =>
default
case Leaf(value) =>
value
// no need to match generic types or anything here
case Node(op, args @ _*) =>
op(args map { branches => evaluateTree(branches, default) })
}
trait A
trait B extends A
// doesn't work now
// val notNice: Tree[A] = Node[B]({ bs: Seq[B] => bs.head }, emptyTree)
val notNice: Tree[B] = Node[B]({ bs: Seq[B] => bs.head }, emptyTree)
// doesn't compile, no class cast exception
// val uhoh = evaluateTree(notNice, new A {})