¿Cómo puedo formar la unión de Scala SortedMaps?

Question

(estoy usando nocturnos de Scala, y ver el mismo comportamiento en 2.8.0b1 RC4. Soy un recién llegado Scala.)

tengo dos SortedMap s que me gustaría para formar la unión de. Aquí está el código que me gustaría usar:

import scala.collection._ 

object ViewBoundExample { 
    class X 
    def combine[Y](a: SortedMap[X, Y], b: SortedMap[X, Y]): SortedMap[X, Y] = { 
     a ++ b 
    } 
    implicit def orderedX(x: X): Ordered[X] = new Ordered[X] { def compare(that: X) = 0 } 
} 

La idea aquí es la declaración 'implícita' significa X s se pueden convertir en Ordered[X] s, y entonces tiene sentido combinar SortedMap s en otro SortedMap, en lugar de solo un mapa

Cuando compilo, consigo

sieversii:scala-2.8.0.Beta1-RC4 scott$ bin/scalac -versionScala compiler version 
2.8.0.Beta1-RC4 -- Copyright 2002-2010, LAMP/EPFL 

sieversii:scala-2.8.0.Beta1-RC4 scott$ bin/scalac ViewBoundExample.scala 
ViewBoundExample.scala:8: error: type arguments [ViewBoundExample.X] do not 
    conform to method ordered's type parameter bounds [A <: scala.math.Ordered[A]] 
     a ++ b 
     ^
one error found 

parece que mi problema desaparecería si ese parámetro de tipo unido se [A <% scala.math.Ordered[A]], en lugar de [A <: scala.math.Ordered[A]]. Desafortunadamente, ¡ni siquiera puedo averiguar dónde vive el método 'ordenado'! ¿Alguien puede ayudarme a rastrearlo?

En su defecto, ¿qué debo hacer para producir la unión de dos SortedMap s? Si elimino el tipo de devolución de la combinación (o la cambio a Map) todo funciona bien --- ¡pero no puedo confiar en que la devolución esté ordenada!

Answer 1

Actualmente, lo que está utilizando es el rasgo scala.collection.SortedMap, cuyo método ++ se hereda del rasgo MapLike. Por lo tanto, se ve el siguiente comportamiento:

scala> import scala.collection.SortedMap 
import scala.collection.SortedMap 

scala> val a = SortedMap(1->2, 3->4) 
a: scala.collection.SortedMap[Int,Int] = Map(1 -> 2, 3 -> 4) 

scala> val b = SortedMap(2->3, 4->5) 
b: scala.collection.SortedMap[Int,Int] = Map(2 -> 3, 4 -> 5) 

scala> a ++ b 
res0: scala.collection.Map[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5) 

scala> b ++ a 
res1: scala.collection.Map[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5) 

El tipo del resultado retorno de ++ es una Map[Int, Int], porque esto sería el único tipo que tiene sentido el método de un objeto MapLike++ para regresar. Parece que ++ mantiene la propiedad ordenada del SortedMap, lo que supongo es porque ++ usa métodos abstractos para hacer la concatenación, y esos métodos abstractos se definen para mantener el orden del mapa.

Para tener la unión de dos mapas ordenados, sugiero que use scala.collection.immutable.SortedMap.

scala> import scala.collection.immutable.SortedMap 
import scala.collection.immutable.SortedMap 

scala> val a = SortedMap(1->2, 3->4) 
a: scala.collection.immutable.SortedMap[Int,Int] = Map(1 -> 2, 3 -> 4) 

scala> val b = SortedMap(2->3, 4->5) 
b: scala.collection.immutable.SortedMap[Int,Int] = Map(2 -> 3, 4 -> 5) 

scala> a ++ b 
res2: scala.collection.immutable.SortedMap[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5) 

scala> b ++ a 
res3: scala.collection.immutable.SortedMap[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5) 

Esta implementación del rasgo SortedMap declara un método que devuelve un ++SortedMap.

Ahora, un par de respuestas a sus preguntas acerca de los límites del tipo:

• Ordered[T] es un rasgo que si se mezcla en una clase especifica que esa clase puede compararse utilizando <, >, =, >= , <=. Solo tiene que definir el método abstracto compare(that: T) que devuelve -1 para this < that, 1 para this > that y 0 para this == that. Luego todos los otros métodos se implementan en el rasgo basado en el resultado de compare.

• T <% U representa una vista delimitada en Scala. Esto significa que el tipo T es un subtipo de U o puede convertirse implícitamente en U mediante una conversión implícita en el alcance. El código funciona si coloca <% pero no con <: ya que X no es un subtipo de Ordered[X], sino que se puede convertir implícitamente a Ordered[X] utilizando la conversión implícita OrderedX.

Editar: En cuanto a su comentario. Si está utilizando el scala.collection.immutable.SortedMap, todavía está programando en una interfaz, no en una implementación, ya que el SortedMap inmóvil se define como trait. Puede verlo como un rasgo más especializado de scala.collection.SortedMap, que proporciona operaciones adicionales (como ++ que devuelve SortedMap) y la propiedad de ser inmutable. Esto está en línea con la filosofía de Scala, prefiera la inmutabilidad, por lo tanto, no veo ningún problema al usar el SortedMap inmutable. En este caso, puede garantizar el hecho de que el resultado será definitivamente ordenado, y esto no se puede cambiar ya que la colección es inmutable.

