假设我有一种用于长时间运行的计算的机制,可以暂停自己以便稍后恢复:
sealed trait LongRunning[+R];
case class Result[+R](result: R) extends LongRunning[R];
case class Suspend[+R](cont: () => LongRunning[R]) extends LongRunning[R];
运行它们的最简单方法是
@annotation.tailrec
def repeat[R](body: LongRunning[R]): R =
body match {
case Result(r) => r
case Suspend(c) => {
// perhaps do some other processing here
println("Continuing suspended computation");
repeat(c());
}
}
问题在于创建这样的计算。假设我们想要实现每 10 个周期暂停一次计算的尾递归阶乘:
@annotation.tailrec
def factorial(n: Int, acc: BigInt): LongRunning[BigInt] = {
if (n <= 1)
Result(acc);
else if (n % 10 == 0)
Suspend(() => factorial(n - 1, acc * n))
else
factorial(n - 1, acc * n)
}
但这不能编译:
错误:无法优化@tailrec
带注释的方法factorial
:它包含不在尾部位置的递归调用
Suspend(() => factorial(n - 1, acc * n))
如何在非挂起调用上保留尾递归?
我找到了一个可能的答案。当我们需要时,我们可以将尾递归部分移到内部函数中,并引用外部函数(非尾递归):
def factorial(n: Int, acc: BigInt): LongRunning[BigInt] = {
@annotation.tailrec
def f(n: Int, acc: BigInt): LongRunning[BigInt] =
if (n <= 1)
Result(acc);
else if (n % 10 == 0)
Suspend(() => factorial(n - 1, acc * n))
else
f(n - 1, acc * n)
f(n, acc)
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)