如何在 Scala 中使用 Stream.cons 编写非泄漏尾递归函数? [英] How to write non-leaking tail-recursive function using Stream.cons in Scala?

问题描述

在编写一个操作 Stream(s) 的函数时，有不同的递归概念.第一个简单的意义在编译器级别上不是递归的，因为如果不立即计算尾部，则函数立即返回，但返回的流是递归的:

When writing a function operating on Stream(s), there are different notions of recursion. The first simple sense is not recursive on the compiler level, since the tail if not evaluated instantly so the function returns immediately, but the returned stream is recursive:

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

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

The above notion of recursion doesn't cause any problems. The second one is truly tail-recursive on the compiler level:

@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 调用，即使没有执行实际调用.这可以通过将流尾分解为辅助函数来避免:

The problem here is that the C) case is detected by the compiler as a non-tailrec call, even if there is no actual call carried out. This can be avoided by factoring out the stream tail into a helper function:

@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函数的栈帧保存了对steam头的引用，并且在 rec 调用返回之前不会让流被垃圾收集，这可能会很长(就递归步骤而言)，具体取决于对 B) 的调用次数.

While it compiles, this approach eventually results in a memory leak. Since the tail-recursive rec is eventually called from the recHelp function, the stack frame of the recHelp function holds a reference to the steam head, and doesn't let the stream to be garbage collected until the rec call returns, which can quite long (in terms of recursion steps) depending on the number of calls to B).

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

Note that even in the helperless case, if the compiler allowed the @tailrec, the memory leak may still be present since the lazy stream tail would in effect create an anonymous object holding reference to the stream head.

推荐答案

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

The problem, as you've hinted, is that in the code you pasted the filterHelp function keeps the head (hence your solution removing it).

最好的答案是简单地避免这种令人惊讶的行为，使用 Scalaz EphemeralStream 并看到它既不 oom 又运行明显更快，因为它比 gc 好得多.它并不总是那么简单，例如head 是 () => A 不是 A，没有提取器等，但它都面向一个客观、可靠的流使用.

Best answer is to simply avoid this surprising behaviour, use Scalaz EphemeralStream and see it both not oom and run significantly faster as its far nicer to the gc. Its not always as simple to work with e.g. head is a () => A not A, no extractors etc, but its all geared to one objective, reliable stream usage.

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

Your filterHelper function generally doesn't have to care about if it keeps a reference around:

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，那里的惊喜要少得多.

I'd go so far as to say that unless you have a compelling reason to use Stream (other library dependencies etc) then just stick to EphemeralStream, there are far less surprises there.

这篇关于如何在 Scala 中使用 Stream.cons 编写非泄漏尾递归函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！