Problem with Implicit conversion from Int to Ordered

This is an implementation for a leftist heap in Scala.

package my.collections

sealed abstract class Heap[E](implicit val ordering:Ordering[E])  {

  import ordering._

  def empty: Heap[E] = Heap.empty

  def isEmpty: Boolean

  def insert(e: E): Heap[E]

  def merge(h: Heap[E]): Heap[E] = {
    def makeT(e:E,a:Heap[E],b:Heap[E]):Heap[E] = if (a.rank >= b.rank) Node(e,a,b,b.rank+1) else Node(e,b,a,a.rank+1)
    (this,h) match {
      case (Nil(),_) => h
      case (_,Nil()) => this
      case (Node(x,l1,r1,_),Node(y,l2,r2,_)) => if (x < y)  makeT(x,l1,r1.merge(h)) else makeT(y,l2,this.merge(r2))
    }
  }

  def findMin: E

  def deleteMin: Heap[E]

  protected def rank:Int
}


object Heap {

  private val emptyEl = new Nil[Nothing]

  def empty[E] = emptyEl.asInstanceOf[Heap[E]]

}

private case class Node[E](e: E, left: Heap[E], right: Heap[E], rank: Int)(implicit  ordering:Ordering[E]) extends Heap[E]()(ordering) {

  def deleteMin = left.merge(right)

  val findMin = e

  def insert(e: E):Heap[E] = Node(e,empty,empty,1).merge(this)

  def isEmpty = false

}

private case class Nil[E]()(implicit ordering:Ordering[E]) extends Heap[E]()(ordering) {

  def deleteMin = throw new NoSuchElementException

  def findMin = throw new NoSuchElementException

  def insert(e: E):Heap[E] = Node[E](e,Heap.empty,Heap.empty,1)

  def isEmpty = true

  protected def rank = 0
}

object PG {

  def main(args: Array[String]) {
    val e:Heap[Int] = Heap.empty[Int]
    val e1:Heap[Int] = e insert 3
    val e2:Heap[Int] = e1 insert 5
    val e3:Heap[Int] = e2.deleteMin
    println()
  }
}

This fails with the following error:

Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to scala.math.Ordered
    at scala.math.LowPriorityOrderingImplicits$$anon$3.compare(Ordering.scala:开发者_JS百科117)
    at scala.math.Ordering$class.lt(Ordering.scala:71)
    at scala.math.LowPriorityOrderingImplicits$$anon$3.lt(Ordering.scala:117)
    at scala.math.Ordering$Ops.$less(Ordering.scala:100)
    at my.collections.Heap.merge(Heap.scala:27)
    at my.collections.Node.insert(Heap.scala:53)
    at my.collections.PG$.main(Heap.scala:77)
    at my.collections.PG.main(Heap.scala)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
    at java.lang.reflect.Method.invoke(Method.java:597)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:115)

My questions are:

1. What exactly am I doing wrong, and how do I fix it?
2. Is there a systematic way of understanding such errors?

Since you are getting a class cast exception, i would look at possible wrong casts in your code. i can find one cast:

def empty[E] = emptyEl.asInstanceOf[Heap[E]]

and since E is not covariant, this is a cast error, Heap[Nothing] is not a subclass of Heap[E] !

You will have quite some job to make E covariant here, so unless you need this functionality, you may just fix the cast:

object Heap {
    def empty[E](implicit  ordering:Ordering[E]) = new Nil[E]
}

By the way, if Heap was covariant in E (e.g. Heap[+E]), you wouldn't need to do the cast, because scalac would accept that you return Nil[Nothing] for a Heap[E]. So unless you know exactly why you use asInstanceOf and there is no way around it, it is almost certainly a mistake.

Ok, here is some more proof that my answer is correct.

class A[B](implicit ord: Ordering[B]) {
  def compare(x: B, y: B) = ord.lt(x, y)
}
object A {
  private val e = new A[Nothing] ()
  def empty[X] = e.asInstanceOf[A[X]]
}
val test = A.empty[Int] // works
test.compare(1, 2)      // ouch

You can see that it's perfectly valid to make a wrong cast regarding type parameters! This is part of the sad JVM story of type erasure -- since casting occurs at runtime, A[B] and A[Nothing] reduce to A[java.lang.Object] and hence the cast itself is not forbidden.

The truth (mistake) is just revealed at the later point...

This is one of the most screwed up examples I have ever seen of what can go wrong when you lie to the compiler! :-)

I'll show what goes on line by line, so one can see what's going on (but 0__ is right and deserves the accepted answer).

val e:Heap[Int] = Heap.empty[Int]

That calls

def empty[E] = emptyEl.asInstanceOf[Heap[E]]

Which calls

private val emptyEl = new Nil[Nothing]

Which takes an implicit Ordering[Nothing]. I was very surprised there was such a thing, so I looked it up. One thing about Ordering, is that if your collection is Ordered, it will make an Ordering of it available. The method that provides this is:

implicit def ordered [A <: Ordered[A]]: Ordering[A] = new Ordering[A] {
    def compare(x: A, y: A) = x.compare(y)
}

So, here's the deal about Nothing: it is a subclass of everything. Ergo, it is a subclass of Ordered[Nothing], thus Ordering[Nothing] is available.

Anyway, there's no error so far. The next line is:

val e1:Heap[Int] = e insert 3

This calls insert on Nil:

def insert(e: E):Heap[E] = Node[E](e,Heap.empty,Heap.empty,1)

Note that no Ordering[E] is being passed to method insert, so it is using the one passed to Nil, Ordering[Nothing]. Still no error, though, so next line:

 val e2:Heap[Int] = e1 insert 5

This calls insert on Node:

def insert(e: E):Heap[E] = Node(e,empty,empty,1).merge(this)

Again, no Ordering[E] was passed, so it uses the one it received on creation, still Ordering[Nothing]. This will finally cause the error, on this line of merge:

  case (Node(x,l1,r1,_),Node(y,l2,r2,_)) => if (x < y)  makeT(x,l1,r1.merge(h)) else makeT(y,l2,this.merge(r2))

The expression x < y is the problem. There's no < method defined on x, since x is just a generic E, so it goes through implicit conversion to execute it:

new ordering.Ops(x) < y

Where Ops.< is:

def <(rhs: T) = lt(lhs, rhs)

And lt is defined on ordering (which was imported). In other words, it executes this:

ordering.lt(x, y)

That will result in a call to ordering.compare. We saw the definition for Ordering[Nothing] previously, which was:

x.compare(y)

And here is where the error happens. The type of x is java.lang.Integer (because of auto-boxing). The method compare is from scala.math.Ordered, which java.lang.Integer obviously does not implement.

So it fails. All of this because of a little white lie... :-)

If, on the other hand, an Ordering[Int] was being used, it would resort to this definition:

  def compare(x: Int, y: Int) = 
      if (x < y) -1
      else if (x == y) 0
      else 1
  }

Here, < exists, because x is Int.