如何转换ackermann函数的变体以支持尾部调用？
我目前正在解决一个问题，那就是在scala中实现ackermann函数的一个变体，并支持尾部调用优化，这样堆栈就不会溢出。
问题是，我找不到一种尾部调用优化它的方法。有人告诉我继续传递样式( CPS )会有帮助，但即使我成功地用CPS样式重新实现了它，我仍然迷失了方向。
ackermann函数的变化如下：
ppa(p, a, b) = p(a, b) (if a <= 0 or b <= 0)
ppa(p, a, b) = p(a, ppa(p, a-1, b)) (if p(a, b) is even and a, b > 0)
ppa(p, a, b) = p(ppa(p, a, b-1), b) (if p(a, b) is odd and a, b > 0)没有优化的代码如下：
def ppa(p: (Int, Int) => Int, a: Int, b: Int): Int = {
def ppa_cont(a: Int, b: Int, ret: (Int, Int) => Int): Int = {
if (a <= 0 || b <= 0) ret(a, b)
else (a, b) match {
case (_, _) if (p(a, b) % 2 == 0) => ret(a, ppa_cont(a-1, b, (x, y) => ret(x, y)))
case (_, _) => ret(ppa_cont(a, b-1, (x, y) => ret(x, y)), b)
}
}
ppa_cont(a, b, p)
}另一个试验是这样的：
def ppa(p: (Int, Int) => Int, a: Int, b: Int): Int = {
def ppa_cont(a: Int, b: Int, cont: (Int, Int) => Int): (Int, Int) => Int = {
if (a <= 0 || b <= 0) cont
else if (p(a, b) % 2 == 0) (a, b) => cont(a, ppa_cont(a-1, b, cont)(a-1, b))
else (a, b) => cont(ppa_cont(a, b-1, cont)(a, b-1), b)
}
ppa_cont(a, b, p)(a, b)
}我试着这样尾部调用optimize it：
def ppa(p: (Int, Int) => Int, a: Int, b: Int): Int = {
@annotation.tailrec
def ppa_cont(a: Int, b: Int, ret: (Int, Int) => TailRec[Int]): TailRec[Int] = {
if (a <= 0 || b <= 0) tailcall(ret(a, b))
else (a, b) match {
case (_, _) if (p(a, b) % 2 == 0) => {
tailcall(ret(a, ppa_cont(a-1, b, (x, y) => ret(x-1, y))))
}
case (_, _) => {
tailcall(ret(ppa_cont(a, b-1, (x, y) => ret(x, y-1)), b))
}
}
}
val lifted: (Int, Int) => TailRec[Int] = (x, y) => done(p(x, y))
ppa_cont(a, b, lifted).result
}但由于类型不匹配，这将无法编译。
可能的问题是什么？我走错方向了吗？小提示和帮助之手将不胜感激。Thx :)
回答 1
Stack Overflow用户
发布于 2020-10-09 04:39:43
尝试使用cats.free.Trampoline或scala.util.control.TailCalls.TailRec。它不是@tailrec，而是堆栈安全。
import scala.util.control.TailCalls._
def ppa(p: (Int, Int) => Int, a: Int, b: Int): Int = {
def hlp(a: Int, b: Int): TailRec[Int] = {
if (a <= 0 || b <= 0) done(p(a, b))
else if (p(a, b) % 2 == 0) tailcall(hlp(a - 1, b)).map(p(a, _))
else tailcall(hlp(a, b - 1)).map(p(_, b))
}
hlp(a, b).result
}http://eed3si9n.com/herding-cats/stackless-scala-with-free-monads.html
http://eed3si9n.com/herding-cats/tail-recursive-monads.html
实际上你的函数看起来不像Ackermann。实际的Ackermann进行了两次递归调用
f(m, n) = f(m - 1, f(m, n - 1))你的函数进行单次递归调用。编写函数的迭代版本并不难(通常使用尾递归，因为编译器可以自动将其转换为迭代版本)。假设我们已经计算了0 <= i <= a - 1，0 <= j <= b - 1 (黄色区域)的ppa(i, j)。然后，我们计算两个橙色段(a, 0), (a, 1), ..., (a, b - 1) (按此顺序)和(0, b), (1, b), ..., (a - 1, b) (按此顺序)。然后我们计算红细胞(a, b)。
https://stackoverflow.com/questions/64268960
复制相似问题
腾讯云开发者
