Creando una O (1) -memoria Iterable de un objeto inicial y una función que genera el siguiente objeto, en Scala

Question

Quiero una forma conveniente de generar un Iterable, dado un objeto inicial y una función para producir el siguiente objeto de el actual, que consume O (1) memoria (es decir, no almacena en caché los resultados anteriores, si desea iterar por segunda vez, la función debe aplicarse nuevamente).

Parece que no hay soporte de biblioteca para esto. En Scala 2.8, el método tiene la firma scala.collection.Iterable.iterate

def iterate [A] (start: A, len: Int)(f: (A) ⇒ A) : Iterable[A] 

por lo que requiere que se especifique el número de aplicaciones de funciones iteradas que le interesa antes de tiempo, y mi comprensión de la documentación es que en realidad Iterable.iterate calcula todos estos valores inmediatamente. Por otra parte, el método tiene la firma scala.collection.Iterator.iterate

def iterate [T] (start: T)(f: (T) ⇒ T) : Iterator[T] 

la que se ve muy bien, pero sólo recibe un Iterator que no ofrece todas las ventajas de map, filter y amigos.

¿Existe un método de biblioteca conveniente para producir lo que quiero?

y si no,

Puede alguien sugerir el código Scala 'coloquial' para hacer esto?

En resumen, dado un objeto inicial a: A, y una función de f: A => A, me gustaría un TraversableLike (por ejemplo, probablemente un Iterable) que genera a, f(a), f(f(a)), ..., y utiliza O (1) de memoria, con map, filter etc. funciones que también devuelven algo que es O (1) en la memoria.

Answer 1

Iterator.iterate demo con filtro:

object I { 
    def main(args:Array[String]) { 
    val mb = 1024 * 1024 
    val gen = Iterator.iterate(new Array[Int](10 * mb)){arr => 
     val res = new Array[Int](10 * mb) 
     arr.copyToArray(res) 
     println("allocated 10mb") 
     res(0) = arr(0) + 1 // store iteration count in first elem of new array 
     res 
    } 
    // take 1 out of 100 
    val gen2 = gen filter (arr => arr(0) % 100 == 0) 
    // print first 10 filtered 
    gen2.take(10).foreach { arr => println("filtered " + arr(0)) } 
    } 
} 

(esto puede no funcionar en el REPL como el paso de impresión puede estropear con la gestión de memoria)

JAVA_OPTS="-Xmx128m" scala -cp classes I mostrará que las obras de filtrado y es perezoso. Si no se hizo en la memoria constante eso causaría un error de montón (ya que está asignando algo como 900 * 10mb).

Utilice JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I para ver los eventos de recolección de basura.

Answer 2

Stream hará lo que quiera, simplemente no se aferre a las celdas; solo iterar sobre los valores.

Es una idea errónea tristemente común que flota alrededor de que los flujos inherentemente almacenan en caché cada valor que calculan.

Si se escribe esto:

val s1: Stream[Thing] = initialValue #:: «expression computing next value» 

continuación, de hecho cada valor producido por la corriente se mantiene, pero esto no es necesario. Si se escribe:

def s2: Stream[Thing] = initialValue #:: «expression computing next value» 

y si la persona que llama sólo itera sobre los valores de la corriente, pero no recuerda el valor corriente en sí (en concreto cualquiera de sus cons cells), no se realizará la retención no deseada. Por supuesto, en esta formulación, cada llamada crea un nuevo Stream a partir de un valor inicial fijo. Eso no es necesario:

def s3(start: Thing): Stream[Thing] = start #:: «expression computing next value» 

Lo único que hay que tener en cuenta es pasar un Stream a un método. Al hacerlo, se capturará el encabezado de la secuencia pasada en el parámetro del método. Una forma de evitar esto es procesar la secuencia con código recursivo de cola.

Answer 3

Iterator es lo que usted desea. Y iterator do tiene map, filter, takeWhile y muchos otros métodos que son O (1) en la memoria. No creo que haya otro tipo de colección con O (1) en la memoria.

Answer 4

val it = new Iterable[Int] { 
    def iterator = Iterator.iterate(0)(_+1) 
    override 
    def toString: String = "Infinite iterable" 
} 

No lo pruebe en REPL (excepto insertándolo dentro de un objeto o clase), como REPL intentará imprimirlo, y no utiliza toString.