Scala 的排序和无

Question

Scala 的 Ordered trait 被描述了，所以我们必须使用 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]]并且效果很好。

Answer 1

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

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

你的 mkTree 方法需要一个 (implicit ord: Ordering[A]) 参数，但我不明白这个方法有什么用 - 它看起来像一个属于伴生对象的工厂方法(它确实如此，因为您只是遵从 Branch 对象)- 所以我会删除它。