Type aliasing ordered generics in Scala

Question

I have a minimal definition of what a binary tree should look like:

type Tree[T] = Option[Node[T]]
case class Node[T](left: Tree[T], entry: T, right: Tree[T])

I now want to define a binary search tree as:

type BST[T: Ordering] = Tree[T] 

but that does not compile. What am I doing wrong?

Answer 1

The compile error you're getting basically says that context bounds cannot be used for type aliases. Context bounds do work in function or class definitions. For example,

class BST[T: Ordering](val tree: Tree[T])

is actually shorthand notation for

class BST[T](val tree: Tree[T])(implicit ordering: Ordering[T])

Note that different BST objects could potentially have different Orderings, and those values must be stored at runtime.

For your use case, the easiest thing might be to put the context bound on the generic functions you have in mind,

def f[T: Ordering](t1: Tree[T], t2: Tree[T]) {
  import scala.math.Ordering.Implicits._
  t1.get.entry < t2.get.entry
}

Then the appropriate Ordering[T] implicit will be found at the call site of f, where the type T is known.