¿Cómo puedo ordenar un conjunto 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 obras como esta

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, sólo porque tiene la A Ordered[A] rasgo no significa que List[A] tiene el rasgo Ordered[List[A]]. Es de suponer que, sin embargo, la 'vía Scala' de hacerlo es con una definición implícita.

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

Tengo en mente utilizando el orden lexicográfico en objetos List[A], pero me gustaría código que puede ser adaptado a otros ordenamientos.

Answer 1

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

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

que es equivalente 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 tuplas están clasificadas, esto puede ser útil para la comparación lexicográfico de las 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 el 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

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

import scala.math.Ordering.Implicits._

antes de hacer la lista de [Int] comparación, para asegurar que el infixOrderingOps función implícita es en su alcance.

Answer 3

(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 ' ver cota ' A <% Ordered[A], que asegura que no necesidad A sí por un Ordered[A], sólo que hay una manera de hacer esta conversión. Felizmente, de la biblioteca Scala objeto Predef tiene una conversión implícita de Ints a RichInts, que en particular son Ordered[Int]s.

El resto del código es simplemente implementando orden lexicográfico.

Answer 4

2.8, usted debe ser capaz de simplemente hacer collection.sorted. sorted toma un parámetro Ordering implícita. Cualquier tipo que implementos Ordered tiene una Ordering correspondiente (gracias a la Ordering.ordered conversión implícita). También existe la Ordering.Iterable implícita de que hace un Iterable[T] tener un Ordering si T tiene una 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 no puede encontrar el Ordering[Iterable[A]] si el tipo de elemento de la colección es List[A].

Answer 5

Inspirado por el comentario de Daniel, que aquí hay 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 para verificar la corrección de una función recursiva, y desde luego su versión es lo suficientemente corto que no hay ninguna razón de peso para preferir recursiva.

Yo estaba intrigado por las implicaciones de rendimiento sin embargo. Así que he intentado establecer criterios de referencia: ver http://gist.github.com/468435 . Me sorprendió ver que la versión recursiva es más rápido (suponiendo que hice el punto de referencia correctamente). Los resultados siguen siendo válidas para la lista de alrededor de longitud 10.