Tutorial de diseño de colecciones de Scala 2.8

scala-collections scala-2.8

Question

Después de mi confusión sin aliento , ¿cuáles son algunos buenos recursos que explican cómo se ha estructurado la nueva biblioteca de colecciones de Scala 2.8 ? Me interesa encontrar información sobre cómo encajan los siguientes puntos:

• Las clases / características de la colección en sí (p. Ej. List , Iterable )
• Por qué existen las clases Like (p. Ej. TraversableLike )
• Para qué sirven los métodos complementarios (por ejemplo, List.companion )
• Cómo sé qué objetos implicit están en el alcance en un punto dado

Answer 1

Prefacio

Hay un recorrido de colección de 2.8 por Martin Odersky que probablemente sea su primera referencia. También se ha complementado con notas arquitectónicas , que serán de particular interés para aquellos que quieran diseñar sus propias colecciones.

El resto de esta respuesta fue escrita mucho antes de que existiera tal cosa (de hecho, antes de que se lanzara la versión 2.8.0).

Puede encontrar un documento sobre esto como Scala SID # 3 . Otros documentos en esa área también deberían ser interesantes para las personas interesadas en las diferencias entre Scala 2.7 y 2.8.

Voy a citar el artículo, selectivamente, y lo complementaré con algunos de mis pensamientos. También hay algunas imágenes, generadas por Matthias en decodified.com, y los archivos SVG originales se pueden encontrar here .

Las clases / rasgos de la colección en sí

En realidad, existen tres jerarquías de rasgos para las colecciones: una para colecciones mutables, una para colecciones inmutables y otra que no hace suposiciones sobre las colecciones.

También hay una distinción entre colecciones paralelas, seriales y quizás paralelas, que se introdujo con Scala 2.9. Hablaré de ellos en la próxima sección. La jerarquía descrita en esta sección se refiere exclusivamente a colecciones no paralelas .

La siguiente imagen muestra la jerarquía no específica introducida con Scala 2.8:

Todos los elementos mostrados son rasgos. En las otras dos jerarquías también hay clases que heredan directamente los rasgos, así como las clases que se pueden ver como pertenecientes a esa jerarquía mediante la conversión implícita a clases contenedoras. La leyenda de estos gráficos se puede encontrar después de ellos.

Gráfico para la jerarquía inmutable:

Gráfico para la jerarquía mutable:

Leyenda:

Aquí hay una representación abreviada de ASCII de la jerarquía de colecciones, para aquellos que no pueden ver las imágenes.

                    Traversable
                         |
                         |
                      Iterable
                         |
      +------------------+--------------------+
     Map                Set                  Seq
      |                  |                    |
      |             +----+----+         +-----+------+
    Sorted Map  SortedSet   BitSet   Buffer Vector LinearSeq

Colecciones Paralelas

Cuando Scala 2.9 introdujo colecciones paralelas, uno de los objetivos del diseño era hacer que su uso fuera lo más fluido posible. En los términos más simples, uno puede reemplazar una colección no paralela (serie) por una paralela y cosechar los beneficios al instante.

Sin embargo, dado que todas las colecciones hasta ese momento eran de serie, muchos algoritmos que las usaban suponían y dependían del hecho de que eran seriales. Las colecciones paralelas alimentadas a los métodos con tales suposiciones fallarían. Por esta razón, toda la jerarquía descrita en la sección anterior exige un procesamiento en serie .

Se crearon dos nuevas jerarquías para admitir las colecciones paralelas.

La jerarquía de colecciones paralelas tiene los mismos nombres para los rasgos, pero precedidos por Par : ParIterable , ParSeq , ParMap y ParSet . Tenga en cuenta que no existe ParTraversable , ya que cualquier colección que soporte acceso paralelo es capaz de soportar el rasgo ParIterable más fuerte. Tampoco tiene algunos de los rasgos más especializados presentes en la jerarquía serial. Toda esta jerarquía se encuentra en el directorio scala.collection.parallel .

