Haskell: Problems with Lazy evaluation

One problem with lazy evaluation is, it creates many thunks while processing data, which leads to occupy more and more memory so that the operating system has to paginate, which makes the program slower.

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

I had written more about this in my previous post “How Lazy evaluation works in Haskell”.

Previous                                                 Next                                                 Home