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

Если 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.

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

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

Ответ 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 позволяет сопоставить ваше значение с другим типом, для которого уже есть экземпляр 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)))

Ответ 2

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

import scala.math.Ordering.Implicits._

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

Ответ 3

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

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

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

Ответ 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].

Ответ 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.

Ответ 6

Просто потому, что я уже реализовал это по-другому, вот нерекурсивная версия, которая не использует return:

new Ordering[Seq[String]]() {
  override def compare(x: Seq[String], y: Seq[String]): Int = {
    x.zip(y).foldLeft(None: Option[Int]){ case (r, (v, w)) =>
        if(r.isDefined){
          r
        } else {
          val comp = v.compareTo(w)
          if(comp == 0) None
          else Some(comp)
        }
      }.getOrElse(x.size.compareTo(y.size))
    }
  }