scala - 如何在 Scala 中使我的不可变二叉搜索树通用？

Question

我是 Scala 的新手。我正在尝试开发自己的不可变二叉搜索树。

首先，我开发了一个二叉搜索树，其节点采用 Int。在那之后，我决定开发通用的二叉搜索树。

当我编译这些代码时，我从终端获取了这些错误信息。

trait GenericBST[+T] {

    def add[TT >: T](x: T): GenericBST[TT] = this match {
        case Empty => Branch(x, Empty, Empty)
        case Branch(d, l, r) => 
          if(d > x) Branch(d, l.add(x), r) 
          else if(d < x) Branch(d, l, r.add(x)) 
          else this   
    }
}

case class Branch[+T](x: T, left: GenericBST[T], right: GenericBST[T]) extends GenericBST[T]
case object Empty extends GenericBST[Nothing]

error: value < is not member of type paramater T.

错误是合理的，我该如何解决？

不要忘记我是 Scala 的新手，所以请为我详细解释一下。

Answer 1

T代表任何类型，但为了使用 >和 <您需要一种排序有意义的类型。

在 scala 中，这意味着你必须设置一个 T 类型的边界。 , 将其限制为所有 T为此 Ordering[T]存在。您可以使用上下文绑定(bind)，或者等效地需要隐式 ord类型 Ordering[TT] .

trait GenericBST[+A] {
  def add[B >: A](x: B)(implicit ord: Ordering[B]): GenericBST[B] = {
    import ord.mkOrderingOps
    this match {
      case Empty => Branch(x, Empty, Empty)
      case Branch(e, l, r) =>
        if (e > x) Branch(e, l.add(x), r)
        else if (e < x) Branch(e, l, r.add(x))
        else this
    }
  }
}

case class Branch[+A](x: A, left: GenericBST[A], right: GenericBST[A]) extends GenericBST[A]
case object Empty extends GenericBST[Nothing]

导入 ord.mkOrderingOps允许语法

e > x

代替

ord.gt(e, x)

---

您也可以直接使用上下文绑定(bind)，但需要一些额外的工作才能获得隐式 ord在范围内(并且可以说它的可读性较差):

def add[B >: A : Ordering](x: B): GenericBST[B] = {
  val ord = implicitly[Ordering[B]]
  import ord.mkOrderingOps
  ...
}

---

绝对不相关，但您可能想知道为什么我使用 A和 B在我的示例中，与 T 相对和 TT .根据official style guide :

For simple type parameters, a single upper-case letter (from the English alphabet) should be used, starting with A (this is different than the Java convention of starting with T)