Creazione di un (1) -Memoria Iterable da un oggetto O 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 il prossimo oggetto da quello attuale, che consuma O (1) di memoria (cioè, non memorizza nella cache i vecchi risultati, se si vuole iterare una seconda volta, la funzione deve essere applicato di nuovo).

E non sembra che ci sia il supporto 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]

in modo che richiede di specificare il numero di applicazioni iterata funzione che ti interessa prima del tempo, e la mia comprensione della documentazione è che in realtà Iterable.iterate calcola tutti questi valori immediatamente. 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 un Iterator che non offre tutte le comodità di map, filter e gli amici.

  

Esiste un metodo biblioteca conveniente produrre ciò che voglio?

e se non,

  

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

Per riassumere, dato un oggetto a: A iniziale, e una funzione f: A => A, vorrei un 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 tornare 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)) } 
  }
}

(Questo potrebbe non funzionare in REPL come il passo di stampa può rovinare con gestione della memoria)

JAVA_OPTS="-Xmx128m" scala -cp classes I mostrerà che le opere di filtraggio ed è pigro. Se non è stato fatto in ricordo costante che potrebbe causare un errore di heap (dal momento che è l'allocazione qualcosa come 900 10mb *).

Usa JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I per visualizzare gli eventi di raccolta dei rifiuti.

Answer 2

Stream farà ciò che si vuole, basta non tenere alle cellule; solo iterate sui valori.

E 'un errore comune, purtroppo galleggianti intorno che Streams intrinsecamente cache ogni valore che calcolano.

Se si scrive questo:

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

poi effettivamente ogni valore prodotto dal flusso viene mantenuto, ma questo non è necessario. Se si scrive:

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

e se il chiamante itera appena oltre i valori del flusso, ma non ricorda il valore di flusso in sé (in particolare una delle sue celle cons), allora si verificherà la ritenzione non indesiderata. Naturalmente, in questa formulazione, ogni chiamata crea un nuovo Stream partendo da un valore iniziale fisso. Non è necessario:

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 catturare il capo del flusso trasmesso nel parametro del metodo. Un modo per aggirare questo è quello di elaborare il flusso con il codice ricorsiva in coda.

Answer 3

Iterator è la cosa molto ciò che si desidera. E iteratore facciamo ha carta, filtri, TakeWhile e molti altri metodi che è O (1) nel memory.I non credo 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 cercare fuori su REPL (se non per incorporarlo all'interno di un oggetto o di classe), come REPL cercherà di stamparlo, e non usa toString.