Working with laziness and recursion

So far, we have seen a simple recursion; recursion using worker pattern. Haskell adds laziness to the mix. We can use laziness to our advantage while working with recursion. 

In this recipe, we will again calculate the fibonacci number. However, this time, we will do it with infinite lists. By taking advantage of Haskell's laziness to evaluate an expression only when it is required, we can really create a linear time algorithm (O(n)) for the fibonacci number.

Getting ready

Create a new project, fibonacci-infinite, by running Stack. Change into the project directory and build it using Stack:

      stack new fibonacci-infinite simple
      stack build

How to do it...

1. Open src/Main.hs in an editor. After the module definition, we will add the definition for our fibonacci number.
2. Add the function declaration for fib. Let's assume that we have an infinite list of fibonacci numbers, fiblist. Finding the n^th fibonacci number in the list is easy using the List index...