在Scala中,从初始对象和生成下一个对象的函数创建O(1)-memory Iterable

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和朋友.

是否有方便的库方法来生产我想要的东西？

如果不,

有人可以建议使用'口语'Scala代码吗？

总而言之,给定一个初始对象a: A和一个函数f: A => A,我想生成一个TraversableLike(例如,可能是一个Iterable)生成a, f(a), f(f(a)), ...,并使用O(1)内存map,filter等等也返回O(1)的函数的函数.记忆.

Answer 1

Stream会做你想做的事,只是不要坚持细胞; 只迭代值.

这是一个令人遗憾的常见误解,Streams固有地缓存了他们计算的每个值.

如果你这样写:

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

那么确实保留了流产生的每个值,但这不是必需的.如果你写:

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

如果调用者只是遍历流的值但是不记得Stream值本身(特别是其任何cons单元格),则不会发生不需要的保留.当然,在这个公式中,每个调用都会Stream从固定的初始值创建一个新的开始.这没有必要:

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

你需要注意的一件事是将Stream方法传递给方法.这样做将捕获方法参数中传递的流的头部.解决此问题的一种方法是使用尾递归代码处理流.

Answer 2

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查看垃圾收集事件。