algorithm - 如何在 Scala 中定义一个采用 Ordered[T] 数组的方法？

Question

我正在 Scala 中构建一些基本算法(根据 Cormen 的书)以刷新我对这个主题的认识，并且我正在构建插入排序 算法。这样做，它可以正常工作:

class InsertionSort extends Sort {

def sort ( items : Array[Int] ) : Unit = {

    if ( items.length < 2 ) {
        throw new IllegalArgumentException( "Array must be bigger than 1" )
    }

    1.until( items.length ).foreach( ( currentIndex ) => {

        val key = items(currentIndex)

        var loopIndex = currentIndex - 1

        while ( loopIndex > -1 && items(loopIndex) > key ) {

            items.update( loopIndex + 1, items(loopIndex) )

            loopIndex -= 1
        }

        items.update( loopIndex + 1, key )

    } )

}

}    

但这仅适用于 Int，我想使用泛型和 Ordered[A] 这样我就可以对任何已排序的类型进行排序。当我将签名更改为这样时:

def sort( items : Array[Ordered[_]] ) : Unit

以下规范无法编译:

"sort correctly with merge sort" in {

  val items = Array[RichInt](5, 2, 4, 6, 1, 3)

  insertionSort.sort( items )

  items.toList === Array[RichInt]( 1, 2, 3, 4, 5, 6 ).toList

}

编译错误是:

Type mismatch, expected: Array[Ordered[_]], actual Array[RichInt]

但是 RichInt 不是一个 Ordered[RichInt] 吗？我应该如何以接受任何 Ordered 对象的方式定义此方法签名？

编辑

如果有人感兴趣，可以使用最终来源 here .

Answer 1

实际上 RichInt不是 Ordered[RichInt]但是一个Ordered[Int] .然而scala.runtime.RichInt <: Ordered[_] , 但类 Array在类型上是不变的 T所以Array[RichInt]不是 Array[Ordered[_]] .

scala> def f[T <% Ordered[T]](arr: Array[T]) = { arr(0) < arr(1) }
f: [T](arr: Array[T])(implicit evidence$1: T => Ordered[T])Boolean

scala> f(Array(1,2,3))
res2: Boolean = true

scala>