How do I sort a collection of Lists in lexicographic order in Scala?

Question

If A has the Ordered[A] trait, I'd like to be able to have code that works like this

val collection: List[List[A]] = ... // construct a list of lists of As
val sorted = collection sort { _ < _ }

and get something where the lists have been sorted in lexicographic order. Of course, just because A has the trait Ordered[A] doesn't mean that List[A] has the trait Ordered[List[A]]. Presumably, however, the 'scala way' to do this is with an implicit def.

How do I implicitly convert a List[A] to a Ordered[List[A]], assuming A has the trait Ordered[A] (so that the code above just works)?

I have in mind using the lexicographic ordering on List[A] objects, but I'd like code that can be adapted to others orderings.

Answer 1

(11 minutes ago I actually didn't know how to do this, I hope it's considered okay to answer my own question.)

implicit def List2OrderedList[A <% Ordered[A]](list1: List[A]): Ordered[List[A]] = { 
    new Ordered[List[A]] {
        def compare(list2: List[A]): Int = {
            for((x,y) <- list1 zip list2) {
                val c = x compare y
                if(c != 0) return c
            }
            return list1.size - list2.size
        }
    }
}

An important thing to note here is the 'view bound' A <% Ordered[A], which ensures that A needn't itself by an Ordered[A], just that there's a way to do this conversion. Happily, the Scala library's object Predef has an implicit conversion from Ints to RichInts, which in particular are Ordered[Int]s.

The rest of the code is just implementing lexicographic ordering.

Answer 2

In 2.8, you should be able to just do collection.sorted. sorted takes an implicit Ordering parameter. Any type that implements Ordered has a corresponding Ordering (thanks to the implicit conversion Ordering.ordered). There is also the implicit Ordering.Iterable that makes an Iterable[T] have an Ordering if T has an Ordering.

However, if you try this it doesn't work:

scala> def sort[A <: Ordered[A]](coll: List[List[A]]) = coll.sorted

<console>:5: error: could not find implicit value for parameter ord: Ordering[List[A]]
       def sort[A <: Ordered[A]](coll: List[List[A]]) = coll.sorted
                                                             ^

You need to explicitly specify that you want the Ordering[Iterable[A]]:

def sort[A <: Ordered[A]](coll: List[List[A]]) = coll.sorted[Iterable[A]]

I'm not sure why the compiler can't find the Ordering[Iterable[A]] if the element type of the collection is List[A].

Answer 3

Inspired by Daniel's comment, here is a recursive version:

implicit def toOrdered[A <% Ordered[A]](list1: List[A]): Ordered[List[A]] = { 
  @scala.annotation.tailrec
  def c(list1:List[A], list2:List[A]): Int = {
    (list1, list2) match {
      case (Nil, Nil) => 0
      case (x::xs, Nil) => 1
      case (Nil, y::ys) => -1
      case (x::xs, y::ys) => (x compare y) match {
        case 0 => c(xs, ys)
        case i => i
      }
    }
  }
  new Ordered[List[A]] {
    def compare(list2: List[A]): Int = c(list1, list2)
  }
}

With respect to the comment: I used to think it's more a matter of taste. Sometimes it's easier to verify correctness on a recursive function, and certainly your version is short enough that there is no compelling reason to prefer recursive.

I was intrigued by the performance implications though. So I tried to benchmark it: see http://gist.github.com/468435. I was surprised to see that the recursive version is faster (assuming I did the benchmark correctly). The results still hold true for list of about length 10.