How to add 'Array[Ordered[Any]]' as a method parameter

Question

Below is an implementation of Selection sort written in Scala.

The line ss.sort(arr) causes this error : type mismatch; found : Array[String] required: Array[Ordered[Any]]

Since the type Ordered is inherited by StringOps should this type not be inferred ? How can I add the array of Strings to sort() method ?

Here is the complete code :

object SelectionSortTest {

  def main(args: Array[String]){

    val arr = Array("Hello","World")

    val ss = new SelectionSort()
    ss.sort(arr)
  }

}

class SelectionSort {

  def sort(a : Array[Ordered[Any]]) = {
    var N = a.length

    for (i <- 0 until N) {
        var min = i

        for(j <- i + 1 until N){
            if( less(a(j) , a(min))){
              min = j
            }
        exchange(a , i , min)
        }
    }

  }

  def less(v : Ordered[Any] , w : Ordered[Any]) = {
    v.compareTo(w) < 0
  }

  def exchange(a : Array[Ordered[Any]] , i : Integer , j : Integer) = {
    var swap : Ordered[Any] = a(i)
    a(i) = a(j)
    a(j) = swap
  }
}

Answer 1

Array is invariant. You cannot use an Array[A] as an Array[B] even if A is subtype of B. See here why: Why are Arrays invariant, but Lists covariant?

Neither is Ordered, so your implementation of less will not work either.

You should make your implementation generic the following way:

object SelectionSortTest {

  def main(args: Array[String]){

    val arr = Array("Hello","World")

    val ss = new SelectionSort()
    ss.sort(arr)
  }

}

class SelectionSort {

  def sort[T <% Ordered[T]](a : Array[T]) = {
    var N = a.length

    for (i <- 0 until N) {
        var min = i

        for(j <- i + 1 until N){
            if(a(j) < a(min)){ // call less directly on Ordered[T]
              min = j
            }
        exchange(a , i , min)
        }
    }

  }

  def exchange[T](a : Array[T] , i : Integer , j : Integer) = {
    var swap = a(i)
    a(i) = a(j)
    a(j) = swap
  }
}

The somewhat bizarre statement T <% Ordered[T] means "any type T that can be implicitly converted to Ordered[T]". This ensures that you can still use the less-than operator.

See this for details: What are Scala context and view bounds?

Answer 2

The answer by @gzm0 (with some very nice links) suggests Ordered. I'm going to complement with an answer covering Ordering, which provides equivalent functionality without imposing on your classes as much.

Let's adjust the sort method to accept an array of type 'T' for which an Ordering implicit instance is defined.

def sort[T : Ordering](a: Array[T]) = {
  val ord = implicitly[Ordering[T]]
  import ord._ // now comparison operations such as '<' are available for 'T'
  // ...
  if (a(j) < a(min))
  // ...
}

The [T : Ordering] and implicitly[Ordering[T]] combo is equivalent to an implicit parameter of type Ordering[T]:

def sort[T](a: Array[T])(implicit ord: Ordering[T]) = {
  import ord._
  // ...
}

Why is this useful? Imagine you are provided with a case class Account(balance: Int) by some third party. You can now add an Ordering for it like so:

// somewhere in scope
implicit val accountOrdering = new Ordering[Account] {
  def compare(x: Account, y: Account) = x.balance - y.balance
}

// or, more simply
implicit val accountOrdering: Ordering[Account] = Ordering by (_.balance)

As long as that instance is in scope, you should be able to use sort(accounts).
If you want to use some different ordering, you can also provide it explicitly, like so: sort(accounts)(otherOrdering).

Note that this isn't very different from providing an implicit conversion to Ordering (at least not within the context of this question).

Answer 3

Even though, when coding Scala, I'm used to prefer functional programming style (via combinators or recursion) over imperative style (via variables and iterations), THIS TIME, for this specific problem, old school imperative nested loops result in simpler and performant code.

I don't think falling back to imperative style is a mistake for certain classes of problems, such as sorting algorithms which usually transform the input buffer (more like a procedure) rather than resulting to a new sorted collection.

Here it is my solution:

package bitspoke.algo

import scala.math.Ordered
import scala.collection.mutable.Buffer

abstract class Sorter[T <% Ordered[T]] {

  // algorithm provided by subclasses
  def sort(buffer : Buffer[T]) : Unit

  // check if the buffer is sorted
  def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }

  // swap elements in buffer
  def swap(buffer : Buffer[T], i:Int, j:Int) {
    val temp = buffer(i)
    buffer(i) = buffer(j)
    buffer(j) = temp
  }
}


class SelectionSorter[T <% Ordered[T]] extends Sorter[T] {
  def sort(buffer : Buffer[T]) : Unit = {
    for (i <- 0 until buffer.length) {
      var min = i
      for (j <- i until buffer.length) {
        if (buffer(j) < buffer(min))
          min = j
       }
       swap(buffer, i, min)
     }
  }
}

As you can see, to achieve parametric polymorphism, rather than using java.lang.Comparable, I preferred scala.math.Ordered and Scala View Bounds rather than Upper Bounds. That's certainly works thanks to Scala Implicit Conversions of primitive types to Rich Wrappers.

You can write a client program as follows:

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new SelectionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))