Creating an O (1) -ememory Iterable from the source object and the function that generates the next object in Scala

Question

I want a convenient way to generate an Iterable , a given starting object and a function, to create the next object from the current one that consumes O (1) memory (i.e. does not cache the old results; if you want to iterate a second time, the function must be applied again )

The library does not seem to support the library. In Scala 2.8, the scala.collection.Iterable.iterate method has a signature

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

therefore, it is required that you indicate how many iterative functional applications you are interested in in advance, and my understanding of the documentation is that Iterable.iterate actually calculates all these values ​​immediately. The scala.collection.Iterator.iterate method, on the other hand, has a signature

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

which looks great, but we only get an Iterator that does not offer all the amenities of map , filter and friends.

Is there a convenient library method for creating what I want?

And if not,

Can anyone suggest a "colloquial" Scala code for this?

To summarize, given the starting object a: A and the function f: A => A , I would like to use a TraversableLike (e.g., possibly Iterable ) that generates a, f(a), f(f(a)), ... and uses O (1) memory, with map , filter , etc. functions that also return what is O (1) in memory.

Answer 1

Iterator.iterate demo with 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)) } } } 

(this may not work in REPL, as the PRINT step may corrupt memory management)

JAVA_OPTS="-Xmx128m" scala -cp classes I will show that filtering works and is lazy. If this was not done in read-only memory, which could cause a heap error (since it allocates something like 900 * 10 MB).

Use JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I to see garbage collection events.

Answer 2

Stream will do what you want, just don’t hold onto the cells; only iterate over the values.

This is a notorious misconception floating around the fact that threads essentially cache every value that they calculate.

If you write this:

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

then indeed every value created by the stream is saved, but this is not necessary. If you write:

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

and if the caller simply iterates over the values ​​of the stream, but does not remember the value of Stream itself (in particular, any of its cons cells), then unwanted saving will not occur. Of course, in this statement, each call creates a new Stream , starting with a fixed initial value. It's not obligatory:

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

The only thing you need to pay attention to is to pass the Stream method to the method. This will capture the stream header passed in the method parameter. One way is to process the stream using tail recursive code.

Answer 3

An iterator is what you want. An iterator has a map, a filter, takeWhile and many other methods that are O (1) in memory. I do not think that there is another type of collection with O (1) in memory.

Answer 4

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

Do not try to use REPL (except nesting it inside an object or class), as REPL will try to print it and it does not use toString .