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 ，其父类(super class)型为 Tree[Nothing] .先验地，这两种类型之间没有子类型关系。

您要的是Tree协变:如果X <: Y然后 Tree[X] <: Tree[Y] .然后，作为 Nothing <: A对于任何 A你得到 EmptyTree.type <: Tree[A]而且你可以随时通过EmptyTree每当您需要 Tree[A] .

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

这是一篇关于 Scala 协变和逆变的好文章:Be friend with covariance and contravariance

更新 在您的 questioning answer 之后我实际上已经查看了 Tree 的构造函数并且，根据定义，您 不能 制作 Tree协变。可悲的是，编译器不会提示(你看，它实际上应该提示更多)。您的 op在 Node在 Seq[A] 上是逆变的，因此您不能制作 Node协变。这时候你可能会想:

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

好吧，通过制作它的父类(super class)型 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]()案例类；遗憾的是没有无参数的值类。

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