Las clases que implementan colecciones paralelas también difieren, con ParHashMap y ParHashSet para colecciones paralelas mutables e inmutables, además de ParRange y ParVector implementando immutable.ParSeq y ParArray implementando mutable.ParSeq .

También existe otra jerarquía que refleja los rasgos de las colecciones en serie y paralelas, pero con un prefijo Gen : GenTraversable , GenIterable , GenSeq , GenMap y GenSet . Estos rasgos son padres de colecciones paralelas y en serie. Esto significa que un método que toma un Seq no puede recibir una colección paralela, pero se espera que un método que tome un GenSeq funcione con colecciones seriales y paralelas.

Dada la estructura de estas jerarquías, el código escrito para Scala 2.8 era totalmente compatible con Scala 2.9 y exigía un comportamiento en serie. Sin ser reescrito, no puede aprovechar las colecciones paralelas, pero los cambios requeridos son muy pequeños.

Usar colecciones paralelas

Cualquier colección se puede convertir en una paralela llamando al método par sobre ella. Del mismo modo, cualquier colección se puede convertir en una serie llamando al método seq en ella.

Si la colección ya era del tipo solicitado (paralelo o en serie), no se realizará ninguna conversión. Sin embargo, si se llama a seq en una colección paralela o par en una colección en serie, se generará una nueva colección con la característica solicitada.

No confunda seq , que convierte una colección en una colección no paralela, con toSeq , que devuelve un Seq creado a partir de los elementos de la colección. Llamar toSeq en una colección paralela devolverá un ParSeq , no una colección en serie.

Los principales rasgos

Si bien hay muchas clases de implementación y subtratos, existen algunos rasgos básicos en la jerarquía, cada uno de los cuales proporciona más métodos o garantías más específicas, pero reduce el número de clases que podrían implementarlos.

En las siguientes subsecciones, daré una breve descripción de los rasgos principales y la idea detrás de ellos.

Trait TraversableOnce

Este rasgo es muy parecido al rasgo Traversable describe a continuación, pero con la limitación de que solo puedes usarlo una vez . Es decir, cualquier método invocado en TraversableOnce puede volverlo inutilizable.

Esta limitación hace posible que los mismos métodos se compartan entre las colecciones y Iterator . Esto hace posible que un método que funcione con un Iterator pero que no utiliza métodos específicos de Iterator pueda realmente trabajar con cualquier colección, más iteradores, si se reescribe para aceptar TraversableOnce .

Como TraversableOnce unifica colecciones e iteradores, no aparece en los gráficos anteriores, que se refieren solo a las colecciones.

Traible Trasables

En la parte superior de la jerarquía de la colección , es Traible Traversable . Su única operación abstracta es

def foreach[U](f: Elem => U)

La operación pretende atravesar todos los elementos de la colección y aplicar la operación dada f a cada elemento. La aplicación está hecha solo por su efecto secundario; de hecho, cualquier resultado de función de f es descartado por foreach.

Los objetos transversales pueden ser finitos o infinitos. Un ejemplo de un objeto atravesable infinito es la corriente de números naturales Stream.from(0) . El método hasDefiniteSize indica si una colección es posiblemente infinita. Si hasDefiniteSize devuelve verdadero, la colección es hasDefiniteSize finita. Si devuelve falso, la colección no ha sido completamente elaborada todavía, por lo que podría ser infinita o finita.

Esta clase define métodos que pueden implementarse de manera eficiente en términos de foreach (más de 40 de ellos).

Rasgo Iterable

Este rasgo declara un iterator método abstracto que devuelve un iterador que produce todos los elementos de la colección uno por uno. El método foreach en Iterable se implementa en términos de iterator . Las subclases de Iterable menudo anulan foreach con una implementación directa para la eficiencia.

Clase Iterable también agrega algunos métodos menos utilizados a Traversable , que se pueden implementar de manera eficiente solo si hay un iterator disponible. Se resumen a continuación.

