如何在Scala中使用Stream.cons编写非泄漏尾递归函数？

Question

当编写在Stream(s)上运行的函数时,存在不同的递归概念.第一个简单的意义在编译器级别上不是递归的,因为如果不立即计算尾部,那么函数会立即返回,但返回的流是递归的:

final def simpleRec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              
  else someB(a.head) #:: simpleRec(a.tail) 

上述递归概念不会引起任何问题.第二个是在编译器级别上真正的尾递归:

@tailrec
final def rec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              // A) degenerated
  else if (someCond) rec(a.tail)           // B) tail recursion
  else someB(a.head) #:: rec(a.tail)       // C) degenerated

这里的问题是C)编译器将该情况检测为非tailrec调用,即使没有执行实际调用.这可以通过将流尾部分解为辅助函数来避免:

@tailrec
final def rec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              
  else if (someCond) rec(a.tail)          // B)
  else someB(a.head) #:: recHelp(a.tail)  

@tailrec
final def recHelp[A](as: Stream[A]): Stream[B] = 
  rec(as)

在编译时,这种方法最终会导致内存泄漏.由于尾递归rec最终是从recHelp函数调用的,函数的堆栈帧recHelp保存了对蒸汽头的引用,并且在rec调用返回之前不会让流被垃圾收集,这可能会很长(就递归步骤)取决于调用次数B).

请注意,即使在无帮助的情况下,如果编译器允许@tailrec,则内存泄漏可能仍然存在,因为惰性流尾部实际上会创建一个保持对流头部的引用的匿名对象.

Answer 1

正如您所暗示的那样，问题在于您粘贴的代码中 filterHelp 函数保留了头部（因此您的解决方案将其删除）。

最好的答案是简单地避免这种令人惊讶的行为，使用 Scalaz EphemeralStream 并看到它不会 oom 并且运行速度明显更快，因为它对 gc 更好。它的使用并不总是那么简单，例如 head is a () => A not A，没有提取器等，但它都适合一个目标、可靠的流使用。

您的 filterHelper 函数通常不必关心它是否保留引用：

import scalaz.EphemeralStream

@scala.annotation.tailrec
def filter[A](s: EphemeralStream[A], f: A => Boolean): EphemeralStream[A] = 
  if (s.isEmpty) 
    s
  else
    if (f(s.head())) 
      EphemeralStream.cons(s.head(), filterHelp(s.tail() , f) )
    else
      filter(s.tail(), f)

def filterHelp[A](s: EphemeralStream[A], f: A => Boolean) =
  filter(s, f)

def s1 = EphemeralStream.range(1, big)

我什至想说，除非您有令人信服的理由使用 Stream（其他库依赖项等），然后坚持使用 EphemeralStream，否则惊喜要少得多。