Проблема с неявным преобразованием из 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]), вам не нужно было бы выполнять приведение, потому что скалак принял бы, что вы возвращаете 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: это подкласс всего. Ergo, это подкласс 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.