生成斐波那契数在Haskell？生成斐波那契数在Haskell？(Generating Fibona

在Haskell，如何可以生成基于属性斐波那契数第n个斐波那契数等于第（n-2）个第Fibonacci数Fibonacci数加上第（n-1）？

我已经看到了这一点：

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

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

我怎么会写Haskell代码，通过计算实际定义，而不是做一些与列表功能很奇怪的作品？

Answer 1:

下面是计算第n个Fibonacci数不同和简单的功能：

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

你是指继电器关于在斐波那契如何价值观的一些意见实施的相互关系（和Haskell如何有效定义数据结构themselfs方面创造无限的数据结构）

在你的问题的功能是这样的：

假设你已经有斐波那契数的无限名单：

   [ 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个Fibonacci数，只得到Fibonacci数的无限列表的第n个元素：

fib n = fibs !! n

哈斯克尔的美妙之处在于它不计算斐波那契数的列表中的任何元素，直到它的需要。

难道我让你的脑袋爆炸？ :)

Answer 2:

通过定义去，斐波那契数列的每一项是前两项的总和。 把这个定义懒惰哈斯克尔插上U这个！

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

现在只取n项从FIBO开始0,1

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 ^2）。 这是因为你指定的一个考虑到的是，计算帐户fib n和fib (n-1)其需要计算它）共用的依赖fib (n-2)并且它可以被计算一次，既节省时间。 O（N ^2）是用于的O（N）位的号码N个加法。

Answer 4:

有许多不同的哈斯克尔算法斐波纳契数列在这里 。 该“天真”的实现看起来你是什么之后。

Answer 5:

产生无限斐波纳契数列的懒惰方式可以很容易地通过以下方式实现unfoldr如下;

fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)

Answer 6:

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容纳所有的fibonaccis到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

Answer 7:

大声笑，我喜欢哈斯克尔模式匹配，但它是在标准的斐波纳契功能形同虚设。 标准列表从右边构成。 要使用模式匹配和利弊，列表必须从左边来构建。 那么，一个安慰，至少，这是真的很快。 〜O（n）时，它应该是。 需要一个辅助函数来扭转无限列表（的东西，你只能在Haskell，快乐做），这功能输出使“最后”的辅助函数管道也被用来运行的每个后续名单。

f (x:y:xs) = (x+y):(x:(y:xs))

助手

fib n = reverse . last . take n $ iterate f [1,0]

这是一个列表版本，我认为，它explicates名单是如何构建它的宗旨。 我想做一个元组版本。

编辑2018年3月15日

首先，威尔内斯开导我的知识，在每次迭代产生一个完整的列表是不必要的，并需要只用了最后两个值，并且在结果列表中的值生成每个列表或对的第一个值。 它是如此有趣。 后，将告诉我的值入榜名单的第一个值，我跑，看见那值0,1,1,2,3,5,8,13每个列表中的每个头，我说跆拳道，并会改变我的电脑上我的代码？ 这些值在那里，但如何！？ 过了一会儿，我意识到他们在那里一直，但我只是没有看到他们。 啊。 威尔版的功能和辅助功能有：

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)]

这些都是迭代和强大。 最快的是在12.23秒的FIB 5000与列表中的地图元组的理解是第二快的FIB 5000为135.8秒。

Answer 8:

使用iterator

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]

文章来源: Generating Fibonacci numbers in Haskell?