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

Question

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

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。我相信实现是可以改变的。可以做哪些改变？

Answer 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一些时间。