斯卡拉正确定义一个抽象数据类型

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为任何A你得到EmptyTree.type <: Tree[A]，你可以随时通过EmptyTree，只要你需要一个Tree[A]。

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

这是一个很好的职位上协方差和逆变Scala中：Be friend with covariance and contravariance

UPDATE你questioning answer后，其实我已经看了你的构造函数Tree和定义，你不能使Tree协变。不幸的是，编译器不会抱怨（你看，它实际上应该抱怨更多）。您的op在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 {})