隐式从Int到有序转换的问题

Question

这是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() 
    } 
} 

这失败，出现以下错误：

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: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) 

我的问题是：

1. 究竟我做错了，以及如何解决这个问题？
2. 有没有一种理解这种错误的系统方法？

Answer 1

由于您正在获得类转换异常，因此我会在您的代码中查看可能的错误转换。我能找到一个投：

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

而且由于E是不是协变，这是一个错误投，Heap[Nothing]不是Heap[E]子类！

您将有相当一些工作，使这里E协变，所以，除非你需要这个功能，你可能只是修复演员：

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

顺便说一句，如果Heap在E协变（如Heap[+E] ），您不需要进行演员表演，因为scalac会接受Nil[Nothing]代替Heap[E]。所以除非你确切地知道你为什么使用asInstanceOf，并且没有办法绕过它，这几乎肯定是一个错误。

Answer 2

好的，这里有更多证据表明我的答案是正确的。

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 

你可以看到，它是完全有效的做出错误的投关于类型参数！这是可悲的JVM故事类型擦除的一部分 - 由于投射发生在运行时，A[B]和A[Nothing]减少到A [java.lang.Object]，因此投射本身不被禁止。

事实（错误）只是透露，目前稍后...

Answer 3

这是我所见过的最搞砸了的例子，当你骗编译器可能出现的错误之一！ :-)

我会显示一行一行的内容，所以可以看到发生了什么（但是0__是正确的并且值得接受的答案）。

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

这就要求

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

其中要求

private val emptyEl = new Nil[Nothing] 

这需要一个隐含的Ordering[Nothing]。我很惊讶有这样的事情，所以我查了一下。有关Ordering的一点是，如果您的收藏是Ordered，它将使其可用Ordering。提供此方法是：

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

所以，这里的约Nothing交易：它是一切的子类。埃尔戈，它是Ordered[Nothing]的子类，因此Ordering[Nothing]可用。

无论如何，目前为止没有错误。下一行是：

val e1:Heap[Int] = e insert 3 

这就要求insert上Nil：

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

注意，没有Ordering[E]被传递给方法insert，所以它使用的是一个传递给Nil，Ordering[Nothing]。仍然没有错误，虽然如此，下一行：

val e2:Heap[Int] = e1 insert 5 

这就要求insert上Node：

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

同样，没有Ordering[E]传递，因此它使用它创建接受，仍Ordering[Nothing]之一。这将最终导致错误，在这条线的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)) 

表达x < y是问题。有一个关于x没有定义<方法，因为x只是一个普通的E，所以它会通过隐式转换来执行它：

new ordering.Ops(x) < y 

其中Ops.<是：

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

而且lt上ordering定义（这是进口的）。换句话说，它执行此操作：

ordering.lt(x, y) 

这将导致致电ordering.compare。我们看到了Ordering[Nothing]的定义之前，它是：

x.compare(y) 

这里是在错误发生。 x的类型是java.lang.Integer（因为自动装箱）。方法compare是从scala.math.Ordered，其中java.lang.Integer显然没有实现。

因此失败。所有这一切都因为一点点善意的谎言... :-)

如果，另一方面，正在使用的Ordering[Int]，它会采取这样的定义：

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

这里，<存在，因为x是Int。