scala - 如何使此Scala函数(一种 “flatMap”变体)尾部递归？

Question

我在看下面的代码

http://aperiodic.net/phil/scala/s-99/p26.scala

具体来说

def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
    }

我收到较大值的StackOverflowError大概是因为该函数不是尾部递归的。有没有一种方法可以转换功能以容纳大量数字？

Answer 1

绝对不是尾递归。 f(sublist) :::正在修改递归调用的结果，使其成为普通的老栈吹嘘式递归，而不是尾部递归。

确保函数是尾部递归的一种方法是将@annotation.tailrec放在您希望是尾部递归的任何函数上。如果编译器无法执行尾部调用优化，则将报告错误。

为此，我将添加一个小的辅助函数，该函数实际上是尾递归的:

def flatMapSublistsTR[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = {
  @annotation.tailrec
  def helper(r: List[B], ls: List[A]): List[B] = {
    ls match {
      case Nil => r
      case sublist@(_ :: tail) => helper(r ::: f(sublist), tail)
    }
  }
  helper(Nil, ls)
}

出于对我来说并不立即显而易见的原因，结果的输出顺序与原始函数的顺序不同。但是，它似乎起作用了:-)固定。