Aunque, todavía me parece extraño que el scala.collection.SortedMap no proporcione un método ++ que devuelva un SortedMap como resultado. Todas las pruebas limitadas que he hecho parecen sugerir que el resultado de una concatenación de dos scala.collection.SortedMap s de hecho produce un mapa que conserva la propiedad ordenada.

Answer 2

¡Has elegido un hueso duro para romper como un principiante de Scala! :-)

Bien, breve recorrido, no espere comprenderlo por completo en este momento. Primero, tenga en cuenta que el problema ocurre en el método ++. Buscando su definición, la encontramos en el rasgo MapLike, que recibe un Iterator o un Traversable. Como y es SortedMap, entonces es la versión Traversable que se está utilizando.

Tenga en cuenta en su firma de tipo extenso que hay un CanBuildFrom pasado. Se está aprobando implícitamente, por lo que normalmente no debe preocuparse por ello. Sin embargo, para entender lo que está pasando, esta vez lo haces.

Puede localizar CanBuildFrom haciendo clic en él donde aparece en la definición de ++, o filtrando. Como menciona Randall en los comentarios, hay un campo en blanco sin marcar en la esquina superior izquierda de la página scaladoc. Solo tiene que hacer clic allí y escribir, y devolverá las coincidencias para lo que sea que haya escrito.

Por lo tanto, busque el rasgo CanBuildFrom en ScalaDoc y selecciónelo. Tiene una gran cantidad de subclases, cada una responsable de construir un tipo específico de colección. Busque y haga clic en la subclase SortedMapCanBuildFrom. Esta es la clase del objeto que necesita para generar un SortedMap de Traversable. Tenga en cuenta que el constructor de instancias (el constructor de la clase) recibe un parámetro implícito Ordering. Ahora nos estamos acercando.

Esta vez, utilice el filtro de filtro para buscar Ordering. Su objeto complementario (haga clic en la pequeña "o" del nombre) aloja un implícito que generará Ordering s, ya que los objetos complementarios se examinan en busca de implícitos que generen instancias o conversiones para esa clase. Se define dentro del rasgo LowPriorityOrderingImplicits, que se extiende al objeto Ordering, y mirándolo verá el método ordered[A <: Ordered[A]], que producirá el Ordering requerido ... o lo produciría, si no hubiera ningún problema.

Uno podría suponer que la conversión implícita de X a Ordered[X] sería suficiente, tal como lo había hecho antes, al analizar esto con más detenimiento. Eso, sin embargo, es una conversión de objetos, y ordered espera recibir un tipo que es un subtipo de Ordered[X]. Si bien uno puede convertir un objeto de tipo X en un objeto de tipo Ordered[X], X, no es un subtipo de Ordered[X], por lo que no se puede pasar como un parámetro a ordered.

Por otro lado, se puede crear una implícita valOrdering[X], en lugar de la defOrdered[X], y obtendrá alrededor del problema. Específicamente:

object ViewBoundExample { 
    class X 
    def combine[Y](a: SortedMap[X, Y], b: SortedMap[X, Y]): SortedMap[X, Y] = { 
     a ++ b 
    } 
    implicit val orderingX = new Ordering[X] { def compare(x: X, y: X) = 0 } 
} 

creo que la mayoría de la gente reacción inicial a Ordered/Ordering debe ser uno de perplejidad: ¿por qué tiene clases para la misma cosa? El primero se extiende java.lang.Comparable, mientras que el último se extiende java.util.Comparator. Por desgracia, el tipo de firma para compare resume bastante bien la principal diferencia:

def compare(that: A): Int  // Ordered 
def compare(x: T, y: T): Int // Ordering 

El uso de un Ordered[A] requiere, ya sea para A que se extienden Ordered[A], lo que requeriría que uno sea capaz de modificarA 's definición, o para pasar un método que puede convertir un A en un Ordered[A]. Scala es perfectamente capaz de hacer esto último fácilmente, pero entonces usted tiene para convertir cada instancia antes de comparar.

Por otro lado, el uso de Ordering[A] requiere la creación de un único objeto, como se demostró anteriormente. Cuando lo usa, simplemente pasa dos objetos de tipo A a compare - no se crean objetos en el proceso.

Así que hay algunas mejoras en el rendimiento, pero hay una razón mucho más importante para la preferencia de Scala para Ordering sobre Ordered. Mire nuevamente en el objeto complementario al Ordering. Notará que hay varias implicaciones para muchas de las clases de Scala definidas allí. Puede recordar que mencioné anteriormente que se buscará un implícito para la clase T dentro del objeto complementario de T, y eso es exactamente lo que está sucediendo.

Este podría hacerse para Ordered también. Sin embargo, y este es el punto de fricción, eso significa que todos los métodos compatibles con Ordering y Ordered ¡fallarían! Esto se debe a que Scala buscará un implícito para que funcione y encontrará dos: uno para Ordering, y otro para Ordered. Al no poder decidir qué es lo que quería, Scala se da por vencido con un mensaje de error. Por lo tanto, se tuvo que hacer una elección, y Ordering tuvo más cosas para eso.

Duh, olvidé explicar por qué la firma no está definida como ordered[A <% Ordered[A]], en lugar de ordered[A <: Ordered[A]]. Sospecho que hacerlo causaría la falla de las dobles implícitas que he mencionado antes, pero le preguntaré al tipo que realmente hizo estas cosas y tuvo el doble de problemas implícitos si este método en particular es problemático.