Haskell:改进我的尾部递归fibonacci实现

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几次电话.