如何在Scala中使用Stream.cons写入不泄漏的尾递归函数？

发布时间：2020-12-16 19:07:13 所属栏目：安全来源：网络整理

导读：当编写一个在Stream上运行的函数时,有不同的递归概念.第一个简单的意义在编译器级别不是递归的,因为尾部如果不能立即评估,所以函数立即返回,但返回的流是递归的： final def simpleRec[A](as: Stream[A]): Stream[B] = if (a.isEmpty) Stream.empty else som

当编写一个在Stream上运行的函数时,有不同的递归概念.第一个简单的意义在编译器级别不是递归的,因为尾部如果不能立即评估,所以函数立即返回,但返回的流是递归的：

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)

在编译时,这种方法最终会导致内存泄漏.由于最终从recHelp函数调用尾递归rec,recHelp函数的堆栈框架保存对蒸汽头的引用,并且不允许流被垃圾回收,直到rec调用返回,这可以很长(根据递归步骤),取决于对B的呼叫次数).

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

解决方法

你所暗示的问题是,在你粘贴的代码中,filterHelp函数会保留头(因此你的解决方案会被删除).

最好的答案是简单地避免这种令人惊讶的行为,使用Scalaz EphemeralStream,并且看起来它们都不会比运行得更快,并且运行得更快,因为它远比gc更好.它并不总是像例如工作一样简单.头是a()=> 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)

我会说,除非你有一个令人信服的理由使用Stream(其他图书馆依赖等),那么只要坚持使用EphemeralStream,那里的惊喜就会少得多.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!