Come faccio a ordinare un insieme di elenchi in ordine lessicografico a Scala?

Question

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

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é ha la A Ordered[A] caratteristica non significa che List[A] ha il tratto Ordered[List[A]]. Presumibilmente, però, il 'modo scala' per farlo è con una definizione implicita.

Come faccio a convertire implicitamente un List[A] ad un Ordered[List[A]], supponendo che A ha la caratteristica Ordered[A] (in modo che il codice di cui sopra solo lavori)?

ho in mente utilizzando l'ordinamento lessicografico su oggetti List[A], ma mi piacerebbe codice che può essere adattato ad altri ordinamenti.

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

Si noti che ordering è implicitamente convertito in 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))

E '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 di classi case.

Per fare un esempio, definiamo un involucro di un Int, applicare Ordering.by(_.v), dove _.v estrae il 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 in una classe case con più membri, riutilizzando i comparatori per le 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

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

import scala.math.Ordering.Implicits._

prima di fare la vostra lista di confronto [Int], al fine di garantire che la funzione infixOrderingOps implicito è di portata.

Answer 3

(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 ' vista legato ' A <% Ordered[A], che assicura che necessità A non si da un Ordered[A], solo che c'è un modo per fare questa conversione. Fortunatamente, oggetto Predef della libreria Scala ha una conversione implicita da Ints a RichInts, che, in particolare, sono Ordered[Int]s.

Il resto del codice è solo attuando ordinamento lessicografico.

Answer 4

In 2.8, si dovrebbe essere in grado di fare proprio collection.sorted. sorted prende un parametro Ordering implicita. Qualsiasi tipo che implementa Ordered ha una Ordering corrispondente (grazie al Ordering.ordered conversione implicita). C'è anche la Ordering.Iterable implicito che fa un Iterable[T] avere 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]]

Io non sono sicuro perché il compilatore non riesce a trovare il Ordering[Iterable[A]] se il tipo di elemento della collezione è List[A].

Answer 5

Ispirato dal commento di Daniel, ecco un 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 a pensare che sia più una questione di gusti. A volte è più facile per verificare la correttezza su una funzione ricorsiva, e certamente la versione è abbastanza breve che non v'è alcuna ragione per preferire ricorsiva.

Sono rimasto affascinato dalle implicazioni sulle prestazioni però. Così ho cercato di benchmark: vedi http://gist.github.com/468435 . Sono rimasto sorpreso di vedere che la versione ricorsiva è più veloce (assumendo che ho fatto il punto di riferimento in modo corretto). I risultati hanno ancora un senso per la lista di circa 10 di lunghezza.