How can I define a method that takes an Ordered[T] Array in Scala?

Question

I'm building some basic algorithms in Scala (following Cormen's book) to refresh my mind on the subject and I'm building the insertion sort algorithm. Doing it like this, it works correctly:

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 )

    } )

}

}

But this is for Int only and I would like to use generics and Ordered[A] so I could sort any type that is ordered. When I change the signature to be like this:

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

The following spec doesn't compile:

"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

}

And the compiler error is:

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

But isn't RichInt an Ordered[RichInt]? How should I define this method signature in a way that it would accept any Ordered object?

EDIT

In case anyone is interested, the final source is available here.

score 10 · Accepted Answer · edited Jan 06 '12 at 06:05

10

Actually RichInt is not an Ordered[RichInt] but an Ordered[Int]. However scala.runtime.RichInt <: Ordered[_], but class Array is invariant in type T so Array[RichInt] is not an 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>

edited Jan 06 '12 at 06:05

Dan Burton

53,238
27
117
198

answered Jan 06 '12 at 04:10

Eastsun

18,526
6
57
81

score 6 · Answer 2 · edited May 23 '17 at 12:12

You can do this with a context bound on the type parameter;

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

Such that usage is:

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

The advantage to this is that you don't need the default order of the type if you don't want it:

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

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

How can I define a method that takes an Ordered[T] Array in Scala?

2 Answers2