haskell - 使用 Burstall & Darlington 的折叠/展开系统从线性递归版本派生的尾递归斐波那契数列

Question

低效(树递归)fib(n) 函数计算第 n 个斐波那契数。在 Haskell 中:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

使用以下身份:

gfib(n) = (fib(n), fib (n+1))

我们可以合成一个线性递归版本:

fib n = fst (gfib n)
    where gfib 0 = (0, 1)
          gfib n = (b, a + b)
              where (a, b) = gfib (n - 1)

另一方面，有一个著名的尾递归版本:

fib n = go n 0 1
    where go 0 a b = a
          go n a b = go (n - 1) b (a + b)

现在问题:

有没有办法使用 Burstall & Darlington 的折叠/展开技术从线性递归版本合成尾递归版本？我的目标是了解如何转换线性递归程序，以便将返回的元组转换为两个累积参数，从而使生成的程序是尾递归的。

上下文:函数式编程、程序综合/推导、程序转换、归纳

Answer 1

该转换称为 "accumulating" (例如，Bird 和 Gibbons 在 Haskell 中的算法设计中)。

fib n = fst (go n)
    where go 0 = (0, 1)
          go n = (b, a + b)
              where (a, b) = go (n - 1)

积累:

fib n = fst (go n (0, 1))
    where go 0 (a, b) = (a, b)
          go n (a, b) = go (n - 1) (b, a + b)

虽然应该注意，在这种情况下，累加很容易，因为向上或向下计数都没有关系(n 并未真正使用)。但总的来说，您应该注意结果函数仍然是正确的。

然后为了实现您想要的实现，您必须应用两个更简单的转换:

压入fst(我不知道这是不是一个常见的名字):

fib n = go n (0, 1)
    where go 0 (a, b) = a
          go n (a, b) = go (n - 1) (b, a + b)

柯里化(Currying):

fib n = go n 0 1
    where go 0 a b = a
          go n a b = go (n - 1) b (a + b)