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

问题描述

编写在Stream上运行的函数时，有不同的递归概念.第一个简单意义不是在编译器级别上递归的，因为尾部如果没有立即求值，则函数会立即返回，但是返回的流是递归的:

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)

虽然编译，但此方法最终会导致内存泄漏.由于最终从recHelp函数调用了尾递归rec，因此recHelp函数的堆栈框架保留了对蒸汽压头的引用，并且直到调用返回，根据调用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).

请注意，即使在无助的情况下，如果编译器允许@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屋！