xs.iterator          An iterator that yields every element in xs, in the same order as foreach traverses elements.
xs takeRight n       A collection consisting of the last n elements of xs (or, some arbitrary n elements, if no order is defined).
xs dropRight n       The rest of the collection except xs takeRight n.
xs sameElements ys   A test whether xs and ys contain the same elements in the same order

Otros rasgos

Después de Iterable , aparecen tres rasgos básicos que heredan de él: Seq , Set y Map . Los tres tienen un método de apply y los tres implementan el rasgo PartialFunction , pero el significado de apply es diferente en cada caso.

Confío en que el significado de Seq , Set y Map sea ​​intuitivo. Después de ellos, las clases se dividen en implementaciones específicas que ofrecen garantías particulares con respecto al rendimiento y los métodos que pone a su disposición como resultado de ello. También están disponibles algunos rasgos con mejoras adicionales, como LinearSeq , IndexedSeq y SortedSet .

La lista a continuación puede mejorarse. Deja un comentario con sugerencias y lo arreglaré.

Clases base y rasgos

• Traversable - Clase de colección básica. Se puede implementar solo con foreach .
  • TraversableProxy - Proxy para un Traversable . Simplemente apunta a la verdadera colección.
  • TraversableView - A Traversable con algunos métodos no estrictos.
  • TraversableForwarder : reenvía la mayoría de los métodos a underlying , excepto toString , hashCode , equals , stringPrefix , newBuilder , view y todas las llamadas creando un nuevo objeto iterable del mismo tipo.
  • mutable.Traversable e immutable.Traversable . Traversable : lo mismo que Traversable , pero restringe el tipo de colección.
  • Existen otras clases especiales Iterable , como MetaData .
  • Iterable : una colección para la cual se puede crear un Iterator (a través del iterator ).
    • IterableProxy , IterableView , mutable e immutable.Iterable .
• Iterator : un rasgo que no es descendiente de Traversable . Define next y hasNext .
  • CountedIterator - count que define el Iterator , que devuelve los elementos vistos hasta el momento.
  • BufferedIterator - Define head , que devuelve el siguiente elemento sin consumirlo.
  • Existen otras clases de Iterator casos especiales, como Source .

Los mapas

• Map : un Iterable de Tuple2 , que también proporciona métodos para recuperar un valor (el segundo elemento de la tupla) con una clave (el primer elemento de la tupla). Extiende la función PartialFunction también.
  • MapProxy : un Proxy para un Map .
  • DefaultMap : un rasgo que implementa algunos de los métodos abstractos de Map .
  • SortedMap - Un Map cuyas claves están ordenadas.
    • immutable.SortMap
      • immutable.TreeMap - Una clase que implementa immutable.SortedMap .
  • immutable.Map
    • immutable.MapProxy
    • immutable.HashMap - Una clase que implementa immutable.Map través de la clave hash.
    • immutable.IntMap - Una clase que implementa immutable.Map especializada para claves Int . Utiliza un árbol basado en los dígitos binarios de las teclas.
    • immutable.ListMap - Una clase que implementa immutable.Map través de listas.
    • immutable.LongMap - Una clase que implementa immutable.Map especializada para claves Long . Ver IntMap .
    • Hay clases adicionales optimizadas para una cantidad específica de elementos.
  • mutable.Map
    • mutable.HashMap - Una clase que implementa mutable.Map través de la clave hash.
    • mutable.ImmutableMapAdaptor - Una clase que implementa un mutable.Map desde un mutable.Map immutable.Map existente.
    • mutable.LinkedHashMap -?
    • mutable.ListMap - Una clase que implementa mutable.Map través de listas.
    • mutable.MultiMap - Una clase que acepta más de un valor distinto para cada clave.
    • mutable.ObservableMap - Una mezcla que, cuando se mezcla con un Map , publica eventos a los observadores a través de una interfaz de Publisher .
    • mutable.OpenHashMap - Una clase basada en un algoritmo hash abierto.
    • mutable.SynchronizedMap - Una mezcla que se debe mezclar con un Map para proporcionar una versión con métodos sincronizados.
    • mutable.MapProxy .

