Extend scala class that extends ordered

Question

I'm having trouble extending a base class that extends Ordered[Base]. My derived class can't extend Ordered[Derived] so can't be used as a key in a TreeMap. If I create a TreeMap[Base] and then just override compare in Derived that works but it's not what I want. I would like to be able to have the derived class as a key. Is there a way around this?

case class A(x: Int) extends Ordered[A] {
  def compare(that: A) = x.compare(that.x)
}

// Won't compile
//  case class B(val y : Int) extends A(1) with Ordered[B] {
//    def compare(that: B) = x.compare(that.x) match {
//      case 0 => y.compare(that.y)
//      case res => res
//    }
//  }

// Compiles but can't be used to define a TreeMap key
case class B(y: Int) extends A(1) {
  override def compare(that: A) = that match {
    case b: B => x.compare(b.x) match {
      case 0 => y.compare(b.y)
      case res => res
    }
    case _: A => super.compare(that)
  }
}

def main(args: Array[String]) {
  TreeMap[B, Int]() // Won't compile
}

Edit

This discussion on the scala mailing list seems to be very relevant but it loses me a bit.

Answer 1

You can use a type conversion from B to Ordered[B]:

class OrderedB(me : B) extends Ordered[B]{
    def compare(that: B) = me compare that
}
collection.immutable.TreeMap.empty[B, Int](new OrderedB(_))

I think B has always to be a subtype of A which implies Order[A] whoes type A is invariant. It cannot define a second compare method to implement Order[B] with the same type errasure as the compare method from Ordered[A].

Alternatively you can define an implicit type versions from B to Ordered[B]:

implicit def orderedA2orderedB[B <: A with Ordered[A]](b : B) : Ordered[B] = b.asInstanceOf[Ordered[B]]
collection.immutable.TreeMap[B, Int]()

This should be valid. I'm not aware of a way to express this in the type system without casts.

Answer 2

You could put an implicit Ordering[B] in scope somewhere, like this:

  object BOrdering extends Ordering[B] {
    def compare(a: B, b: B) = a.compare(b)
  }
  implicit val bo = BOrdering
  TreeMap[B, Int]() // Now it works!

---

EDIT: This is only in Scala 2.8 (thanks, Ken)

Answer 3

The trait Ordered takes a parameter. A type parameter, granted, but it works just like any other parameter. When you extend it twice, in the base class and in the subclass, you are not "importing" two versions of Ordered. Instead, linearization of classes takes place, and you import it only once. For that reason, you cannot pass two different parameters to it.

Now, there is a reason why TreeMap does not require a subclass of Ordered, just a conversion from your class to an Ordered of it. It is precisely to make such things possible. Instead of extending these things directly, you should implicits for them:

scala> class A(val x: Int)
defined class A

scala> class B(x : Int, val y : Int) extends A(x)
defined class B

scala> import scala.collection.immutable.TreeMap
import scala.collection.immutable.TreeMap

scala> class AOrd(a: A) extends Ordered[A] {
     |   def compare(that: A) = a.x.compare(that.x)
     | }
defined class AOrd

scala> object AOrd {
     | implicit def toAOrd(a: A) = new AOrd(a)
     | }
defined module AOrd

scala> class BOrd(b: B) extends Ordered[B] {
     |   def compare(that: B) = b.x.compare(that.x) match {
     |     case 0 => b.y.compare(that.y)
     |     case res => res
     |   }
     | }
defined class BOrd

scala> object BOrd {
     | implicit def toBOrd(b: B) = new BOrd(b)
     | }
defined module BOrd

scala> import AOrd._
import AOrd._

scala> import BOrd._
import BOrd._

scala> TreeMap[B, Int]()
res1: scala.collection.immutable.SortedMap[B,Int] = Map()