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]。然后，作为 Nothing <: A for any A 你得到 EmptyTree.type <: Tree[A] 并且你总是可以在需要 [=12= 时传递 EmptyTree ].

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

这是一篇很好的 post Scala 中的协变和逆变：Be friend with covariance and contravariance

UPDATE 在你的 questioning answer 之后，我实际上已经查看了你的 Tree 的构造函数，并且根据定义，你不能使 Tree 协变。可悲的是，编译器不会抱怨（你看，它实际上应该抱怨 more）。 Node 中的 op 在 Seq[A] 上是逆变的，因此你不能使 Node 协变。此时你可能会想：

Who cares about Node? I just want Tree to be covariant!

Well，通过使其超类型 Tree 协变 Node 在实践中变得如此。 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]() 案例 class;可惜没有无参值classes.

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

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

scala properly defining a empty value for a abstract data type

generics

scala

abstract-data-type

covariance

abstract-syntax-tree