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

Как мне неясно преобразовать 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))

Было спросило, как поставить собственную функцию сравнения; Достаточно использовать заказ. 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

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

import scala.math.Ordering.Implicits._

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

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

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

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

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.