隱式從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。