使用默认值时 AN => Ordered[A] 没有可用的隐式视图

Question

我正在 Scala 中实现简单的 BST（基于泛型）。我已经实现了抽象 class:

abstract class MyTree[A <% Ordered[A]]() .....

和子class节点

case class Node[A <% Ordered[A]](v: A, left: MyTree[A] = Leaf[A], right: MyTree[A] = Leaf[A]) extends MyTree[A] .....

还有一个叶子案例 class 代表我的树的空叶子。我想没关系，所以我不会 post 它的代码在这里。问题是我得到一个错误：

No implicit view available from A => Ordered[A]. case class Node[A <% Ordered[A]](v: A, left: MyTree[A] = Leaf[A], right: MyTree[A] = Leaf[A]) extends MyTree[A]

当我将 <% 更改为 <: 时，一切正常，除了我想将我的 BST 与 Int 作为类型（不是有序的）一起使用。我也知道问题的根源可能是我分配给左边和右边的默认值 (Leaf[A])。我该如何解决？为什么会出现这个错误？

Answer 1

如果没有实际代码，很难评估您的隐式函数 A => Ordered[A] 在哪一点缺失。

但无论如何我都建议不要使用 Ordered[A] 的转换，而是使用单独的类型 class Ordering[A]。使用它，您不需要实际转换元素类型，但您有一个提供排序操作的实例。我想不出我更喜欢 Ordered 而不是 Ordering 的情况。

我还建议不要在抽象类型中使用构造函数参数（MyTree 在您的情况下）。最好定义一个抽象成员。例如：

sealed trait MyTree[-A] {
  def contains(x: A): Boolean
}

case class Leaf[A](v: A) extends MyTree[A] {
  def contains(x: A): Boolean = x == v
}

case object Empty extends MyTree[Any] {
  def contains(x: Any): Boolean = false
}

case class Node[A](v: A, left: MyTree[A], right: MyTree[A])
                  (implicit val ordering: Ordering[A])
  extends MyTree[A] {

  def contains(x: A): Boolean = x == v || {
    import Ordering.Implicits._   // nice operator syntax
    (if (x < v) left else right).contains(x)
  }
}

val t = Node(5, Node(3, Leaf(1), Empty), Leaf(8))
(0 to 9).map(t.contains) // F T F T F T F F T F

（这里 MyTree 类型中的反方差 -A 允许将 Empty 定义为单例对象，但您也可以坚持不变量 A )

使用默认值时 AN => Ordered[A] 没有可用的隐式视图

No implicit view avaliable from A => Ordered[A] while using default values

scala

view

implicit

binary-search-tree