Pregunta Tutorial de diseño de colecciones de Scala 2.8


Siguiente de mi confusión sin aliento, ¿cuáles son algunos buenos recursos que explican cómo el nuevo Scala  2.8 la biblioteca de colecciones ha sido estructurada. Me interesa encontrar información sobre cómo encajan los siguientes puntos:

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

73
2017-11-12 13:21


origen


Respuestas:


Prefacio

Hay una 2.8 recorrido de la colección por Martin Odersky, que probablemente sea su primera referencia. Se ha complementado también con notas arquitectónicas, que será 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).

Puedes encontrar un artículo 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 aquí.

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: General collection hierarchy

Todos los elementos mostrados son rasgos. En las otras dos jerarquías también hay clases heredando directamente los rasgos, así como las clases que pueden ser Visto como perteneciente 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: Immutable collection hierarchy

Gráfico para la jerarquía mutable: Mutable collection hierarchy

Leyenda:

Graph legend

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 entonces eran seriales, muchos algoritmos que las usaban suponían y dependían del hecho de que fueronde serie. 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 ordena el 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 precedida por Par: ParIterable, ParSeq, ParMap y ParSet. Tenga en cuenta que no hay ParTraversable, ya que cualquier colección que soporte acceso paralelo es capaz de soportar el ParIterable rasgo. 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 tanto mutables como inmutables, más ParRange y ParVector implementar immutable.ParSeq y ParArray implementar 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 a colecciones paralelas y en serie. Esto significa que un método que toma una Seq no puede recibir una colección paralela, sino un método que toma una GenSeq se espera que funcione con colecciones seriadas 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 en eso. Del mismo modo, cualquier colección se puede convertir en una serie llamando al método seq en eso.

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

No confundir 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. Vocación toSeq en una colección paralela devolverá un ParSeq, no una colección de 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 más o menos como un rasgo Traversable se describe a continuación, pero con la limitación de que solo puedes usarlo una vez. Es decir, cualquier método llamado en un TraversableOnce  mayo hacerlo 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 no usando Iteratormétodos específicos para poder trabajar con cualquier colección, más iteradores, si se reescriben para aceptar TraversableOnce.

Porque 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 colección jerarquía es rasgo 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 la función de f es descartado por para cada.

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

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

Rasgo Iterable

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

Clase Iterable también agrega algunos métodos menos utilizados a menudo Traversable, que se puede implementar de manera eficiente solo si iterator está 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 Iterable allí vienen tres rasgos básicos que heredan de él: Seq, Sety Map. Los tres tienen un apply método y los tres implementan el PartialFunction rasgo, pero el significado de apply es diferente en cada caso.

Confío en el significado de Seq, Set y Map es 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 más refinamientos, 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. Puede ser implementado solo con foreach.
    • TraversableProxy - Proxy para un Traversable. Solo punto self a la colección real.
    • TraversableView - Un 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 crean un nuevo objeto iterable del mismo tipo.
    • mutable.Traversable y immutable.Traversable - Lo mismo que Traversable, pero restringiendo el tipo de colección.
    • Otros casos especiales Iterable clases, como MetaData, existe
    • Iterable - Una colección para la cual Iterator puede ser creado (a través de iterator)
      • IterableProxy, IterableView, mutable y immutable.Iterable.
  • Iterator - Un rasgo que no es descendiente de Traversable. Definir next y hasNext.
    • CountedIterator -- Un Iterator definiendo count, que devuelve los elementos vistos hasta ahora.
    • BufferedIterator - Define head, que devuelve el siguiente elemento sin consumirlo.
    • Otros casos especiales Iterator clases, como Source, existe

