Semántica de Scala Traversable, Iterable, Sequence, Stream y View?

Question

Hay otras preguntas como Scala: What is the difference between Traversable and Iterable traits in Scala collections? y How would I get the sum of squares of two Lists in Scala? que responden la pregunta parcialmente. Sentí que una pregunta que cubre todo esto en un lugar tiene sentido.

Answer 1

Traversable es la parte superior de la jerarquía de colecciones. Su método principal es 'foreach' por lo que permite hacer algo para cada elemento de la colección.

Un Iterable puede crear un iterador, en función de qué foreach se puede implementar. Esto define cierto orden de los elementos, aunque ese orden puede cambiar para cada iterador.

Seq (uence) es un Iterable donde se arregla el orden de los elementos. Por lo tanto, tiene sentido hablar sobre el índice de un elemento.

Las secuencias son secuencias perezosas. Es decir. los elementos de una secuencia no pueden computarse antes de acceder a ellos. Esto hace posible trabajar con secuencias infinitas como la secuencia de todos los enteros.

Las vistas son versiones no estrictas de las colecciones. Los métodos como filtro y mapa en vista solo ejecutan las funciones pasadas cuando se accede al elemento respectivo. Por lo tanto, un mapa de una enorme colección regresa inmediatamente porque solo crea un envoltorio alrededor de la colección original. Solo cuando uno accede a un elemento, el mapeo se ejecuta realmente (para ese elemento). Tenga en cuenta que View no es una clase, pero hay muchas clases de XxxView para varias colecciones.

Answer 2

Un comentario que me gustaría agregar acerca de las transmisiones frente a los iteradores. Tanto las secuencias como los iteradores se pueden usar para implementar colecciones largas, no estrictas, potencialmente infinitas, que no computan un valor hasta que se necesita.

Sin embargo, hay un problema complicado con la "ejecución prematura" que se produce al hacer esto, que se puede evitar utilizando iteradores pero no flujos, y en el proceso señala una importante diferencia semántica entre los dos. Esta es quizás ilustra más claramente de la siguiente manera:

def runiter(start: Int) { 
    // Create a stream that returns successive integers on demand, e.g. 3, 4, 5, .... 
    val iter = { 
    def loop(v: Int): Stream[Int] = { println("I computed a value", v); v} #:: loop(v+1) 
    loop(start) 
    } 
    // Now, sometime later, we retrieve the values .... 
    println("about to loop") 
    for (x <- iter) { 
    if (x < 10) println("saw value", x) else return 
    } 
} 

Este código crea un flujo infinito que comienza en un valor dado y devuelve enteros sucesivos. Se utiliza como un sustituto de código más complejo que podría, por ejemplo, abrir una conexión a Internet y devolver valores de la conexión según sea necesario.

Resultado:

scala> runiter(3) 
(I computed a value,3) 
about to loop 
(saw value,3) 
(I computed a value,4) 
(saw value,4) 
(I computed a value,5) 
(saw value,5) 
(I computed a value,6) 
(saw value,6) 
(I computed a value,7) 
(saw value,7) 
(I computed a value,8) 
(saw value,8) 
(I computed a value,9) 
(saw value,9) 
(I computed a value,10) 

Nota cuidadosamente cómo la ejecución requerida para calcular el primer valor se produce antes del lugar donde se utilizan realmente los valores de la corriente. Si esta ejecución inicial implica, por ejemplo, abrir un archivo o conexión a Internet y hay una gran demora después de crear la secuencia y antes de que se use cualquiera de los valores, esto puede ser muy problemático: terminará con un descriptor de archivo abierto sentado alrededor, y lo que es peor, su conexión a Internet podría expirar, haciendo que todo falle.

Un simple intento de fijarlo con un flujo de vacío inicial no funciona:

def runiter(start: Int) { 
    // Create a stream that returns successive integers on demand, e.g. 3, 4, 5, .... 
    val iter = { 
    def loop(v: Int): Stream[Int] = { println("I computed a value", v); v} #:: loop(v+1) 
    Stream[Int]() ++ loop(start) 
    } 
    // Now, sometime later, we retrieve the values .... 
    println("about to loop") 
    for (x <- iter) { 
    if (x < 10) println("saw value", x) else return 
    } 
} 

Resultado (igual que antes):

scala> runiter(3) 
(I computed a value,3) 
about to loop 
(saw value,3) 
(I computed a value,4) 
(saw value,4) 
(I computed a value,5) 
(saw value,5) 
(I computed a value,6) 
(saw value,6) 
(I computed a value,7) 
(saw value,7) 
(I computed a value,8) 
(saw value,8) 
(I computed a value,9) 
(saw value,9) 
(I computed a value,10) 

Sin embargo, usted puede solucionar este problema cambiar la secuencia a un iterador con un iterador vacío inicial, aunque está lejos de ser obvio que este es el caso:

def runiter(start: Int) { 
    // Create an iterator that returns successive integers on demand, e.g. 3, 4, 5, .... 
    val iter = { 
    def loop(v: Int): Iterator[Int] = { println("I computed a value", v); Iterator(v)} ++ loop(v+1) 
    Iterator[Int]() ++ loop(start) 
    } 
    // Now, sometime later, we retrieve the values .... 
    println("about to loop") 
    for (x <- iter) { 
    if (x < 10) println("saw value", x) else return 
    } 
} 

Resultado:

scala> runiter(3) 
about to loop 
(I computed a value,3) 
(saw value,3) 
(I computed a value,4) 
(saw value,4) 
(I computed a value,5) 
(saw value,5) 
(I computed a value,6) 
(saw value,6) 
(I computed a value,7) 
(saw value,7) 
(I computed a value,8) 
(saw value,8) 
(I computed a value,9) 
(saw value,9) 
(I computed a value,10) 

Tenga en cuenta que si no se agrega el iterador vacío inicial, que se ejecutará en el mismo problema de eyaculación ejecución como con las corrientes.