How can I create a generic binary search tree in Scala?
I am new to Scala. I am trying to develop my own immutable binary search tree.
First, I have developed a binary search tree that occupies Int
on its nodes. After that, I decided to develop a generic binary search tree.
When I compiled these codes, I took this error message from the terminal.
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 a member of type paramater T.
The error is reasonable, how can I fix it?
Don't forget that I'm new to Scala, so please explain this in detail for me.
source to share
T
represents any type, but to use it >
and <
you need a type for which the order makes sense.
In scala words, this means that you need to put a type boundary T
, limiting it to whatever it T
exists for Ordering[T]
. You can use a bound context or an implicit ord
type respectively 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]
Import ord.mkOrderingOps
allows syntax
e > x
instead
ord.gt(e, x)
You can also use context binding directly, but getting the implicit ord
in scope (and possibly less readable) will take some extra work:
def add[B >: A : Ordering](x: B): GenericBST[B] = {
val ord = implicitly[Ordering[B]]
import ord.mkOrderingOps
...
}
Absolutely not relevant, but you might be wondering why I used A
and B
in my example, as opposed to T
and TT
. According to the official style guide :
Simple type parameters should use a single uppercase letter (from the English alphabet) starting with
A
(this differs from the Java convention of starting withT
)
source to share