Diverging implicit expansion for type Ordering[ProgramVertex]

Question
1

I see this topic raised here https://users.scala-lang.org/t/diverging-implicit-expansion/495 and it seems to be when you can mutually recursive (implicit) calls?

However, with this simple case, I can’t see what the problem is:

abstract class Vertex(val id: Int) extends Ordered[Vertex] {
  override def toString() = "vtx_" + id
  def compare(that: Vertex) = this.id - that.id
}

class ProgramVertex(id: Int, name: String) extends Vertex(id)

I think it may be more a program with the inheritance than the comparison?

Error: diverging implicit expansion for type Ordering[ProgramVertex]
[error] starting with method $conforms in object Predef

2

It is indeed a problem with inheritance. Ordered and Ordering are invariant in their type parameter, which means an Ordering[ProgramVertex] is not a subtype of Ordering[Vertex].
I can’t fully explain why this causes a recursion, using the -Xlog-implicits compiler parameter shows several implicits the compiler tries, some of which require implicits themselves, causing a loop somewhere.

If you want all subclasses of vertex to be ordered by the same function, you will need to use an Ordering instead of Ordered:

object Vertex {
  implicit def ord[A <: Vertex] = Ordering.by((_:A).id)
}

This implicit method will generate an ordering for the type of your collection you want to sort.

2 Likes
3

abstract class Vertex(val id: Int) extends Ordering[Vertex]
object Vertex { implicit def ord[A <: Vertex] = Ordering.by((_:A).id) }
class PV extends Vertex(0)
class XV extends Vertex(1)

Thanks - I’m still missing something since the above still errors (either naming it ord or compare)?

class PV needs to be abstract, since method compare in trait Ordering of type (x: Playground.this.Vertex, y: Playground.this.Vertex)Int is not defined

  • ah I think you remove extends Ordering[Vertex]
4

Yes, your abstract class should not extend Ordering or Ordered, the Ordering will only be searched via the implicit in this case.