Creazione di un memoriale O (1) Iterable da un oggetto iniziale e una funzione che genera l'oggetto successivo, in Scala

Question

Voglio un modo conveniente per generare un Iterable, dato un oggetto iniziale e una funzione per produrre l'oggetto successivo da quello corrente, che consuma memoria O (1) (cioè non memorizza i vecchi risultati, se si desidera ripetere una seconda volta, la funzione deve essere nuovamente applicata).

Non sembra che ci sia il supporto di libreria per questo. In Scala 2.8, il metodo scala.collection.Iterable.iterate ha la firma

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

quindi richiede di specificare quante applicazioni algoritmo iterativo che ti interessa prima del tempo, e la mia comprensione della documentazione è che Iterable.iterate calcola in realtà tutti questi valori subito. D'altra parte, il metodo scala.collection.Iterator.iterate ha la firma

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

che sembra grande, ma abbiamo solo ottenere un Iterator che non offre tutte le comodità di map, filter e gli amici.

Esiste un metodo biblioteca conveniente produrre quello che voglio?

e se non,

Qualcuno può suggerire il codice 'colloquiale' Scala per fare questo?

In sintesi, in un oggetto iniziale a: A, e una funzione f: A => A, Vorrei una TraversableLike (ad esempio, probabilmente un Iterable) che genera a, f(a), f(f(a)), ..., e utilizza O (1) di memoria, con map, filter ecc. funzioni che restituiscono anche qualcosa che è O (1) in 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)) } 
    } 
} 

(puo 'non funzionare nel REPL come il passo di stampa può rovinare con gestione della memoria)

JAVA_OPTS="-Xmx128m" scala -cp classes I mostrerà che i lavori di filtraggio ed è artificiale. Se non è stato fatto nella memoria costante, ciò causerebbe un errore di heap (poiché assegna qualcosa come 900 * 10mb).

Utilizzare JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I per visualizzare gli eventi di garbage collection.

Answer 2

Stream farà quello che vuoi, ma non aggrapparti alle celle; solo scorrere i valori.

È un malinteso tristemente comune che gira attorno al fatto che gli Stream memorizzano intrinsecamente ogni valore che calcolano.

Se si scrive questo:

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

allora davvero ogni valore prodotto dal flusso viene mantenuta, ma questo non è necessario. Se si scrive:

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

e se il chiamante solo itera oltre i valori del flusso, ma non ricorda il Value Stream stesso (ogni delle sue cellule cons), quindi si verificherà alcuna ritenzione indesiderata. Naturalmente, in questa formulazione, ogni chiamata crea un nuovo Stream a partire da un valore iniziale fisso. Che non è necessaria:

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

L'unica cosa che dovete guardare fuori per sta passando un Stream a un metodo. In questo modo si catturerà la testa dello stream trasmesso nel parametro method. Un modo per aggirare questo è elaborare lo stream con codice ricorsivo in coda.

Answer 3

Iterator è proprio ciò che desideri. E l'iteratore ha map, filter, takeWhile e molti altri metodi che è O (1) in memoria. Non penso che ci sia un altro tipo di raccolta con O (1) in memoria.

Answer 4

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

non provare su REPL (se non per incorporarlo all'interno di un oggetto o di classe), come REPL cercherà di stamparlo, e non usa toString.