Diverging implicit expansion error using SortedSet

Question

I'm trying to use a code similar to

abstract class A[T] extends Ordered[A[T]] {
  val att:Int

  def compare(that:A[T]) = 
    if (this.att >= that.att)
       1
    else
      -1
}

class B extends A[Int] {
  val att = 1
}

When I try this in Scala 2.11 REPL

scala> import scala.collection.immutable.SortedSet
scala> SortedSet[B]()

I get the following error

<console>:11: error: diverging implicit expansion for type Ordering[B]
starting with method ordered in trait LowPriorityOrderingImplicits
          SortedSet[B]()

How can I solve this?

Answer 1

You need an instance of the Ordering type class to create a SortedList. The ordered method mentioned in the error message will automatically create an Ordering[X] for any type X that's an Ordered[X].

Your B is not an Ordered[B], however—it only extends Ordered[A[Int]]. Ordered is invariant in its type argument, so Ordered[B] and Ordered[A[Int]] have essentially nothing to do with each other.

You can address this issue with F-bounded polymorphism:

abstract class A[T, S <: A[T, S]] extends Ordered[S] {
  val att: Int

  def compare(that: S)= 
    if (this.att >= that.att)
      1
    else
      -1
}

class B extends A[Int, B] {
  val att = 1
}

Now B extends Ordered[B] and you can create the sorted set. Alternatively, you could use your original code and just create a SortedSet[A[Int]]. It's a much better idea to avoid Ordered altogether, though, and just define the Ordering type class instance directly.