如何使这个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)
}

由于我不明显的原因,结果的顺序与原始函数不同.但是,它看起来像是有效的:-)固定.