Las secuencias

• Seq - Una secuencia de elementos. Uno asume una repetición de tamaño y elemento bien definida. Extiende la función PartialFunction también.
  • IndexedSeq - Secuencias que admiten O (1) acceso a elementos y O (1) cálculo de longitud.
    • IndexedSeqView
    • immutable.PagedSeq - Una implementación de IndexedSeq donde los elementos son producidos bajo demanda por una función que pasa a través del constructor.
    • immutable.IndexedSeq
      • immutable.Range : una secuencia delimitada de enteros, cerrada en el extremo inferior, abierta en el extremo superior y con un paso.
        • immutable.Range.Inclusive : un Range cerrado en el extremo superior también.
        • immutable.Range.ByOne - Un Range cuyo paso es 1.
      • immutable.NumericRange : una versión más genérica de Range que funciona con cualquier Integral .
        • immutable.NumericRange.Inclusive , immutable.NumericRange.Exclusive .
        • immutable.WrappedString , immutable.RichString - Wrappers que permite ver un String como un Seq[Char] , mientras se conservan los métodos String . No estoy seguro de cuál es la diferencia entre ellos.
    • mutable.IndexedSeq
      • mutable.GenericArray - Una estructura de matriz basada en Seq . Tenga en cuenta que la "clase" Array es Java''s Array , que es más un método de almacenamiento de memoria que una clase.
      • mutable.ResizableArray - Clase interna utilizada por clases basadas en matrices de tamaño variable.
      • mutable.PriorityQueue , mutable.SynchronizedPriorityQueue - Clases que implementan colas priorizadas - colas en las que los elementos se quitan de la cola según un Ordering primero y el orden de la última cola.
      • mutable.PriorityQueueProxy - un Proxy abstracto para PriorityQueue .
  • LinearSeq - Un rasgo para secuencias lineales, con tiempo eficiente para isEmpty , head y tail .
    • immutable.LinearSeq
      • immutable.List : una implementación de lista inmutable, de enlace único.
      • immutable.Stream - A lazy-list. Sus elementos solo se computan a pedido, pero se memorizan (guardan en la memoria) después. Puede ser teóricamente infinito.
    • mutable.LinearSeq
      • mutable.DoublyLinkedList - Una lista con mutable prev , head ( elem ) y tail ( next ).
      • mutable.LinkedList - Una lista con head mutable ( elem ) y tail ( next ).
      • mutable.MutableList - Una clase utilizada internamente para implementar clases basadas en listas mutables.
        • mutable.Queue , mutable.QueueProxy - Una estructura de datos optimizada para operaciones FIFO (First-In, First-Out).
        • mutable.QueueProxy - Un Proxy para un mutable.Queue .
  • SeqProxy , SeqView , SeqForwarder
  • immutable.Seq
    • immutable.Queue : una clase que implementa una estructura de datos optimizada para FIFO (First-In, First-Out). No existe una superclase común de colas mutable e immutable .
    • immutable.Stack - Una clase que implementa una estructura de datos optimizada para LIFO (Last-In, First-Out). No existe una superclase común de ambas pilas mutable immutable .
    • immutable.Vector -?
    • scala.xml.NodeSeq - Una clase XML especializada que extiende immutable.Seq .
    • immutable.IndexedSeq - Como se ve arriba.
    • immutable.LinearSeq - Como se ve arriba.
  • mutable.ArrayStack - Una clase que implementa una estructura de datos optimizada para LIFO utilizando matrices. Supuestamente significativamente más rápido que una pila normal.
  • mutable.Stack , mutable.SynchronizedStack - Clases que implementan una estructura de datos optimizada para LIFO.
  • mutable.StackProxy - Un Proxy para un mutable.Stack ..
  • mutable.Seq
    • mutable.Buffer - Secuencia de elementos que pueden modificarse añadiendo, anteponiendo o insertando nuevos miembros.
      • mutable.ArrayBuffer - Una implementación de la clase mutable.Buffer , con tiempo amortizado constante para las operaciones de mutable.Buffer , actualización y acceso aleatorio. Tiene algunas subclases especializadas, como NodeBuffer .
      • mutable.BufferProxy , mutable.SynchronizedBuffer .
      • mutable.ListBuffer - Un buffer respaldado por una lista. Proporciona anexar y anexar un tiempo constante, siendo la mayoría de las demás operaciones lineales.
      • mutable.ObservableBuffer - Un rasgo de mixin que, cuando se mezcla con un Buffer , proporciona eventos de notificación a través de las interfaces de un Publisher .
      • mutable.IndexedSeq - Como se ve arriba.
      • mutable.LinearSeq - Como se ve arriba.

