Wie sortiere ich eine Sammlung von Listen in lexikographischer Reihenfolge in Scala?

Question

Wenn A die Ordered[A] Eigenschaft hat, würde Ich mag Lage sein, Code zu haben, wie diese

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

arbeitet und etwas zu bekommen, wo die Listen haben in lexikographische Reihenfolge sortiert sind. Natürlich, nur weil A hat das Merkmal Ordered[A] bedeutet nicht, dass List[A] hat das Merkmal Ordered[List[A]]. Vermutlich ist der "Scala-Weg" dies jedoch mit einem impliziten Def.

Wie konvertiere ich implizit eine List[A] zu einem Ordered[List[A]], unter der Annahme, A das Merkmal Ordered[A] (so dass der Code oben gerade arbeitet) hat?

Ich habe im Sinn mit der lexikographischen Bestellung auf List[A] Objekte, aber ich möchte Code, der an andere Ordnungen 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 zu Ordering[Iterable[A]] umgewandelt.

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

Es wurde gefragt, wie Sie Ihre eigene Vergleichsfunktion zu liefern; Es genügt verwenden 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 können Sie Ihren Wert in eine andere Art abzubilden, für die es bereits eine Bestellung Instanz. Da auch Tupel angeordnet sind, kann dies für den lexikografischen Vergleich von 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 das gleiche tun mit mehreren Mitgliedern auf eine Fall-Klasse, 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

(11 Minuten wusste ich wirklich nicht, 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 ‚view bound‘ A <% Ordered[A] , die dafür sorgt, dass A sich selbst nicht durch eine Ordered[A] brauchen, nur dass es eine Möglichkeit gibt, diese Konvertierung durchzuführen. Glücklicherweise hat das Objekt Predef der Scala-Bibliothek eine implizite Umwandlung von Int s zu RichInt s, die insbesondere Ordered[Int] s sind.

Der Rest des Codes implementiert nur lexikographische Anordnung.

Answer 3

In 2.8 sollten Sie einfach tun können. sorted nimmt einen impliziten Ordering Parameter. Jeder Typ, der Ordered implementiert, hat einen entsprechenden Ordering (dank der impliziten Konvertierung Ordering.ordered). Es gibt auch die implizite Ordering.Iterable, die eine Iterable[T] eine Ordering hat, wenn T eine Ordering hat.

Wenn Sie jedoch versuchen, diese funktioniert es nicht:

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 wollen, dass die Ordering[Iterable[A]]:

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

Ich bin mir nicht sicher, warum der Compiler finde den Ordering[Iterable[A]] nicht, wenn der Elementtyp der Sammlung List[A] ist.

Answer 4

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: Ich denke, verwendet es mehr eine Frage des Geschmacks ist. Manchmal ist es einfacher, die Korrektheit einer rekursiven Funktion zu überprüfen, und sicherlich ist Ihre Version so kurz, dass es keinen zwingenden Grund gibt, rekursiv vorzugehen.

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

Answer 5

Inspiriert von Ben Lings' Antwort, ich schaffte es, herauszufinden, was wie der einfachste Weg scheint Listen lexikographisch zu sortieren: fügen Sie die Zeile

import scala.math.Ordering.Implicits._ 

vor Machen Sie Ihren List [Int] Vergleich, um sicherzustellen, dass die implizite Funktion infixOrderingOps im Geltungsbereich ist.