这是一个不同且更简单的函数，用于计算第n个斐波那契数：
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
你所提到的实现依赖于Fibonacci数列中的值如何相互关联，以及Haskell如何使用它们来定义数据结构，从而创建无限的数据结构。
你的问题中的函数工作方式如下：
假设你已经有了一个无限的Fibonacci数列表：
[ 1, 1, 2, 3, 5, 8, 13, .... ]
这个列表的尾部是：
[ 1, 2, 3, 5, 8, 13, 21, .... ]
zipWith使用给定的运算符逐个将两个列表中的元素组合：
[ 1, 1, 2, 3, 5, 8, 13, .... ]
+ [ 1, 2, 3, 5, 8, 13, 21, .... ]
= [ 2, 3, 5, 8, 13, 21, 34, .... ]
因此，无限斐波那契数列可以通过在无限斐波那契数列和其尾部的无限斐波那契数列使用+运算符进行压缩的结果前加入元素1和1来计算。
现在，要获取第n个斐波那契数，只需获取无限斐波那契数列的第n个元素：
fib n = fibs !! n
Haskell的优美之处在于，它不会计算出斐波那契数列中的任何元素，直到需要用到它们为止。
我让你脑袋爆炸了吗？ :)
0: 1: zipWith (+) fibs (tail fibs)生成一个无限列表。你从[0，1 ...]开始，并将zipWith (+) fibs (tail fibs)附加到其末尾。fibs的第一个元素是0，tail fibs的第一个元素是10，所以下一个元素是0 + 1 = 1，从而给出[0，1，1 ...]，现在您可以获得zipWith ...的第二个元素，即1 + 1 = 2，这样您就得到了[0，1，1，2 ...]等等。 - semicolon根据定义，斐波那契数列的每一项都是前两项的和。将这个定义转化为惰性 Haskell 代码，得到以下结果！
fibo a b = a:fibo b (a+b)
现在只需要从以0和1开头的斐波那契数列中选取n个项目即可。
take 10 (fibo 0 1)
map fst $ ((\(a,b)->(b,a+b)) iterate (0,1))。这段代码使用了一个无限列表的迭代器，每次迭代都会生成下一个斐波那契数对，并且通过map fst只保留数对中的第一个元素，从而得到斐波那契数列。这是一种非常简洁和优雅的实现方式。 - Will Nessfibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)，请参见 https://wiki.haskell.org/The_Fibonacci_sequence#With_iterate - Wolffibs = 0：1：zipWith（+）fibs（tail fibs） 相比，它的计算复杂度是多少？ - Wolf在dtb的回答上进行补充：
“简单”解决方案和更好的解决方案之间存在重要区别：
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
而你指定的那一个：
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
简单的解决方案需要 O(1.618NN) 的时间来计算第N个元素，而你指定的方法需要 O(N2) 的时间。这是因为你指定的方法考虑了计算 fib n 和 fib (n-1)（用于计算它）共享 fib (n-2) 的依赖关系，并且可以同时计算以节省时间。O(N2) 是对 O(N) 位数的数字进行 N 次加法运算。
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
首先，使用fibs和tail fibs，我们可以获得第3个元素：
fibs : [1, 1, ?
tail fibs : [1, ?
zipWith (+) fibs (tail fibs): [2, ?
现在我们知道第三个是2，我们可以得到第四个：
fibs : [1, 1, 2, ?
tail fibs : [1, 2, ?
zipWith (+) fibs (tail fibs): [2, 3, ?
现在是第五个版本：
fibs : [1, 1, 2, 3, ?
tail fibs : [1, 2, 3, ?
zipWith (+) fibs (tail fibs): [2, 3, 5, ?
and so on ..
fibonacci(n)的定义如下：
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
Haskell中的朴素实现：
fibonacci :: Integer -> Integer
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci x = fibonacci (x-1) + fibonacci (x-2)
n = 0 => (0,0,1)
n = 1 => (1,1,1) - calculated from the previous triple
n = 2 => (2,1,2) - calculated from the previous triple
n = 3 => (3,2,3) - calculated from the previous triple
n = 4 => (4,3,5) - calculated from the previous triple
n = 5 => (5,5,8) - calculated from the previous triple
nextTripleIfCurrentNIsLessThanN :: (Int, Integer, Integer) -> Int -> (Int, Integer, Integer)
nextTripleIfCurrentNIsLessThanN (currentN, x, y) n = if currentN < n
then nextTripleIfCurrentNIsLessThanN (currentN + 1, y, x + y) n
else (currentN, x, y)
thirdElementOfTriple :: (x,y,z) -> z
thirdElementOfTriple (x,y,z) = z
fibonacci :: Int -> Integer
fibonacci n = thirdElementOfTriple (nextTripleIfCurrentNIsLessThanN (0,0,1) n)
这将在O(n)的时间复杂度内运行 [虽然在处理大量数据时会稍微有些二次方，因为加大数字比加小数字更耗费资源。但这是一个关于计算模型的单独讨论话题。]
fibonacci 0
1
fibonacci 1
1
fibonacci 2
2
fibonacci 3
3
fibonacci 4
5
fibonacci 5
8
fibonacci 5000
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626
fibonaci = map fst (iterate f (0,1)) where f (x,y) = (y,x+y)
使用
take 10 fibonaci
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
通过使用 unfoldr，可以轻松地生成无限斐波那契数列；
fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)
哈哈，我喜欢 Haskell 的模式匹配，但在标准 Fibonacci 函数中它变得无用了。标准列表是从右侧构建的。要使用模式匹配和 cons，必须从左侧构建列表。好吧，至少有一个安慰，这真的很快。 ~O(n)，应该是的。需要一个辅助函数来反转无限列表（只有在 Haskell 中才能做到，太棒了），并且该函数输出每个运行的后续列表，因此在辅助函数管道中也使用了 'last'。
f (x:y:xs) = (x+y):(x:(y:xs))
辅助程序
fib n = reverse . last . take n $ iterate f [1,0]
这是一个列表版本，我认为它解释了列表的构造方式，这也是目的所在。我想做一个元组版本。
编辑于2018年3月15日
首先，Will Ness让我明白了每次迭代生成整个列表是不必要的，只需要使用最后两个值，并且结果列表的值是生成的每个列表或对的第一个值。这太有趣了。当Will告诉我列表的值是列表的第一个值时，我运行它并看到0,1,1,2,3,5,8,13作为每个列表的头部时，我说WTF，Will在我的电脑上更改了我的代码吗？这些值一直在那里，但我没有看到它们。唉。
Will的函数和辅助函数版本如下：
f = (\(x:y:xs) -> (x+y):x:xs) -- notice, no y: put back only x+y & x
以及他的辅助函数重写
fib n = map head . take n $iterate f [0,1]
我认为现在它们可以结合起来：
fib n = take n . map head $ iterate (\(x:y:xs) -> (x+y):x:xs) [0,1]
顺便提一下，这个函数也可以使用元组。
fib n = take n . map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)
fib n = take n [ fst t | t <- iterate (\(a,b) -> (b,a+b)) (0,1)]
这些都是迭代且健壮的。列表中最快的是使用map函数，对于斐波那契数列5000项的计算只需12.23秒。元组推导式是第二快的，对于斐波那契数列5000项的计算只需13.58秒。
last . take n就是(!! (n-1))。对于你的fib，fib n并不能像我们想要的那样帮助找到fib (n+1)。只需定义fibs = map head $ iterate f [1,0]，然后fib n = fibs !! n。现在我们发现它在每一步都创建了一个完整的列表，但只使用其中的2个头元素，因此我们将其更改为fibs = map fst $ iterate g (1,0)，并相应地将f更改为g。大功告成。 - Will NessmapM_ print $ take 15 $ iterate f [1,0]。现在将 f 更改为 f (x:y:xs) = (x+y):(x:xs)，然后再次运行 mapM_ ... 行并比较输出结果。 - Will Nessy g = g(y g)可行。Data.Function 定义了 fix f = x where { x = f x }，这与之非常相似，但又有着天壤之别。 - Will Ness我尝试在Python3中重新实现这个算法。目标是获得一个类似的Python算法，显然与Haskell相同，但不是模仿Haskell的所有方面。
我想出了以下代码。
fibs.py:
# python version of Haskell's code
# fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
from operator import add
fibsList = [1, 1] # growing
def fibs(n):
if n >= len(fibsList): # lazy evaluation
x=zipWith(n-2,add,fibs,tail(fibs)) # or: ...,fibs,tailfibs)
fibsList.append(x)
return fibsList[n]
def zipWith(n,op,list1,list2):
return op(list1(n),list2(n))
def tail(list): # or: def tailfibs(n):
return lambda n : list(n + 1) # return fibs(n+1)
# test
print (fibs(10))
print (*fibsList)
运行它将输出
$ python fibs.py
89
1 1 2 3 5 8 13 21 34 55 89
这将与Haskell代码执行相同的操作，但它是一步一步的版本，您可以添加一些日志记录
fibSerie a b = a : (fibSerie b (a+b))然后：fibs = fibSerie 1 1。 - jpmarinierω = 2 + min ω (ω - 1)。zipWith在这里生成一个（无限）整数列表，不仅仅是一个整数，因此它不是2 + 1总共的元素，而是2 + ω。其中ω是序数。 - Will Ness