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]) 

Now I want to define the binary search tree as:

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

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

Answer 1

The compilation error you get basically says that context boundaries cannot be used for type aliases. Context boundaries work in function or class definitions. For instance,

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

is an abbreviation for

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

Note that different BST objects can potentially have different Ordering s, and these values ​​should be stored at runtime.

For your use case, it’s easiest to associate the context with the main functions that you mean,

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

Then the corresponding Ordering[T] implicit will be found on the call site f , where type T is known.