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

Question

Если A имеет черту Ordered[A], я бы хотел иметь код, который работает следующим образом

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

и получите что-то, где списки отсортированы в лексикографическом порядке. Конечно, то, что A имеет черту Ordered[A], не означает, что List[A] имеет черту Ordered[List[A]]. Предположительно, однако, «scala способ» сделать это с неявным def.

Как мне неявно преобразовать List[A] в Ordered[List[A]], предполагая, что A имеет черту Ordered[A] (так что приведенный выше код просто работает)?

Я имею в виду использование лексикографического порядка для List[A] объектов, но я хотел бы, чтобы код мог быть адаптирован к другим порядкам.

Answer 1

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

import scala.math.Ordering.Implicits._

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

Answer 2

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

Важная вещь, на которую следует обратить внимание, это ' view bound 'A <% Ordered[A], что гарантирует, что A не нужно само по себе Ordered[A], просто есть способ сделать это преобразование.К счастью, объект библиотеки Scala Predef имеет неявное преобразование из Int с в RichInt с, в частности это Ordered[Int] с.

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

Answer 3

Вдохновленный ответом Бена Линса, я написал свою собственную версию sort:

def sort[A : Ordering](coll: Seq[Iterable[A]]) = coll.sorted

, что эквивалентно:

def sort[A](coll: Seq[Iterable[A]])(implicit ordering: Ordering[A]) = coll.sorted

Обратите внимание, что ordering неявно преобразуется в Ordering[Iterable[A]].

Примеры:

scala> def sort[A](coll: Seq[Iterable[A]])(implicit ordering: Ordering[A]) = coll.sorted
sort: [A](coll: Seq[Iterable[A]])(implicit ordering: Ordering[A])Seq[Iterable[A]]

scala> val coll = List(List(1, 3), List(1, 2), List(0), Nil, List(2))
coll: List[List[Int]] = List(List(1, 3), List(1, 2), List(0), List(), List(2))

scala> sort(coll)
res1: Seq[Iterable[Int]] = List(List(), List(0), List(1, 2), List(1, 3), List(2))

Был задан вопрос, как предоставить собственную функцию сравнения; Достаточно использовать Ordering.fromLessThan:

scala> sort(coll)(Ordering.fromLessThan(_ > _))
res4: Seq[Iterable[Int]] = List(List(), List(2), List(1, 3), List(1, 2), List(0))

Ordering.by позволяет вам сопоставить ваше значение с другим типом, для которого уже есть экземпляр Ordering. Учитывая, что также упорядочены кортежи, это может быть полезно для лексикографического сравнения классов случаев.

Чтобы создать пример, давайте определим оболочку Int, применим Ordering.by(_.v), где _.v извлекает базовое значение, и покажем, что мы получаем тот же результат:

scala> case class Wrap(v: Int)
defined class Wrap

scala> val coll2 = coll.map(_.map(Wrap(_)))
coll2: List[List[Wrap]] = List(List(Wrap(1), Wrap(3)), List(Wrap(1), Wrap(2)), List(Wrap(0)), List(), List(Wrap(2)))

scala> sort(coll2)(Ordering.by(_.v))
res6: Seq[Iterable[Wrap]] = List(List(), List(Wrap(0)), List(Wrap(1), Wrap(2)), List(Wrap(1), Wrap(3)), List(Wrap(2)))

Наконец, давайте сделаем то же самое для класса case с большим количеством членов, повторно используя компараторы для Tuples:

scala> case class MyPair(a: Int, b: Int)
defined class MyPair

scala> val coll3 = coll.map(_.map(MyPair(_, 0)))
coll3: List[List[MyPair]] = List(List(MyPair(1,0), MyPair(3,0)), List(MyPair(1,0), MyPair(2,0)), List(MyPair(0,0)), List(), List(MyPair(2,0)))

scala> sort(coll3)(Ordering.by(x => (x.a, x.b)))
res7: Seq[Iterable[MyPair]] = List(List(), List(MyPair(0,0)), List(MyPair(1,0), MyPair(2,0)), List(MyPair(1,0), MyPair(3,0)), List(MyPair(2,0)))

Answer 4

В 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].

Answer 5

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

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 *.