scala - 在 Scala 中是否有创建尾递归函数的通用方法？

Question

同时检查英特尔的 BigDL repo ，我偶然发现了这个方法:

private def recursiveListFiles(f: java.io.File, r: Regex): Array[File] = {
  val these = f.listFiles()
  val good = these.filter(f => r.findFirstIn(f.getName).isDefined)
  good ++ these.filter(_.isDirectory).flatMap(recursiveListFiles(_, r))
}

我注意到它不是尾递归的，所以决定写一个尾递归版本:

private def recursiveListFiles(f: File, r: Regex): Array[File] = {
@scala.annotation.tailrec def recursiveListFiles0(f: Array[File], r: Regex, a: Array[File]): Array[File] = {
  f match {
    case Array() => a
    case htail => {
      val these = htail.head.listFiles()
      val good = these.filter(f => r.findFirstIn(f.getName).isDefined)
      recursiveListFiles0(these.filter(_.isDirectory)++htail.tail, r, a ++ good)
    }
  }
}
recursiveListFiles0(Array[File](f), r, Array.empty[File])
}

与我习惯的相比，让这变得困难的是文件可以转换为数组 [File] 的概念，这增加了另一个层次。

具有以下成员的数据类型的递归背后的理论是什么？

def listTs[T]: T => Traversable[T]

Answer 1

简答

如果您概括这个想法并将其视为 monad(适用于任意类型参数的多态事物)，那么您将无法实现尾递归实现。

Trampolines 试图通过提供一种在不溢出堆栈的情况下评估递归计算的方法来解决这个问题。总体思路是创建成对的(结果，计算)流。因此，在每一步中，您都必须返回到该点为止的计算结果和一个创建下一个结果的函数(又名 thunk)。

来自 Rich Dougherty 的博客:

A trampoline is a loop that repeatedly runs functions. Each function, called a thunk, returns the next function for the loop to run. The trampoline never runs more than one thunk at a time, so if you break up your program into small enough thunks and bounce each one off the trampoline, then you can be sure the stack won't grow too big.

更多+引用

在分类意义上，这种数据类型背后的理论与 Cofree Monads 和 fold 和 unfold 函数密切相关，一般来说到 固定点类型。

看看这个精彩的演讲:Fun and Games with Fix Cofree and Doobie由 Rob Norris 撰写，其中讨论了一个与您的问题非常相似的用例。

这篇关于 Free monads 和 Trampolines 的文章也与你的第一个问题有关:Stackless Scala With Free Monads .

另请参阅 Matryoshka docs 的这一部分. Matryoshka是围绕 FixedPoint 类型的概念实现 monad 的 Scala 库。