Erstellen eines O (1) -memory Iterable von einem Anfangsobjekt und einer Funktion, die das nächste Objekt erzeugt, in Scala

Question

Ich möchte einen Iterable mit einem Anfangsobjekt und einer Funktion zum Erzeugen des nächsten Objekts erstellen das aktuelle, das O (1) Speicher verbraucht (dh es speichert keine alten Ergebnisse; wenn Sie es ein zweites Mal wiederholen wollen, muss die Funktion erneut angewendet werden).

Es scheint nicht, dass es Bibliotheksunterstützung dafür gibt. In Scala 2.8 hat das Verfahren scala.collection.Iterable.iterate Signatur

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

so erfordert es, dass Sie angeben, wie viele iterierte Funktionsanwendungen Sie in vor der Zeit interessiert sind, und mein Verständnis der Dokumentation ist, dass Iterable.iterate alle tatsächlich berechnet diese Werte sofort. Auf der anderen Seite hat das Verfahren scala.collection.Iterator.iterate Unterschrift

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

, die sieht gut aus, aber wir haben nur ein Iterator bekommen, die nicht den Komfort von map, filter und Freunden bietet.

Gibt es eine bequeme Bibliotheksmethode, um zu produzieren, was ich will?

und wenn nicht,

Kann jemand den 'umgang' Scala Code vorschlagen, dies zu tun?

Zusammenfassend wird ein Anfangsobjekt a: A gegeben, und eine Funktion f: A => A, würde Ich mag eine TraversableLike (zB wahrscheinlich eine Iterable), die a, f(a), f(f(a)), ... erzeugt und verwendet O (1) Speicher, mit map, filter usw. Funktionen, die auch etwas zurückgeben, das O (1) im Speicher ist.

Answer 1

Iterator.iterate Demo mit Filter:

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)) } 
    } 
} 

(dies kann nicht als PRINT Schritt kann mess up mit Speicherverwaltung in der REPL arbeiten)

JAVA_OPTS="-Xmx128m" scala -cp classes I wird zeigen, dass die Filterwerke und faul ist. Wenn es nicht im konstanten Speicher getan wurde, würde das einen Heap-Fehler verursachen (da es etwas wie 900 * 10mb zuweist).

Verwenden JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I die Garbage Collection Ereignisse zu sehen.

Answer 2

Stream tun Sie, was Sie wollen, halten Sie einfach nicht an den Zellen fest; Iteriere nur über die Werte.

Es ist ein häufig anzutreffendes Missverständnis, dass Streams jeden Wert, den sie berechnen, in Cache speichern.

Wenn Sie schreiben:

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

dann in der Tat jeder Wert durch den Strom erzeugt wird beibehalten, aber dies ist nicht erforderlich. Wenn Sie schreiben:

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

und wenn der Anrufer gerade iteriert über die Werte der Strom aber erinnert sich nicht an den Stream-Wert selbst (genauer gesagt eine ihrer Nachteile Zellen), dann keine unerwünschte Retention auftreten. Natürlich erzeugt bei dieser Formulierung jeder Anruf ausgehend von einem festen Anfangswert einen neuen Stream. Das ist nicht nötig:

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

Das einzige, was Sie zu achten haben, ist ein Stream auf eine Methode übergeben. Dadurch wird der Kopf des im method-Parameter übergebenen Streams erfasst. Eine Möglichkeit besteht darin, den Stream mit tailrekursivem Code zu verarbeiten.

Answer 3

Iterator ist genau das, was, was Sie wollen. Und Iterator hat Map, Filter, TakeWhile und viele andere Methoden, die O (1) im Speicher ist. Ich glaube nicht, dass es einen anderen Sammlungstyp mit O (1) im Speicher gibt.

Answer 4

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

Versuchen Sie es nicht auf REPL (ausgenommen durch sie innerhalb eines Objekts oder einer Klasse Einbettung), wie REPL werden versuchen, es zu drucken, und es nicht toString nicht verwendet.