在Haskell中，如何基于第n个Fibonacci数等于第（n-2）个Fibonacci数加上第（n-1）个Fibonacci数的属性生成Fibonacci数？
我见过这个：
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
我真的不明白，或者它是如何产生无限列表而不是包含3个元素的列表。
我如何通过计算实际定义来编写haskell代码，而不是通过使用list函数做一些非常奇怪的事情？
这是一个计算第n个Fibonacci数的不同且更简单的函数：
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, .... ]
这份清单的tail是
[ 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, .... ]
所以Fibonacci数的无限列表可以通过使用1算子将元素1和+前置到使用无限的斐波纳契数列表的尾部压缩无限列表的Fibonacci数来计算。
现在，要获得第n个Fibonacci数，只需获得Fibonacci数无限列表的第n个元素：
fib n = fibs !! n
Haskell的优点在于它不需要计算Fibonacci数列表中的任何元素。
我让你的头爆炸了吗？ :)
根据定义，斐波纳契数列的每个项目都是前两个项的总和。将此定义放入lazy haskell给你这个！
fibo a b = a:fibo b (a+b)
现在只需从0开始从fibo中取n个项目
take 10 (fibo 0 1)
扩展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）用于N个O（N）个数字的加法。
Fibonacci序列here有许多不同的Haskell算法。 “天真”的实现看起来就像你追求的那样。
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
首先，使用fibs和tail fibs，我们可以获得第3个元素：
fibs : [1, 1, ?
tail fibs : [1, ?
zipWith (+) fibs (tail fibs): [2, ?
现在，我们知道第3名是2，我们可以获得第4名：
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, ?
等等 ..
如下所示，unfoldr可以很容易地实现产生无限斐波纳契数列的懒惰方式;
fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)
斐波那契（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)
所有公式都可以追溯到这个定义，有些运行速度非常快，其中一些运行速度非常慢。上面的实现具有O（n）= 2 ^ n
根据你的问题的精神，让我删除列表的使用，并给你一些在O（n）I.e.运行的东西。让我们不要在列表中保留从0到n的所有斐波那契。
如果我们有一个三元组（一个有三个成员的元组），它们看起来像：
(n, fibonacci[n-1], fibonacci[n])
记住最初的定义，我们可以计算出最后一个三元组的下一个三元组：
(n+1, fibonacci[n], fibonacci[n-1] + fibonacci[n]) = (n+1, fibonacci[n], fibonacci[n+1])
而上一个三重奏的下一个三倍：(n+2, fibonacci[n+1], fibonacci[n] + fibonacci[n+1]) = (n+1, fibonacci[n+1], fibonacci[n+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
让我们在Haskell中实现它并使用自解释变量名：
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]
大声笑，我喜欢Haskell模式匹配，但它在标准Fibonacci函数中变得无用。标准清单由右侧构成。要使用模式匹配和缺点，必须从左侧构建列表。嗯，至少，一个安慰是，这真的很快。 ~O（n），它应该是。需要辅助函数来反转无限列表（你只能在Haskell中做的事情，欢乐），这个函数输出每个后续的运行列表，所以'last'也用在辅助函数管道中。
f (x:y:xs) = (x+y):(x:(y:xs))
帮助者
fib n = reverse . last . take n $ iterate f [1,0]
这是一个列表版本，我认为，它阐明了如何构建列表的目的。我想做一个元组版本。
编辑3/15/2018
首先，Will Ness启发了我的知识，即在每次迭代中生成的整个列表是不必要的，并且只需要使用的最后两个值，并且结果列表的值是生成的每个列表或对的第一个值。太有趣了。 Will告诉我列表的值是列表的第一个值，我运行它并看到每个列表的每个头的值为0,1,1,2,3,5,8,13，我说WTF，我的PC上的代码会改变吗？价值观在那里，但如何！？过了一会儿，我意识到他们一直都在那里，但我只是没有看到他们。啊。 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)]
这些都是迭代和稳健的。最快的是用于fib 5000的12.23秒列表的地图。对于fib 5000，在13.58秒时，元组理解度是第二快的。