Wie kann ich eine Sammlung von Listen in lexikographischer Ordnung in Scala sortieren?

Question

Wenn A die Ordered[A] Eigenschaft hat, ich möchte in der Lage sein, Code zu haben, dass Arbeiten wie diese

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

und bekommen etwas, wo die Listen haben in lexikographische Reihenfolge sortiert sind. Natürlich, nur weil A das Merkmal Ordered[A] bedeutet aber hat nicht, dass List[A] das Merkmal Ordered[List[A]] hat. Vermutlich ist jedoch die ‚scala Art und Weise‘ dies mit einem impliziten def zu tun ist.

Wie implizit konvertiere ich eine List[A] zu einem Ordered[List[A]], unter der Annahme, A hat das Merkmal Ordered[A] (so dass der Code über nur Werke)?

Ich denke dabei an die lexikographische Ordnung auf List[A] Objekte verwenden, aber ich würde gerne Code mit anderen Anordnungen angepasst werden kann.

Answer 1

Inspiriert von Ben Lings' Antwort schrieb ich meine eigene Version von sort:

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

, die gleich ist:

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

Beachten Sie, dass ordering implizit Ordering[Iterable[A]] umgewandelt wird.

Beispiele:

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

wurde gefragt, wie Sie Ihre eigene Vergleichsfunktion zu liefern; Es genügt Ordering.fromLessThan zu verwenden:

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

Ordering.by können Sie Ihren Wert in eine andere Art abzubilden, für die es bereits eine Bestellung Instanz. Da auch Tupel bestellt, kann dies für lexikographischen Vergleich der Fallklassen nützlich sein.

Um ein Beispiel zu machen, lassen Sie uns einen Wrapper eines Int definieren, gelten Ordering.by(_.v), wo _.v den zugrunde liegenden Wert extrahiert, und zeigen, dass wir das gleiche Ergebnis erhalten:

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

Schließlich wollen wir tun dasselbe auf einer Fall-Klasse mit mehreren Mitgliedern, die Komparatoren für Tupeln Wiederverwendung:

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

Inspiriert von Ben Lings' Antwort, ich schaffte es, herauszufinden, was lexikographisch zu sortieren Listen wie die einfachste Art und Weise scheint: die Zeile

import scala.math.Ordering.Implicits._

vor Ihrer Liste [Int] Vergleich zu tun, um sicherzustellen, dass die implizite Funktion infixOrderingOps im Gültigkeitsbereich befindet.

Answer 3

(11 Minuten vor mir eigentlich nicht weiß, wie dies zu tun, ich hoffe, dass es in Ordnung betrachtet ist meine eigene Frage zu beantworten.)

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

Eine wichtige Sache zu beachten ist hier die ‚ sehen gebunden ‘ A <% Ordered[A], die sorgt dafür, dass A Bedarf nicht selbst von einem Ordered[A], nur, dass es einen Weg gibt, um diese Umwandlung zu tun. Glücklicherweise des Objekts Predef Scala Bibliothek hat eine implizite Konvertierung von Ints zu RichInts, die Ordered[Int]s insbesondere sind.

Der Rest des Codes ist nur lexikographische Ordnung zu implementieren.

Answer 4

2,8, sollten Sie in der Lage sein, nur collection.sorted zu tun. sorted nimmt einen impliziten Ordering Parameter. Jede Art, daß Arbeitsgeräte Ordered eine entsprechende Ordering (dank der impliziten Konvertierung Ordering.ordered). Es besteht auch die implizite Ordering.Iterable, dass ein Iterable[T] eine Ordering haben macht, wenn T eine Ordering hat.

Wenn Sie jedoch versuchen, dies es nicht funktioniert:

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
                                                             ^

Sie müssen explizit angeben, dass Sie die Ordering[Iterable[A]] wollen:

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

Ich bin mir nicht sicher, warum die Compiler nicht die Ordering[Iterable[A]] finden können, wenn der Elementtyp der Sammlung List[A] ist.

Answer 5

Inspiriert von Daniel Kommentar, hier ist eine rekursive Version:

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

In Bezug auf den Kommentar: Früher dachte ich, es ist mehr eine Frage des Geschmacks. Manchmal ist es einfacher Korrektheit auf einer rekursive Funktion, um zu überprüfen, und ist sicher Version ist kurz genug, dass es kein zwingender Grund ist rekursiv zu bevorzugen.

Ich war allerdings durch die Auswirkungen auf die Leistung fasziniert. Also habe ich versucht zu Benchmark es: siehe http://gist.github.com/468435 . Ich war überrascht zu sehen, dass die rekursive Version ist schneller (vorausgesetzt ich die Benchmark richtig gemacht). Die Ergebnisse halten nach wie vor gilt für die Liste von etwa Länge 10.