在 Scala 中，从初始对象和生成下一个对象的函数创建 O(1) 内存 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 的所有便利。代码>地图，<代码>过滤器和朋友。

是否有方便的库方法来生成我想要的内容？

如果没有，

有人可以建议执行此操作的“口语”Scala 代码吗？

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

Answer 1

Stream 会做你想做的事，只是不要保留单元格；仅迭代值。

这是一个常见的误解，认为 Stream 本质上会缓存它们计算的每个值。

如果你这样写：

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

那么确实会保留流产生的每个值，但这不是必需的。如果你写：

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

并且如果调用者只是迭代流的值但不记住流值本身（特别是它的任何 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 查看垃圾收集事件。

Answer 3

迭代器正是您想要的东西。而且迭代器确实有map，filter，takeWhile和许多其他方法，在内存中的复杂度为O(1)。我不认为还有另一种集合类型在内存中的复杂度为O(1)。

Answer 4

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

不要在 REPL 上尝试（除非将其嵌入到对象或类中），因为 REPL 会尝试打印它，并且它不使用 toString。