如何定義一個在Scala中使用有序[T]數組的方法？

我正在斯卡拉建立一些基本算法（以下Cormen的書），以更新我對這個主題的想法，並且我正在構建插入排序算法。做這樣的，它工作正常：如何定義一個在Scala中使用有序[T]數組的方法？

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) 

    }) 

} 

}

但是，這僅僅是爲了詮釋，我想用有序[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]？我應該如何定義這種方法簽名，使其能夠接受任何Ordered對象？

編輯

如果有人有興趣，最後源可用here。

來源

2012-01-06 Maurício Linhares

實際上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>

來源

2012-01-06 04:10:12 Eastsun

是的，就是這樣，謝謝！ – 2012-01-06 11:30:00

您可以在類型參數上使用context bound;

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

來源

2012-01-06 08:06:04

如何定義一個在Scala中使用有序[T]數組的方法？

回答

相關問題