Functional Programming►Haskell

Fibonacci sequence in Haskell

首先，利用iterate生成Fibonacci的pair序列，

1
fibpairlst = iterate (\(x1,x2)->(x1+x2,x1+2*x2)) (1,1)

运行结果如下，

1
2
3
*Main> let fibpairlst = iterate (\(x1,x2)->(x1+x2,x1+2*x2)) (1,1)
*Main> take 10 fibpairlst
[(1,1),(2,3),(5,8),(13,21),(34,55),(89,144),(233,377),(610,987),(1597,2584),(4181,6765)]

然后，再用foldr将pair序列展平（flat）即可得到一个斐波那契数列（Fibonacci Sequence）：

1
foldr (\(x1,x2) xs->x1:x2:xs) [] fibpairlst

综上所述，

1
2
fiblst = let fibpairlst = iterate (\(x1,x2)->(x1+x2,x1+2*x2)) (1,1)
         in foldr (\(x1,x2) xs->x1:x2:xs) [] fibpairlst

生成的序列是一个无穷序列，可以用take函数来选出前n个，也可以直接用!!运算符来选出特定的某个。

1
2
3
4
5
6
7
8
9
10
*Main> take 20 fiblst
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]
*Main> fiblst !! 20
10946
*Main> fiblst !! 5
8
*Main> fiblst !! 3
3
*Main> fiblst !! 1
1

我想这可能是最快的递推生成的斐波那契数列的方法了吧，由于Haskell的惰性求值机制，当用到某个值时直接递推计算，没有产生任何中间冗余的结果，也没有重复运算。