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…

Accepted Answer

`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

Solution

Problem