Error of “No implicit ordering defined for U” where a trait which has extended Ordered

Question

After creating a ScalaIDE Worksheet named test.WsTemp, I wrote the code below and am receiving three errors for a single line in trait Enum:

Diverging implicit expansion for type scala.math.Ordering[U] starting with method ordered in trait LowPriorityOrderingImplicits
No implicit Ordering defined for U
Not enough arguments for method sorted: (implicit ord: scala.math.Ordering[U])List[U], Unspecified value parameter ord.

Why isn't this working since it's obvious Val extends Ordered[Val]?

object WsTemp {
  trait Val extends Ordered[Val] {
    val id: Int
    val name: String
    final def compare(that: Val) = this.id - that.id
    override def toString: String = name
  }

  trait Enum[U <: Val] {
    protected def init: Set[U]
    val all = init
    val allOrdered = all.toList.sorted       // <-- Receiving error here
    val byId = all.map(x => (x.id, x)).toMap
    val byName = all.map(x => (x.name, x)).toMap

    def apply(id: Int) = byId.get(id)
    def apply(name: String) = byName.get(name)
  }

  sealed class Value(val id: Int, val name: String) extends Val
  object Suit extends Enum[Value] {
    override def init: Set[Value] = //Set()
      Set(
          new Value(0, "Spade")
        , new Value(1, "Club")
        , new Value(2, "Diamond")
        , new Value(3, "Heart")
      )
    val Spade = Suit.byId(0)
    val Club = Suit.byId(1)
    val Diamond = Suit.byId(2)
    val Heart = Suit.byId(3)
  }

  val all = Suit.all
  val allOrdered = Suit.allOrdered
  val byId = Suit.byId
  val byName = Suit.byName
  val spade = Suit.Spade
}

Régis Jean-Gilles Régis Jean-Gilles · Accepted Answer · 2013-02-24T23:42:49

Ordering and Ordered are both invariant , so the fact that U is a sub-type of Val (as expressed by the relation U <: Val) does not imply that Ordering[Val] can be used as an Ordering[U]. So even though the fact that Val extends Ordered[Val] means that you implicitly get an Ordering[Val], this means nothing regarding Ordering[U].

So the compiler is right to complain that it cannot find an implicit value of type Ordering[U] (which is required by the call to sorted).

The prolbem is easy to illustrate with a small code snippet that mimics what happens with Ordered and Ordering:

object WsTemp {
  trait MyOrdered[T]

  trait MyOrdering[T]
  object MyOrdering {
    implicit def toOrdering[A <% MyOrdered[A]]: MyOrdering[A] = new MyOrdering[A]{}
  }

  trait Val extends MyOrdered[Val]

  def test[T](implicit ord: MyOrdering[T]) {}

  trait Enum[U <: Val] {
    def callTest() { test[U] }
  }
}

Which produces the following error:

<console>:20: error: could not find implicit value for parameter ord: WsTemp.MyOrdering[U]
           def callTest() { test[U] }

But if you make MyOrdered and MyOrdering covariant, this compiles fine:

trait MyOrdered[+T]      
trait MyOrdering[+T]
...

Obviously, you cannot change scala's Ordering nor Ordered to make them invariant.

Now, one way to solve your problem is to arrange your code so that Val does not extend Ordered[Val], but instead extends Ordered[X] where X is the actual type that you want to have an Ordering for (here, X = U). This can be achieved with F-bounded polymorphism:

trait Val[Self<:Val[Self]] extends Ordered[Self] {
  //...
}

trait Enum[U <: Val[U]] {
  //...
}

sealed class Value(val id: Int, val name: String) extends Val[Value]
//...

U is now a sub-type of Val[U], which is a sub-type of Ordered[U] (as opposed to a sub-type of Ordered[Val] as before), and so you now implicitly get an Ordering[U], which is (implicitly) passed to sorted. Problem solved.

Error of “No implicit ordering defined for U” where a trait which has extended Ordered

2 Answers