scala - 将流参数转发给另一个函数的函数保留引用

Question

我能够编写一个流处理函数 drop(n,s)，它可以扩展到非常大的流。但是当我编写另一个函数 nth(n,s) 时，它接收流 s 并将其转发到 drop(n,s) ，似乎 nth() 正在“捕获流的头部”。对于较大的 n，这将导致 OutOfMemoryError。

代码如下:

import scala.annotation.tailrec
import scala.collection.immutable.Stream.cons

object Streams {

  def iterate[A](start: A, f: A => A): Stream[A] =
    cons(start, iterate(f(start), f))

  def inc(n:Int) = n + 1

  def naturals() =
    iterate(1, inc)

  @tailrec def drop[T](n : Int, s : Stream[T]) : Stream[T] =
    if (n <= 0 || s.isEmpty) s
    else drop(n-1, s.tail)

  // @inline didn't seem to help
  def nth[T](n : Int, s : Stream[T]) =
    drop(n,s).head

  def N = 1e7.toInt

  def main(args: Array[String]) {
    println(drop(N,naturals()).head) // works fine for large N
    println(nth(N, naturals())) // results in OutOfMemoryError for N set to 1e7.toInt and -Xmx10m
  }

}

我对这个 Java 问题的经验:why does this Java method leak—and why does inlining it fix the leak?让我相信 Scala 为 nth() 生成的代码在调用 drop() 之前清除 s 不够积极。 Clojure 库技巧(Java 技巧)(请参阅相关问题)在这里不起作用，因为所有 Scala 函数参数都是 val(不是 var)，所以它们不能t 被分配(null)。

如何根据 drop() 编写可扩展的 nth()？

这是 2009-2011 年的一个相关 Scala 编译器错误(reduceLeft() 根据 foldLeft() 实现):https://issues.scala-lang.org/browse/SI-2239

我无法从那张 Scala 故障单中看出他们是如何修复它的。票证中建议修复它的唯一方法是在 reduceLeft() 中复制 foldLeft() 代码。我真的希望这不是答案。

更新:Andrey Tyukin 的回答 https://stackoverflow.com/a/52209383/156550修复它。现在我有:

// have to call by name (s) here, otherwise we hold on to head!
def nth[T](n : Int, s : => Stream[T]) =
  drop(n,s).head

nth(n,s) 可以很好地缩放。

Answer 1

这是一个快速但简单的解决方案，只需要两个额外的字符:

def nth[T](n : Int, s: => Stream[T]) = drop(n,s).head

下面是没有 => 的情况:

• 当流 s 作为参数传递给 nth 时，它是对已经存在的值的引用，该值先前由 naturals()。
• 由于 .head，drop(n, s) 必须将流返回到 nth 的堆栈帧，因此nth 的堆栈帧不能被丢弃，因此 nth 保留引用 s。
• 因为参数s的引用保存在nth的栈帧中，而drop在起作用，所有被丢弃的前缀实际上不能被垃圾收集(这是因为 Stream 保证如果你捕获它的头部并多次迭代它，它将返回相同的结果)。

现在，如果您添加 =>，则会发生以下情况:

• nth 的栈帧由于.head 仍然不能被丢弃
• 但是:nth 不包含对传递给drop 的流头部的引用。它只包含对生成 Stream 的 thunk 的引用。
• thunk 本身不占用任何大量内存，并且它不持有对创建流的头部的任何引用，因此，流的前缀可以被垃圾收集。

---

附加说明(Dima 的测试用例):

请注意，如果 thunk 本身只是简单地返回对已存在的 Stream 的引用，那么行为仍然与没有 => 时相同。例如，如果您的 inc 定义如下:

def inc(i: Int): Int = {
  println(System.currentTimeMillis())
  i + 1
}

然后调用

val s = naturals()
nth(10, s)
nth(5, s)

只会打印当前时间十次(不是 15 次)。