Los conjuntos

• Set : un conjunto es una colección que incluye a lo sumo uno de cualquier objeto.
  • BitSet - Un conjunto de enteros almacenados como un conjunto de bits.
    • immutable.BitSet
    • mutable.BitSet
  • SortedSet - Un conjunto cuyos elementos están ordenados.
    • immutable.SortedSet
      • immutable.TreeSet : una implementación de SortedSet basado en un árbol.
  • SetProxy : un Proxy para un Set .
  • immutable.Set
    • immutable.HashSet : una implementación de Set basada en hash de elementos.
    • immutable.ListSet : una implementación de Set basada en listas.
    • Existen clases de conjuntos adicionales para proporcionar implementaciones optimizadas para conjuntos de 0 a 4 elementos.
    • immutable.SetProxy - Un Proxy para un Set inmutable.
  • mutable.Set
    • mutable.HashSet - Una implementación de Set basada en hash de elementos.
    • mutable.ImmutableSetAdaptor - Una clase que implementa un Set mutable desde un Set inmutable.
    • LinkedHashSet - Una implementación de Set basada en listas.
    • ObservableSet - Un rasgo de mixin que, cuando se mezcla con un Set , proporciona eventos de notificación a través de una interfaz de Publisher .
    • SetProxy : un Proxy para un Set .
    • SynchronizedSet - Un rasgo mixin que, cuando se mezcla con un Set , proporciona eventos de notificación a través de una interfaz de Publisher .

• Por qué existen las clases Like (p. Ej. TraversableLike)

Esto se hizo para lograr la máxima reutilización del código. La implementación genérica concreta para las clases con una cierta estructura (un traversable, un mapa, etc.) se realiza en las clases Me gusta. Las clases destinadas al consumo general, entonces, anulan los métodos seleccionados que pueden optimizarse.

• Para qué sirven los métodos complementarios (por ejemplo, List.companion)

El generador de las clases, es decir, el objeto que sabe cómo crear instancias de esa clase de una manera que pueda ser utilizada por métodos como el map , se crea mediante un método en el objeto complementario. Entonces, para construir un objeto de tipo X, necesito obtener ese constructor del objeto compañero de X. Desafortunadamente, no hay forma, en Scala, de pasar de la clase X al objeto X. Por eso, hay un método definido en cada instancia de X, companion , que devuelve el objeto complementario de la clase X.

Si bien puede haber algún uso para dicho método en los programas normales, su objetivo es permitir la reutilización del código en la biblioteca de la colección.

• Cómo sé qué objetos implícitos están en el alcance en un punto dado

Se supone que no debes preocuparte por eso. Están implícitos precisamente para que no necesites averiguar cómo hacerlo funcionar.

Estas implicaciones existen para permitir que los métodos en las colecciones se definan en las clases principales pero aún devuelvan una colección del mismo tipo. Por ejemplo, el método de map se define en TraversableLike , pero si lo usaste en una List , obtendrás una List nuevo.