Haskell Cookbook

How it works...

We have revisited fibonacci numbers in this recipe. Here, we used the State Monad to store the intermediate results while calculating the fibonacci number. We defined a map between the fibonacci index and its number as a state. Two functions getFib and putFib are defined. The getFib function uses State Monad function GET to get the map and checks if the result was previously cached. If the result was not cached before, then it proceeds by calculating the n-1^th and n-2^th fibonacci numbers and caching all intermediate results. In fact, since the n-1^th number calculation will involve the n-2^th number as well, the calculation will be quickly done (O(n) complexity). 

We used the function execState to run our fibonacci number calculation ...