在Haskell中生成Fibonacci数？

Question

在Haskell中,如何基于第n个Fibonacci数等于第(n-2)个Fibonacci数加上第(n-1)个Fibonacci数的属性生成Fibonacci数？

我见过这个:

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

我真的不明白,或者它是如何产生无限列表而不是包含3个元素的列表.

我如何通过计算实际定义来编写haskell代码,而不是通过使用list函数做一些非常奇怪的事情？

Answer 1

这是一个计算第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, .... ]

因此,斐波那契数的无限列表可以通过在元素之前预先计算,1并1使用+运算符将无限的Fibonacci数列表与无限的Fibonacci数列表的尾部压缩.

现在,要获得第n个Fibonacci数,只需获得Fibonacci数无限列表的第n个元素:

fib n = fibs !! n

Haskell的优点在于它不需要计算Fibonacci数列表中的任何元素.

我让你的头爆炸了吗？:)

Answer 2

根据定义,斐波纳契数列的每个项目都是前两个项的总和.将此定义放入lazy haskell给你这个!

fibo a b = a:fibo b (a+b)

现在只需从0开始从fibo中取n个项目

take 10 (fibo 0 1)

Answer 3

扩展dtb的答案:

"简单"解决方案之间存在重要区别:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

你指定的那个:

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

简单的解决方案需要O(1.618 ^N N)时间来计算第N个元素,而您指定的那个需要O(N ²).这是因为您指定的那个考虑到计算fib n和fib (n-1)(计算它需要)共享依赖性fib (n-2),并且可以计算一次以节省时间.O(N ²)用于N个O(N)个数字的加法.

Answer 4

有许多不同的哈斯克尔算法斐波纳契数列在这里."天真"的实现看起来就像你追求的那样.

Answer 5

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

首先，使用fibsand tail fibs，我们可以得到第三个元素：

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, ?

现在是第 5 个：

fibs                        : [1, 1, 2, 3, ?
tail fibs                   : [1, 2, 3, ?
zipWith (+) fibs (tail fibs): [2, 3, 5, ?

等等 ..