Scala为抽象数据类型正确定义一个空值 [英] scala properly defining a empty value for a abstract data type

问题描述

我的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]

当我尝试构建随机创建Trees的函数时，我得到了一个EmptyTree问题，类型系统不允许通过

When i try to build a function to randomly create Trees i get a problem with the EmptyTree, the type system does not let go through

  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

basically in create(EmptyTree, currentDepth + 1) it complains that it is expecting a Tree[A] and is receiving a EmptyTree.type

推荐答案

编译器的反对是有道理的。编译器期望 Tree [A] ，并且您正在传递 EmptyTree ，其超级类型为 Tree [没什么] 。先验地，这两种类型之间没有子类型关系。

The compiler objections are justified. The compiler expects Tree[A] and you are passing EmptyTree, whose super type is Tree[Nothing]. A priori, there's no subtyping relationship between these two types.

您想要的是树成为协变量：如果 X <：Y ，则 Tree [X]< ;: Tree [Y] 。然后，作为 Nothing< ;: A 表示 any A ，您将得到 EmptyTree.type< ;： Tree [A] ，只要需要 Tree，您总是可以传递 EmptyTree 。 A] 。

What you want is Tree to be covariant: if X <: Y then Tree[X] <: Tree[Y]. Then, as Nothing <: A for any A you get EmptyTree.type <: Tree[A] and you can always pass EmptyTree whenever you need a Tree[A].

语法用于声明 A Tree 协变量中的参数为 Tree [+ A] ;

The syntax for declaring the A parameter in Tree covariant is Tree[+A]; change that and your code should compile.

这是有关Scala中协方差和协方差的好文章：成为协方差和相反方的朋友

This is a good post on covariance and contravariance in Scala: Be friend with covariance and contravariance

更新，在您提出问题的答案之后，我实际上在看您的树，并且根据定义，您不能使树协变。可悲的是，编译器不会抱怨（您会看到，它实际上应该抱怨 more ）。您在节点中的 op 在 Seq [A] 上是相反的，因此您不能使 Node 成为协变量。此时，您可能会想：

UPDATE After your questioning answer I have actually looked at your constructors for Tree and, as defined, you cannot make Tree covariant. Sadly, the compiler won't complain (you see, it should actually complain more). Your op in Node is contravariant on Seq[A], and thus you cannot make Node covariant. At this point you might be thinking:

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

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

Well ，通过使其超型 Tree 实际上，协变节点变得如此。 scalac 实际上应该检查协变变量的所有子类型构造函数都是（或可以使）协变变量。无论如何，显示此代码的代码如下：

Well, through making its supertype Tree covariant Node becomes so in practice. scalac should actually check that all sub type constructors of a covariant one are (or could be made) covariant. Anyway, code showing this follows:

// 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]（）案例类；遗憾的是，没有无参数的值类别。

UPDATE 2 Back to your original question :) I'd leave your Tree type invariant, and have an EmptyTree[A]() case class; it is a pity that there are no parameterless value 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为抽象数据类型正确定义一个空值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！