在Haskell中生成斐波那契数列？
在Haskell中，如何根据第n个斐波纳契数等于第（n-2）个斐波那契数加上第（n-1）个斐波那契数的性质来生成斐波纳契数？
我见过这个：
fibs :: [Integer] fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 我真的不明白，或者它如何产生一个无限的列表，而不是一个包含3个元素的列表。
我如何编写通过计算实际定义而工作的haskell代码，而不是使用list函数做一些非常奇怪的事情？
这是一个简单的函数，可以计算第n个斐波纳契数：
fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
你的问题的function是这样的：
假设你已经有了一个斐波那契数列的无限列表：
[ 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, .... ]
因此斐波那契数列的无限列表可以通过在元素1和1之前用+运算符将斐波纳契数字的无限列表的尾部与斐波纳契数字的无限列表的尾部进行压缩而得到。
现在，要得到第n个斐波那契数，只要得到斐波纳契数的无限列表的第n个元素：
fib n = fibs !! n
Haskell的美妙之处在于它不计算斐波纳契数列表中的任何元素直到需要。
我的头部爆炸了吗？ 🙂
扩展dtb的答案：
“简单”解决scheme之间有一个重要的区别：
fib 0 = 1 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
而你指定的那个：
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
简单的解决scheme需要O（1.618 N ）时间来计算第N个元素，而您指定的那个需要O（N 2 ）。 那是因为你指定的那个考虑到计算fib n和fib (n-1) （计算它所需要的）共享fib (n-2)的依赖性，并且它可以被计算一次以便保存时间。 O（N 2 ）用于N个数字的O（N）数字。
按照定义，斐波那契数列的每一项都是前两项的和。 把这个定义放在懒惰的哈斯克尔给你这个！
fibo ab = a:fibo b (a+b)
现在只需要从0,1开始的fibo中的n个项目
take 10 (fibo 0 1)
斐波那契数列有许多不同的Haskellalgorithm。 “天真”的实现看起来像你在做什么。
生成无穷斐波那契数列的一个懒惰的方法可以通过unfoldr方法很容易地实现：
fibs :: [Integer] fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)
fibonaci（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）运行的东西，我们不要把所有的斐波纳契从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中实现它，并使用自解释variables名称：
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）[n ^ 2在实践中工作，但这是关于计算模型的单独讨论]
fibonacci 0 1 fibonacci 1 1 fibonacci 2 2 fibonacci 3 3 fibonacci 4 5 fibonacci 5 8 fibonacci 5000
使用迭代
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]
