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)它抱怨它期待a Tree[A]并且正在接收aEmptyTree.type

Answer 1

编译器异议是合理的.编译器期望Tree[A]并且您正在传递EmptyTree,其超类型是Tree[Nothing].先验地,这两种类型之间没有子类型关系.

你需要的是Tree被协变:如果X <: Y然后Tree[X] <: Tree[Y].然后,Nothing <: A对于任何 A你EmptyTree.type <: Tree[A],你可以随时通过EmptyTree每当你需要一个Tree[A].

在协变中声明参数的语法是; 改变它,你的代码应该编译.ATreeTree[+A]

这是关于Scala的协方差和逆变的好帖子:是有协方差和逆变的朋友

更新在你的质疑回答后,我实际上已经看过你的构造函数,Tree并且根据定义,你不能进行Tree协变.可悲的是,编译器不会抱怨(你看,它实际上应该抱怨更多).你的opin Node是逆变的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 {})