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

Stack Overflow用户

提问于 2012-09-21 11:32:35

回答 2查看 2.7K关注 0票数 14

当编写一个在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，内存泄漏可能仍然存在，因为惰性流尾部实际上会创建一个匿名对象，其中包含对流头部的引用。

stream

scala

recursion

memory-leaks

回答 2

Stack Overflow用户

回答已采纳

发布于 2012-09-29 10:41:57

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

最好的答案是简单地避免这种令人惊讶的行为，使用Scalaz EphemeralStream，并看到它既不是oom，而且运行速度要快得多，因为它对gc更好。使用它并不总是那么简单，例如head是一个() => A而不是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)

我甚至要说，除非你有令人信服的理由使用流(其他库依赖等)，否则就坚持使用EphemeralStream，那里就不会有太多的惊喜。

票数 2

Stack Overflow用户

发布于 2012-09-21 11:32:35

一种可能的解决方法是使recHelp方法不包含对流标头的引用。这可以通过将一个包装的流传递给它，并改变包装器以擦除其中的引用来实现：

@tailrec
final def rec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              
  else if (someCond) rec(a.tail)          
  else {
    // don't inline and don't define as def,
    // or anonymous lazy wrapper object would hold reference
    val tailRef = new AtomicReference(a.tail)
    someB(a.head) #:: recHelp(tailRef)  
  }

@tailrec
final def recHelp[A](asRef: AtomicReference[Stream[A]]): Stream[B] = 
  // Note: don't put the content of the holder into a local variable
  rec(asRef.getAndSet(null))