3

Scala 的Orderedtrait 被贬低了，所以我们必须使用Ordering. 我试图重写我的 BST 类以使用Ordering并得到一个编译错误。谁能解释一下如何Ordering正确使用Nothing。这是我的代码：

abstract sealed class Tree[+A: Ordering] {
  def value: A
  def left: Tree[A]
  def right: Tree[A]
  def isEmpty: Boolean

 /**
  * Time - O(1)
  * Space - O(1)
  */
 def mkTree(v: A, l: Tree[A] = Leaf, r: Tree[A] = Leaf): Tree[A] = 
   Branch(v, l, r)

 /**
  * Fails with message.
  */
 def fail(s: String): Nothing =
   throw new NoSuchElementException(s)
}

case object Leaf extends Tree[Nothing] {
  def value: Nothing = fail("Empty tree.")
  def left: Tree[Nothing] = fail("Empty tree.")
  def right: Tree[Nothing] = fail("Empty tree.")
  def isEmpty: Boolean = true
}

case class Branch[A: Ordering](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] {
  def isEmpty: Boolean = false
}

编译时我得到以下信息：

Tree.scala:21: error: No implicit Ordering defined for Nothing.
case object Leaf extends Tree[Nothing] {
             ^
   one error found

我曾经写过这个类abstract class Tree[+A <% Ordered[A]]，它工作得很好。

4

2 回答 2

3

我认为问题不在于Ordering您设置树的方式。错误消息是不言自明的：您已经说过 type 参数应该有一个隐式排序，但是在Leaf您给它的情况下 type parameter Nothing，它没有排序。

所以我会说每个Tree人都有订购的要求是不正确的。您需要做的就是: Ordering从您的第一行中删除该问题，因为您已经将该要求包含在Branch其中，它确实有意义。

你的mkTree方法需要一个(implicit ord: Ordering[A])参数，但我看不出这个方法有什么用途——它看起来像一个属于伴随对象的工厂方法（它确实如此，因为你只是服从 Branch 对象）——所以我会去掉它。

于 2013-09-01T20:39:40.530 回答
2

Luigi 是正确的，该顺序对 Tree 类型没有意义。但是，如果使用Algebraic Data Type，此要求会更明显，并且设计会更简洁。它们使用类层次结构作为接口的一部分，因此它们比面向对象（如 Scala 中的 Option 和 List）更具功能性。

然后，您直接使用案例类来实例化它们（不需要 mkTree 函数），并使用模式匹配来检索它们。

例如：

sealed trait Tree[+A] {
  def isEmpty: Boolean
}

case object Leaf extends Tree[Nothing] {
  def isEmpty: Boolean = true
}

case class Branch[+A: Ordering](value: A, left: Tree[A] = Leaf, right: Tree[A] = Leaf) extends Tree[A] {
  def isEmpty: Boolean = false
}

def depthFirstSearch[A: Ordering](tree: Tree[A], expected: A): Option[Branch[A]] = {
  import Ordering.Implicits._

  tree match {
    case t @ Branch(value, _, _) if value == expected => Some(t)
    case Branch(value, left, _) if value > expected => depthFirstSearch(left, expected)
    case Branch(value, _, right) if value < expected => depthFirstSearch(right, expected)
    case _ => None
  }
}
于 2013-09-02T14:09:24.420 回答