scala - 在Scala中从初始对象和生成下一个对象的函数创建O(1)内存可迭代

Question

我想要一种便捷的方式来生成Iterable，给定一个初始对象和一个从当前对象产生下一个对象的函数，该函数消耗O(1)内存(即，它不缓存旧结果；如果要迭代)第二次，必须再次应用该功能)。

似乎没有库对此提供支持。在Scala 2.8中，方法scala.collection.Iterable.iterate具有签名

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

因此，它要求您提前指定感兴趣的迭代函数应用程序数量，而我对文档的理解是Iterable.iterate实际上会立即计算所有这些值。另一方面，方法scala.collection.Iterator.iterate具有签名

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

看起来不错，但我们只得到了Iterator，它并没有提供map，filter和 friend 的所有便利。

Is there a convenient library method to produce what I want?

如果不，

Can someone suggest the 'colloquial' Scala code for doing this?

总而言之，给定一个初始对象a: A和一个函数f: A => A，我想要一个TraversableLike(例如，可能是一个Iterable)来生成a, f(a), f(f(a)), ...，并使用O(1)内存，以及map，filter等函数，这些函数还返回一些内容就是内存中的O(1)。

Answer 1

带有过滤器的Iterator.iterate演示:

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

(这可能在REPL中不起作用，因为PRINT步骤可能会导致内存管理困惑)
JAVA_OPTS="-Xmx128m" scala -cp classes I将显示过滤有效并且是惰性的。如果未在恒定内存中完成操作，将导致堆错误(因为它分配的内存为900 * 10mb)。

使用JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I查看垃圾回收事件。