哈斯克尔：提高我的尾递归斐波那契实现

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几次。

Answer 2

我不打算去算法本身，但这里有一些关于如何构建递归函数的建议。

首先，这里你将如何格式化一个单独的文件代码

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) 

如果您保存此为fibo.hs，那么你就可以

ghci fibo.hs 

开始GHCI加载文件在开始时。你也可以用命令

:l fibo.hs 

（assumming您在保存fibo.hs相同的目录开始GHCI）

另一个优点是，现在当你编辑的文件开始GHCI后加载文件，只需在GHCi提示符下输入

:r 

即可重新加载所有更改。

现在，为了摆脱额外的参数，Haskell中的常规模式是将递归部分重构为其自身的辅助函数，并将主函数作为仅接受必要参数的入口点。例如，

fibo :: Integral x => x -> [x] 
fibo n = fiboHelper [0,1] 0 1 n 

fiboHelper :: Integral x => [x]->x->x->x->[x] 
fiboHelper l x y 0 = l 
fiboHelper l x y n = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1) 

现在，您可以拨打fibo简单地

> fibo 3 
[0,1,1,2,3,5,8,13] 

此外，一个辅助函数像这样的是没有用的本身通常是隐藏在主函数中的使用let内部函数或where。

fibo :: Integral x => x -> [x] 
fibo n = fiboHelper [0,1] 0 1 n where 
    fiboHelper l x y 0 = l 
    fiboHelper l x y n = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1) 

像这样的内部函数通常给出一个较短的名称，因为背景使得其目的明确，所以我们可以将名称更改为如fibo'。

go是递归辅助函数的另一个常用名称。

Answer 3

只是为了记录：为斐波那契数的列表的“通常”的定义是：

fibo = 0 : scanl (+) 1 fibo