Come si ordina una raccolta di elenchi in ordine lessicografico in Scala?

Question

Se A ha il Ordered[A] tratto, mi piacerebbe essere in grado di avere il codice che funziona in questo modo

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

e ottenere qualcosa in cui le liste sono stati ordinati in ordine lessicografico. Naturalmente, solo perché A ha il tratto Ordered[A] non significa che List[A] abbia il tratto Ordered[List[A]]. Presumibilmente, tuttavia, la "scala" per farlo è con una definizione implicita.

Come posso convertire implicitamente un List[A] ad un Ordered[List[A]], supponendo che A ha la caratteristica Ordered[A] (in modo che il codice precedente funziona solo)?

Ho in mente di utilizzare l'ordinamento lessicografico sugli oggetti List[A], ma mi piacerebbe codice che possa essere adattato agli altri ordini.

Answer 1

Ispirato risposta Ben Lings', ho scritto la mia versione di sort:

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

che è equivalente a:

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

noti che ordering viene convertito in modo implicito Ordering[Iterable[A]].

Esempi:

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

è stato chiesto come fornire la propria funzione di confronto; Basta usare 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 consente di mappare il tuo valore in un altro tipo per i quali esiste già un'istanza di ordinazione. Dato che anche le tuple sono ordinate, questo può essere utile per il confronto lessicografico delle classi di casi.

per fare un esempio, definiamo un involucro di un Int, applicare Ordering.by(_.v), dove _.v estrae il valore sottostante, e mostrare che si ottiene lo stesso risultato:

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

Infine, cerchiamo di fare la stessa cosa su una classe case con più membri, riutilizzando i comparatori di tuple:

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 minuti fa Io in realtà non so come fare questo, spero che è considerato giusto da rispondere alla mia domanda.)

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

Una cosa importante da notare qui è il 'view bound' A <% Ordered[A] , che assicura che non abbia bisogno di sé da solo, solo che c'è un modo per fare questa conversione. Fortunatamente, l'oggetto della libreria Scala Predef ha una conversione implicita da Int s a RichInt s, che in particolare sono Ordered[Int] s.

Il resto del codice sta solo implementando l'ordinamento lessicografico.

Answer 3

In 2.8, si dovrebbe essere in grado di fare solo collection.sorted. sorted prende un parametro implicito Ordering. Qualsiasi tipo che implementa Ordered ha un corrispondente Ordering (grazie alla conversione implicita Ordering.ordered). C'è anche l'implicito Ordering.Iterable che fa sì che uno Iterable[T] abbia un Ordering se T ha un Ordering.

Tuttavia, se si tenta questo non funziona:

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 
                  ^

È necessario specificare esplicitamente che si desidera che il Ordering[Iterable[A]]:

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

non so il motivo per cui il compilatore può trovare lo Ordering[Iterable[A]] se il tipo di elemento della raccolta è List[A].

Answer 4

Ispirato dal commento di Daniel, qui è una versione ricorsiva:

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

Per quanto riguarda il commento: Ho usato per pensare che sia più una questione di gusti. A volte è più facile verificare la correttezza su una funzione ricorsiva, e certamente la tua versione è abbastanza breve da non avere motivi convincenti per preferire la ricorsione.

Sono stato incuriosito dalle implicazioni sulle prestazioni. Così ho provato a confrontarlo: vedi http://gist.github.com/468435.Sono stato sorpreso di vedere che la versione ricorsiva è più veloce (supponendo che abbia fatto il benchmark correttamente). I risultati hanno ancora un senso per la lista di circa lunghezza 10.

Answer 5

Ispirato risposta Ben Lings', sono riuscito a capire quello che sembra il modo più semplice per ordinare le liste lessicografico: aggiungere la riga

import scala.math.Ordering.Implicits._ 

prima eseguendo il confronto Elenco [Int], per garantire che la funzione implicita infixOrderingOps sia inclusa.