3

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

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

4

3 回答 3

7

您的算法是尾递归的，但它看起来还有其他缺点，即 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几次。

于 2012-07-25T19:28:36.173 回答
4

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

首先，这是在单独的文件中格式化代码的方法

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

ghci fibo.hs

在开始时加载文件。也可以在启动 GHCi 后使用命令加载文件

:l fibo.hs

（假设您在保存 fibo.hs 的同一目录中启动 GHCi）

另一个不错的功能是，现在当您编辑文件时，您只需输入即可重新加载所有更改

:r

在 GHCi 提示符中。

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

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]

此外，像这样本身无用的辅助函数通常作为内部函数隐藏在主函数中，使用letor 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)

像这样的内部函数通常被赋予一个较短的名称，因为上下文清楚地说明了它的用途，所以我们可以将名称更改为 eg fibo'。

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

于 2012-07-25T19:37:40.233 回答
3

仅作记录：斐波那契数列的“通常”定义是：

fibo = 0 : scanl (+) 1 fibo
于 2012-07-26T13:01:30.167 回答