Haskell低效fibonacci实现

Question

我是haskell的新手，刚刚开始学习函数式编程的乐趣。但是在斐波那契函数的实现上遇到了麻烦。请找到下面的代码。

--fibonacci :: Num -> [Num]
fibonacci 1 = [1]
fibonacci 2 = [1,1]
--fibonacci 3 = [2]
--fibonacci n = fibonacci n-1
fibonacci n = fibonacci (n-1) ++ [last(fibonacci (n-1)) + last(fibonacci (n-2))]

很尴尬，我知道。我找不到时间去查一查，写一个更好的。尽管我想知道是什么让它如此低效。我知道我应该去查一查，只是希望有人会觉得有必要做个有教养的人，省下我的力气。

Answer 1

orangegoat's answer和Sec Oe's answer包含一个链接，该链接可能是学习如何在Haskell中正确编写斐波那契数列的最佳位置，但这里有一些代码效率低下的原因(请注意，您的代码与传统的naive definition没有太大不同。优雅？好的。高效？天哪，没有)：

让我们考虑一下当您调用

fibonacci 5

它扩展为

(fibonacci 4) ++ [(last (fibonacci 4)) + (last (fibonacci 3))]

除了使用++将两个列表连接在一起之外，我们已经可以看到我们效率低下的一个地方是我们计算两次fibonacci 4 (这两个地方我们称为fibonacci (n-1)。但更糟的是。

无论它在哪里说fibonacci 4，它都会扩展为

(fibonacci 3) ++ [(last (fibonacci 3)) + (last (fibonacci 2))]

无论它在哪里说fibonacci 3，它都会扩展为

(fibonacci 2) ++ [(last (fibonacci 2)) + (last (fibonacci 1))]

显然，这个天真的定义有很多重复的计算，当n越来越大(比如1000)时，它只会变得更糟。fibonacci不是一个列表，它只返回列表，所以它不会神奇地记忆之前计算的结果。

此外，通过使用last，您必须在列表中导航以获取它的最后一个元素，这增加了这种递归定义的问题(请记住，Haskell中的列表不支持常量时间随机访问--它们不是动态数组，它们是linked lists)。

在计算中保留的递归定义(来自提到的链接)的一个示例如下：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

这里，fibs实际上是一个列表，我们可以利用Haskell的惰性计算来根据需要生成fibs和tail fibs，而之前的计算仍然存储在fib中。要得到前五个数字，就像下面这样简单：

take 5 fibs -- [0,1,1,2,3]

(或者，如果希望序列从1开始，可以将前0替换为1)。

Answer 2

在Haskell中实现斐波纳契数列的所有方法只需遵循链接http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

Answer 3

这种实现效率很低，因为它进行了三次递归调用。如果我们将计算fibonacci n的递归关系写成范式(注意，书呆子读者:不是whnf)，它将如下所示：

T(1) = c
T(2) = c'
T(n) = T(n-1) + T(n-1) + T(n-2) + c''

(这里的c、c'和c''是一些我们不知道的常量。)下面是一个更小的递归：

S(1) = min(c, c')
S(n) = 2 * S(n-1)

这个递归有一个很好的简单的封闭形式，也就是S(n) = min(c, c') * 2^(n-1)：它是指数的！坏消息。

我喜欢您的实现的总体思想(即，同时跟踪序列的倒数第二项和最后一项)，但是由于多次递归调用fibonacci而失败了，而这是完全不必要的。下面是一个修复这个错误的版本：

fibonacci 1 = [1]
fibonacci 2 = [1,1]
fibonacci n = case fibonacci (n-1) of
    all@(last:secondLast:_) -> (last + secondLast) : all

这个版本应该要快得多。作为一种优化，它以相反的顺序生成列表，但这里最重要的优化是只进行一次递归调用，而不是有效地构建列表。