Haskell效率低下的斐波纳契实现

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的答案和Sec Oe的答案包含了一个链接,可能是学习如何在Haskell中正确编写斐波那契序列的最佳位置,但是这里有一些原因导致你的代码效率低下(注意,你的代码与经典的天真定义没有什么不同.优雅？当然.高效？善良,没有):

让我们考虑一下你打电话时会发生什么

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中的列表不支持常量时间随机访问 - 它们不是动态的数组,它们是链表).

递归定义的一个例子(来自提到的链接)确实记录了计算:

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

这里fibs实际上是一个列表,我们可以利用Haskell的惰性求值来生成fibs并tail fibs根据需要进行生成,而之前的计算仍然存储在fibs中.要获得前五个数字,它就像下面这样简单:

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

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

Answer 2

在Haskell中实现斐波那契序列的所有方法都只需要点击链接 http://www.haskell.org/haskellwiki/The_Fibonacci_sequence