如何使用TailCalls？

Question

如果我理解正确,可以使用scala.util.control.TailCalls通过使用trampoline来避免非尾递归函数的堆栈溢出.API中给出的示例很简单:

import scala.util.control.TailCalls._

def isEven(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

def isOdd(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

isEven((1 to 100000).toList).result 

但是,更有趣的情况是,如果要在重新调用之后执行某些操作.我有一个"天真"的因子实现以某种方式运行

def fac(n:Long): TailRec[Long] = 
    if (n == 0) done(1) else done(n * tailcall(fac(n - 1)).result)

但这看起来很可怕,我怀疑这是用途.所以我的问题是如何使用TailCalls正确编写阶乘或斐波纳契函数(是的,我知道如何使用累加器来使它们尾递归)？或者TailCalls不适合这种问题吗？

Answer 1

是的,你的天真因子不会是尾递归的,并且会在参数的值中使用线性空间线性.scala.util.control.TailCalls的目的不是将非尾递归算法神奇地转换为尾递归算法.它的目的是允许相互尾调用的函数循环在恒定的堆栈空间中执行.

Scala编译器为在尾部位置调用自身的方法实现尾递归优化,允许调用方使用调用方法的堆栈帧.它主要通过将可证实的尾递归调用转换为while循环来实现这一点.但是,由于JVM限制,它无法实现尾调用优化,这将允许尾部位置的任何方法调用重用调用者的堆栈帧.这意味着如果您有两个或更多方法在尾部位置相互调用,则不会进行优化,并且存在堆栈溢出的风险.scala.util.control.TailCalls是一个黑客,可以让你解决这个问题.

BTW,非常值得查看scala.util.control.TailCalls的源代码."结果"调用是完成所有有趣工作的地方,它基本上只是一个while循环.

Answer 2

这个问题已经超过 6 年了，但接受的答案似乎没有回答这个问题：

所以我的问题是如何使用 TailCalls 正确编写阶乘或斐波那契函数（是的，我知道如何使用累加器使它们成为尾递归）？

所以，这里是：

object Factorial {

  /**
    * Returns the nth factorial
    */
  def apply(n: Long): BigInt = {
    if (n < 0)
      throw new IllegalArgumentException("Can't factorial to an index less than 0")
    else {
      import scala.util.control.TailCalls._
      def step(current: Long): TailRec[BigInt] = {
        if (current <= 0)
          done(1)
        else
          tailcall {
            for {
              next <- step(current - 1)
            } yield current * next
          }
      }
      step(n).result
    }
  }

}

assert(Factorial(0) == 1)
assert(Factorial(7) == 5040)
assert(Factorial(10) == 3628800)

使用 TailCalls 的一个重要用例是做一些类似右折叠的事情。