¿Cómo puedo ordenar una colección de listas en orden lexicográfico en Scala?

Question

Si A tiene el rasgo Ordered[A], me gustaría ser capaz de tener código que funciona de la siguiente

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

y conseguir algo en las listas han sido ordenadas en orden lexicográfico. Por supuesto, el hecho de que A tenga el rasgo Ordered[A] no significa que List[A] tenga el rasgo Ordered[List[A]]. Presumiblemente, sin embargo, la 'manera scala' de hacer esto es con una def implícita.

¿Cómo implícitamente convertir un List[A] a un Ordered[List[A]], suponiendo que A tiene el rasgo Ordered[A] (de modo que el código anterior simplemente funciona)?

Tengo en mente usar el orden lexicográfico en objetos List[A], pero me gustaría tener un código que se pueda adaptar a otras ordenaciones.

Answer 1

Inspirado en respuesta Ben Lings', escribí mi propia versión de sort:

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

lo que equivale a:

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

Tenga en cuenta que ordering se convierte implícitamente a Ordering[Iterable[A]].

Ejemplos:

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

Se preguntó cómo proporcionar su propia función de comparación; Basta con utilizar 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 le permite asignar su valor en otro tipo para el cual ya existe una instancia de pedido. Dado que también se ordenan las tuplas, esto puede ser útil para la comparación lexicográfica de clases de casos.

para hacer un ejemplo, vamos a definir una envoltura de un Int, aplicar Ordering.by(_.v), donde _.v extrae el valor subyacente, y muestran que se obtiene el mismo resultado:

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

Por último, vamos a hacer lo mismo en caso de una clase con más miembros, reutilizando los comparadores de tuplas:

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

(hace 11 minutos que en realidad no sé cómo hacer esto, espero que se considera aceptable para responder a mi propia pregunta.)

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 a tener en cuenta es el 'view bound' A <% Ordered[A] , lo que garantiza que A no necesite un Ordered[A], solo que hay una forma de hacer esta conversión. Afortunadamente, el objeto de la biblioteca de Scala Predef tiene una conversión implícita de Int s a RichInt s, que en particular son Ordered[Int] s.

El resto del código solo está implementando el orden lexicográfico.

Answer 3

En 2.8, debería poder hacer solo collection.sorted. sorted toma un implícito Ordering parámetro. Cualquier tipo que implemente Ordered tiene un Ordering correspondiente (gracias a la conversión implícita Ordering.ordered). También está el Ordering.Iterable implícito que hace que un Iterable[T] tenga un Ordering si T tiene un Ordering.

Sin embargo, si usted intenta esto no funciona:

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 
                  ^

Es necesario especificar explícitamente que quiere el Ordering[Iterable[A]]:

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

no estoy seguro de por qué el compilador puede no encuentra el Ordering[Iterable[A]] si el tipo de elemento de la colección es List[A].

Answer 4

Inspirado por el comentario de Daniel, aquí es una versión recursiva:

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

Con respecto al comentario: Yo solía pensar que es más una cuestión de gusto. A veces es más fácil verificar la corrección en una función recursiva, y ciertamente su versión es lo suficientemente corta como para que no haya una razón convincente para preferir la recursividad.

Sin embargo, estaba intrigado por las implicaciones de rendimiento. Así que traté de compararlo: ver http://gist.github.com/468435.Me sorprendió ver que la versión recursiva es más rápida (suponiendo que hice el punto de referencia correctamente). Los resultados siguen siendo válidas para la lista de alrededor de longitud 10.

Answer 5

Inspirado en respuesta Ben Lings', me las arreglé para trabajar en lo que parece ser la forma más sencilla de ordenar las listas lexicográfico: añada la línea

import scala.math.Ordering.Implicits._ 

antes haciendo su comparación de Lista [Int], para asegurar que la función implícita infixOrderingOps está dentro del alcance.