Compilation error with Ordered in Scala

Question

I'm having some trouble implementing an immutable BST in Scala. The problem seems to be that by some reason although I've defined K to be as Ordered[K] (2nd line), it actually is being considered by the Scala compiler to be an Any. Why?

abstract class BST
sealed case class Node[K <: Ordered[K], V](key : K, value : V, left : BST, right : BST) extends BST
sealed case class Empty() extends BST

object BST {
  def empty = Empty()

  def add[K <: Ordered[K], V](key : K, value : V, tree : BST) : BST = tree match {
    case Empty() => new Node(key, value, Empty(), Empty())
    case Node(nodeKey, nodeValue, left, right) =>
      if (key < nodeKey) new Node(nodeKey, nodeValue, add(key, value, left), right)
      else if (key > nodeKey) new Node(nodeKey, nodeValue, left, add(key, value, right))
      else new Node(key, value, left, right)
  }

score 1 · Answer 1 · answered Sep 15 '15 at 10:12

Ok guys, thanks for the help. But I think you all just got things way too complicated. The only problem seemed to be that BST had to also be BST[K, V]:

abstract class BST[K <: Ordered[K], V]
sealed case class Node[K <: Ordered[K], V](key : K, value : V, left : BST[K, V], right : BST[K, V]) extends BST[K, V]
sealed case class Empty[K <: Ordered[K], V]() extends BST[K, V]

object BST {
  def empty = Empty()

  def add[K <: Ordered[K], V](key : K, value : V, tree : BST[K, V]) : BST[K, V] = tree match {
    case Empty() => new Node(key, value, Empty(), Empty())
    case Node(nodeKey, nodeValue, left, right) =>
      if (key < nodeKey) new Node(nodeKey, nodeValue, add(key, value, left), right)
      else if (key > nodeKey) new Node(nodeKey, nodeValue, left, add(key, value, right))
      else new Node(key, value, left, right)
  }
}

This compiles and works as expected.

score 0 · Answer 2 · answered Sep 15 '15 at 03:52

The compiler seems to be confused by you telling it that the generic type K is a subtype of Ordered[K]. I'm a bit confused by that as well. That's like saying that A is a subtype of List[A], and I can't wrap my head around that either. How can a type be a subtype of a list of that type? Recursively defining types may work in some cases, but I don't believe this is one of them.

From the context, I feel like the actual syntax you want is [K: Ordered]. This tells the compiler to expect a generic type K for which there is an implicit Ordered[K] in scope. It is syntactic sugar that changes your Node class to look like this:

sealed case class Node[K, V](key : K, value : V, left : BST, right : BST)(implicit evidence: Ordered[K]) extends BST

Hm? In Java I would just state that K extends Comparable and there is no confusion to be had. — devoured elysium, Sep 15 '15 at 10:05

score 0 · Answer 3 · edited May 23 '17 at 12:29

0

This is because of the type erasure on the JVM - erased to Any in Scala. See this answer for example on how to work around this problem: How to pattern match on generic type in Scala?. Alternatively consider passing an implicit Ordering like this:

sealed case class Node[K, V](key : K, value : V, left : BST, right : BST,
  implicit cmp: Ordering[K]) extends BST

edited May 23 '17 at 12:29

Community

1
1

answered Sep 15 '15 at 03:52

yǝsʞǝla

16,272
2
44
65

Implicit parameters need to be in a new parameter list. You need `..., right: BST)(implicit cmp: Ordering[K])`. – Peter Neyens Sep 15 '15 at 08:46

score 0 · Answer 4 · answered Sep 15 '15 at 04:08

I've gotten this down to a compiling version, it's probably not minimal though and some explicit annotations can probably be removed. If you need more explanation, please leave a comment.

abstract class BST[K : Ordering, V]
sealed case class Node[K : Ordering, V](key : K, value : V, left : BST[K, V], right : BST[K,V]) extends BST[K, V]
sealed case class Empty[K : Ordering, V]() extends BST[K, V]

object BST {
  def empty[K : Ordering, V] = Empty[K,V]()

  def add[K : Ordering, V](key : K, value : V, tree : BST[K,V]) : BST[K,V] = tree match {
    case Empty() => new Node(key, value, Empty(), Empty())
    case Node(nodeKey, nodeValue, left, right) =>
      if (implicitly[Ordering[K]].lt(key,  nodeKey)) new Node(nodeKey, nodeValue, add(key, value, left), right)
      else if (implicitly[Ordering[K]].gt(key,nodeKey)) new Node(nodeKey, nodeValue, left, add(key, value, right))
      else new Node(key, value, left, right)
  }
}

Compilation error with Ordered in Scala

4 Answers4