Los mapas

  • Map -- Un Iterable de Tuple2, que también proporciona métodos para recuperar un valor (el segundo elemento de la tupla) dado una clave (el primer elemento de la tupla). Extiende PartialFunction también.
    • MapProxy -- UN Proxy para Map.
    • DefaultMap - Un rasgo que implementa algunos de Mapmétodos abstractos
    • SortedMap -- UN Map cuyas claves están ordenadas
      • immutable.SortMap
        • immutable.TreeMap - Una clase implementando immutable.SortedMap.
    • immutable.Map
      • immutable.MapProxy
      • immutable.HashMap - Una clase implementando immutable.Map a través del hash clave.
      • immutable.IntMap - Una clase implementando immutable.Map especializado para Int llaves. Utiliza un árbol basado en los dígitos binarios de las teclas.
      • immutable.ListMap - Una clase implementando immutable.Map a través de listas.
      • immutable.LongMap - Una clase implementando immutable.Map especializado para Long llaves. Ver IntMap.
      • Hay clases adicionales optimizadas para una cantidad específica de elementos.
    • mutable.Map
      • mutable.HashMap - Una clase implementando mutable.Map a través del hash clave.
      • mutable.ImmutableMapAdaptor - Una clase implementando un mutable.Map de un existente immutable.Map.
      • mutable.LinkedHashMap -?
      • mutable.ListMap - Una clase implementando mutable.Map a través de listas.
      • mutable.MultiMap - Una clase que acepta más de un valor distinto para cada clave.
      • mutable.ObservableMap -- UN Mixin que, cuando se mezcla con un Map, publica eventos para los observadores a través de un Publisher interfaz.
      • mutable.OpenHashMap - Una clase basada en un algoritmo hash abierto.
      • mutable.SynchronizedMap -- UN Mixin que debe ser mezclado con un Map para proporcionar una versión de ella 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 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 - Contenedores que permiten ver un String como un Seq[Char], mientras aún preserva el String métodos. No estoy seguro de cuál es la diferencia entre ellos.
      • mutable.IndexedSeq
        • mutable.GenericArray -- Un Seqbasado en una matriz de estructura similar. Tenga en cuenta que la "clase" Array es Java 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 donde los elementos son quitados de acuerdo con un Ordering primero, y último orden de cola.
        • mutable.PriorityQueueProxy -- Un abstracto Proxy 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 - Una lista perezosa. 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 mutable head (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 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 ambos mutable y immutablecolas
      • immutable.Stack - Una clase que implementa una estructura de datos optimizada para LIFO (Last-In, First-Out). No existe una superclase común de ambos mutable  immutable pilas.
      • immutable.Vector -?
      • scala.xml.NodeSeq - Una clase XML especializada que se 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 implementando una estructura de datos optimizada para LIFO.
    • mutable.StackProxy -- UN Proxy para 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 mutable.Buffer clase, con tiempo amortizado constante para las operaciones de adición, 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 Mixin rasgo que, cuando se mezcla con un Buffer, proporciona eventos de notificación a través de Publisher interfaces.
        • 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 un SortedSet basado en un árbol
    • SetProxy -- UN Proxy para Set.
    • immutable.Set
      • immutable.HashSet - Una implementación de Set basado en hash de elementos
      • immutable.ListSet - Una implementación de Set basado en listas
      • Existen clases de conjuntos adicionales para proporcionar implementaciones optimizadas para conjuntos de 0 a 4 elementos.
      • immutable.SetProxy -- UN Proxy para un inmutable Set.
    • mutable.Set
      • mutable.HashSet - Una implementación de Set basado en hash de elementos
      • mutable.ImmutableSetAdaptor - Una clase implementando un mutable Set de un inmutable Set.
      • LinkedHashSet - Una implementación de Set basado en listas
      • ObservableSet -- UN Mixin rasgo que, cuando se mezcla con un Set, proporciona eventos de notificación a través de Publisher interfaz.
      • SetProxy -- UN Proxy para Set.
      • SynchronizedSet -- UN Mixin rasgo que, cuando se mezcla con un Set, proporciona eventos de notificación a través de Publisher interfaz.

  • Por qué existen las clases Like (por ejemplo, TraversableLike)

Esto se hizo para lograr la máxima reutilización del código. El hormigón genérico la implementación para 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é son los métodos complementarios (por ejemplo, List.companion)

El constructor de las clases, es decir, el objeto que sabe cómo crear instancias de esa clase de una manera que puede ser utilizada por métodos como 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 map método se define en TraversableLike, pero si usaste una List obtendrás un List espalda.


188