在haskell中生成fibonacci数?

下面是一个计算第n个斐波那契数的不同而简单的函数:

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

您所指的实现是对一些关于fibonacci中的值如何相互关联的观察(以及haskell如何根据自身定义数据结构,从而创建无限的数据结构)的中继。

问题中的函数如下所示:

假设您已经拥有无限的斐波那契数列表:

   [ 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 和 一 对于使用 + 操作员。

现在,要得到第n个斐波那契数,只需得到无限长斐波那契数列表的第n个元素:

fib n = fibs !! n

哈斯克尔的优点在于,在需要的时候,它不会计算斐波那契数列中的任何元素。

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

根据定义,斐波那契级数的每一项都是前两项的和。把这个定义放进懒惰的哈斯凯尔给了你这个!

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

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

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.618 ^N N) 计算第n个元素的时间,而您指定的元素取0(n ^二 )那是因为你指定的那个考虑到了计算 fib n 和 fib (n-1) (需要计算它)共享 fib (n-2) ,并且可以计算一次以节省时间。O(n) ^二 )表示O(N)位数的n个加法。

对于斐波那契序列,有许多不同的haskell算法 here . “幼稚的”实现看起来像您所追求的。

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中实现这个 并使用自述变量名:

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

此实现几乎立即计算100000个斐波那契数:

fib = fastFib 1 1

fastFib _ _ 0 = 0
fastFib _ _ 1 = 1
fastFib _ _ 2 = 1
fastFib a b 3 = a + b
fastFib a b c = fastFib (a + b) a (c - 1)

一种生成无限斐波那契级数的懒惰方法可以很容易地通过 unfoldr 如下;

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

lol,我喜欢haskell模式匹配,但在标准的fibonacci函数中,它是无用的。标准列表是从右边构建的。要使用模式匹配和cons,必须从左侧构建列表。好吧,至少有一个安慰是,这真的很快。~o(n),应该是。需要一个助手函数来反转无限列表(只能在haskell、joy中执行),该函数输出运行的每个后续列表,因此“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让我明白,在每次迭代中生成一个完整的列表是不必要的,只需要最后两个使用的值,结果列表的值是生成的每个列表或对的第一个值。真有趣。在威尔告诉我列表的值是列表的第一个值之后,我运行它并看到值0,1,1,2,3,5,8,13,作为每个列表的每个头,我说wtf,是否会在我的电脑上更改我的代码?价值观就在那里,但如何!过了一会儿,我意识到他们一直在那儿,但我只是没看见他们。呃。 will函数和helper函数的版本是:

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的tuple理解速度第二快,为13.58秒。

使用迭代

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]