Erstellen ein O (1) -Speicher Iterable von einem Anfang Objekt und eine Funktion, die das nächste Objekt erzeugt, in Scala

Question

Ich möchte eine bequeme Möglichkeit, einen Iterable zu erzeugen, da ein Anfangs Objekt und eine Funktion das nächste Objekt aus dem aktuellen zu erzeugen, dass Verbraucht O (1) Speichern (dh, es nicht Cache alten Ergebnisse, wenn Sie ein zweites Mal zu wiederholen will, muss die Funktion wieder angewandt werden).

Es scheint nicht, wie es Bibliothek Unterstützung für diese. 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 berechnet tatsächlich alle diese sofort Werte. Auf der anderen Seite hat das Verfahren scala.collection.Iterator.iterate Signatur

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

, die sieht gut aus, aber wir haben nur eine Iterator bekommen, die nicht alle den Komfort map, filter und Freunde bietet.

Gibt es eine bequeme Bibliothek Methode zu produzieren, was ich will?

und wenn nicht,

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

Um es zusammenzufassen, gegeben eine erste Objekt a: A und eine Funktion f: A => A, würde ich einen TraversableLike verwenden (zB wahrscheinlich ein Iterable), die a, f(a), f(f(a)), ... erzeugt und verwendet O (1) Speicher, mit map, filter usw. Funktionen, auch etwas zurückgeben, die O (1) im Speicher vorhanden 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 möglicherweise nicht in der REPL als PRINT Schritt kann mit Speicherverwaltung mess up)

JAVA_OPTS="-Xmx128m" scala -cp classes I wird zeigen, dass die Filterung funktioniert und faul ist. Wenn es nicht in konstanten Speichern getan wurde, das einen Haufen Fehler verursachen würde (da es so etwas wie 900 * 10mb Zuweisung).

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

Answer 2

Stream wird tun, was Sie wollen, halten einfach nicht an die Zellen auf; nur Iterierte über die Werte.

Es ist ein verbreiteter Irrtum, leider im Umlauf, dass Ströme von Natur jeden Wert zwischenzuspeichern sie berechnen.

Wenn Sie schreiben, um diese:

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 iteriert nur die Werte des Stroms, sondern erinnert sich nicht an den Stream-Wert selbst (insbesondere jede seiner Nachteile Zellen), dann keine unerwünschte Retention auftreten. Natürlich in dieser Formulierung erzeugt jeder Anruf einen neuen Stream von einem festen Anfangswert beginnt. Das ist nicht nötig:

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

Das einzige, was Sie zu achten haben, ist vorbei eine Stream ein Verfahren. Dadurch wird der Kopf des Stroms in dem Methodenparameter übergeben erfassen. Eine Möglichkeit, dies zu umgehen ist es, den Strom mit tail-rekursive Code zu verarbeiten.

Answer 3

Iterator ist genau das, was, was Sie wollen. Und Iterator tun hat Karte, Filter, Takewhile und viele andere Methoden, die O (1) in memory.I ist glaube nicht, gibt es eine weitere Sammlung Typen mit O (1) im Speicher.

Answer 4

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

Sie es nicht auf REPL ausprobieren (mit Ausnahme von ihm innerhalb eines Objekts oder einer Klasse Einbettung), wie REPL werden versuchen, es zu drucken, und es nicht toString verwenden.