Как отсортировать коллекцию списков в лексикографическом порядке в Scala?

Вдохновленный ответом Бена Линга, я сумел придумать самый простой способ лексикографической сортировки списков: добавить строку

import scala.math.Ordering.Implicits._

Перед выполнением сравнения списка[Int] убедитесь, что неявная функция infixOrderingOps находится в области видимости.

(11 минут назад я на самом деле не знал, как это сделать, я надеюсь, что это считается нормальным, чтобы ответить на мой собственный вопрос.)

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
        }
    }
}

Здесь важно отметить, что " вид связан' A <% Ordered[A], что гарантирует, что A не нужно само по себе Ordered[A], просто есть способ сделать это преобразование. К счастью, объект библиотеки Scala Predef имеет неявное преобразование из Ints в RichInts, которые, в частности, являются Ordered[Int]s.

Остальная часть кода просто реализует лексикографический заказ.

В 2.8, вы должны быть в состоянии просто сделать collection.sorted. sorted принимает неявный параметр Ordering. Любой тип, реализующий Ordered, имеет соответствующий Ordering (благодаря неявному преобразованию Ordering.ordered). Существует также неявное Ordering.Iterable, которое заставляет Iterable[T] иметь Ordering, Если T имеет Ordering.

Однако, если вы попробуете это сделать, это не сработает:

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
                                                             ^

Вам нужно явно указать, что вы хотите Ordering[Iterable[A]]:

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

Я не уверен, почему компилятор не может найти Ordering[Iterable[A]], Если тип элемента коллекции - List[A].

Вдохновленный комментарием Даниэля, вот рекурсивная версия:

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)
  }
}

В отношении комментария: Раньше я думал, что это скорее вопрос вкуса. Иногда легче проверить корректность рекурсивной функции, и, конечно, ваша версия достаточно коротка, чтобы не было убедительных причин предпочесть рекурсивную.

Тем не менее, я был заинтригован результатами работы. Поэтому я попытался сравнить его: см. http://gist.github.com/468435 . я был удивлен, увидев, что рекурсивная версия быстрее (при условии, что я сделал тест правильно). Результаты по-прежнему остаются верными для списка длиной около 10.