Как сортировать коллекцию списков в лексикографическом порядке в 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» для этого заключается в неявном определении.

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

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

Answer 1

Вдохновленный ответ Бен Лингс, я написал свою собственную версию 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 позволяет сопоставить значение в другой тип, для которого существует уже экземпляр заказа. Учитывая, что и кортежи упорядочены, это может быть полезно для лексикографического сравнения классов случаев.

Для примера, давайте определим обертку с 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))) 

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

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 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 s до RichInt s, которое, в частности, Ordered[Int] s.

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

Answer 3

В 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 4

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

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.

Answer 5

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

import scala.math.Ordering.Implicits._ 

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