Haskell: Fibonacci series

Fib.hs

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

Prelude> :load Fib.hs
[1 of 1] Compiling Main             ( Fib.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> fibonacci 0
0
*Main> fibonacci 1
1
*Main> fibonacci 2
1
*Main> fibonacci 3
2
*Main> fibonacci 4
3
*Main> fibonacci 5
5

One problem with above program, due to the lazy evaluation of Haskell, it will not evaluate expression unless needed, so these expressions kept in memory. This overhead affects the performance. Try to calculate Fibonacci series for numbers 20, 30, 40 you can observe it.

*Main> fibonacci 20
6765
*Main> fibonacci 30
832040
*Main> fibonacci 40
102334155

One way to solve above problem is by using bang patter (!). Update above program like below using bang pattern.

Fib.hs

{-# LANGUAGE BangPatterns #-}

fibonacci :: Integer -> Integer
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibhelper n 0 1

-- Everything with a ! before it will be evaluated before the function body
fibhelper :: (Integral a) => a -> a -> a -> a
fibhelper 1 _ (!y) = y
fibhelper (!n) (!x) (!y) = fibhelper (n-1) y (x+y)

*Main> fibonacci 20
6765
*Main> fibonacci 30
832040
*Main> fibonacci 40
102334155
*Main> fibonacci 100
354224848179261915075
*Main> fibonacci 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Previous                                                 Next                                                 Home