Haskell:改进我的尾递归斐波那契实现

我想出了以下有效的尾递归斐波那契生成器:

let {
  fibo :: Integral x => [x]->x->x->x->[x]
  fibo l x y 0 = l
  fibo l x y n = fibo (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)
}

请原谅我将整个实现放在一行中，因为我正在使用 GHCi 并且还没有完全学会如何将它放在一个文件中并运行(我还没有到达那里)。我想知道的是这个电话是如何调用的:

fibo [0, 1] 0 1 5

可以改进。我不想用 0 和 1 传递初始列表，然后再用限制传递 0 和 1。我相信实现是可以改变的。可以做哪些改变？

最佳答案

您的算法是尾递归的，但看起来它还有其他缺点，即 1)您正在通过附加到结果列表的末尾来构建结果列表，以及 2)它不是懒惰的。

对于 1)，请注意，当您附加两个列表 a ++ b 时，您基本上必须重新分配 a 。在您的情况下，a 是不断增长的斐波那契数列，b 是接下来的两个术语。因此，每次迭代都会重新分配已经计算过的斐波那契数，并添加另外两个元素，这将导致二次运行时间。将 b 放在 a 的前面会更有效。您将反向生成斐波那契数列，但运行时间将是线性的。如果您希望序列按升序排列，则可以在末尾对列表进行 reverse。

请注意，以相反的顺序构建列表允许您使用 Code-Guru 的模式匹配思想轻松获得序列的最后两项。

对于 2)，请注意，在整个计算完成之前，您无法获取列表的第一个元素。与以下序列的惰性生成进行比较:

fibs = 0 : (go 0 1)
  where go a b = b : go b (a+b)

尽管看起来递归从未停止，但 fibs 只会根据需要进行评估。例如，fibs !! 3 只调用 go 几次。

关于Haskell:改进我的尾递归斐波那契实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11656507/