Haskell：改善我的尾递归斐波那契实现

Question

Haskell：改善我的尾递归斐波那契实现

4

我想分享一个尾递归的斐波那契数列生成器，可以正常工作：

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。我相信实现可以改变。有哪些改变可以进行？

- badmaash

你可以像在解释器中一样，逐行将代码写入文件中（无需将所有内容都包装在 let 块中），然后在解释器中加载该文件（在 GHCi 中使用 :l 文件名）。 - Cubic

你的代码是尾递归的，但仍然非常低效，因为(++)在其第一个参数上是线性的。但我猜这不是问题的一部分。 - Joachim Breitner

2

Haskell中的尾递归不像严格语言那样需要常量堆栈使用，而非尾递归也不需要线性堆栈使用，因此我质疑您的练习的价值。老实说，我会选择经典的fibs = 0：1：zipWith（+）fibs（tail fibs）或其带有scanl或unfoldr变体之一。请参见此HaskellWiki页面以获取一堆实现。 - Luis Casillas

3个回答

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 中通常的模式是将递归部分重构为自己的辅助函数，并将主函数作为只接受必要参数的入口点。例如，

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 是另一个常用的递归辅助函数的名称。

- shang

3

仅供参考：斐波那契数列的“通常”定义如下：

fibo = 0 : scanl (+) 1 fibo

- Landei

1

或者（稍微简单一些）fibo = 0：1：zipWith（+）fibo（tail fibo）。 - fuz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ErikR · Accepted Answer

您的算法是尾递归的，但似乎有其他缺点，即1）您正在通过将元素附加到列表末尾来构建结果列表，2）它不是惰性的。

对于第一点，请注意，当您附加两个列表a ++ b时，您实际上必须重新分配a。在您的情况下，a是已计算出的斐波那契数列增长的列表，而b是下一个两项。因此，每次迭代都会重新分配已经计算出的斐波那契数列，并添加两个更多的元素，这将导致二次运行时间。更有效的方法是将b前置到a的前面。这样，您将以相反的顺序生成斐波那契数列，但运行时间将是线性的。如果要按升序获取序列，则可以在最后使用reverse函数来反转列表。

请注意，按照相反的顺序构建列表可让您轻松获取代码大师提出的模式匹配思想中的最后两个序列项。

对于第二点，请注意，直到整个计算完成之前，您无法获得列表的第一个元素。与以下惰性生成序列进行比较：

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

虽然看起来递归从未停止，但 fibs 只计算所需的部分。例如，fibs !! 3 只调用 go 几次。