Как определить метод, который принимает массив Ordered [T] в Scala?

Question

Я строю некоторые базовые алгоритмы в Scala (следуя книге Кормена), чтобы освежить мои мысли по этому вопросу, и я строю алгоритм sort sorting . Делая это так, он работает правильно:

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 заказанным [RichInt]? Как мне определить сигнатуру этого метода таким образом, чтобы он принимал любой упорядоченный объект?

EDIT

На случай, если кому-то интересно, окончательный источник доступен здесь .

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>

Answer 2

Это можно сделать с помощью контекста для параметра типа;

scala> def foo[T : Ordering](arr: Array[T]) = { 
    |    import math.Ordering.Implicits._ 
    |    arr(0) < arr(1) 
    |  }
foo: [T](arr: Array[T])(implicit evidence$1: Ordering[T])Boolean

такой, что использование:

scala> foo(Array(2.3, 3.4))
res1: Boolean = true

Преимущество этого в том, что вам не нужен порядок по умолчанию для типа, если он вам не нужен:

scala> foo(Array("z", "bc"))
res4: Boolean = false

scala> foo(Array("z", "bc"))(Ordering.by(_.length))
res3: Boolean = true