如何在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 <不是类型参数t的成员>

错误是合理的，我该如何修复它?

别忘了我是Scala的新手，所以请为我详细解释一下。

Answer 1

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

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

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)

---

您也可以直接使用上下文绑定，但这需要一些额外的工作来获得作用域内的隐式ord(并且它可能不太可读):

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

---

绝对不相关，但你可能想知道为什么我在我的例子中使用A和B，而不是T和TT。根据官方风格指南:

对于简单的类型参数，应该使用单个大写字母(来自英文字母表)，以A开头(这与以T开头的Java惯例不同)