# Haskell Language Getting started with Haskell Language Fibonacci, Using Lazy Evaluation

## Example

Lazy evaluation means Haskell will evaluate only list items whose values are needed.

The basic recursive definition is:

``````f (0)  <-  0
f (1)  <-  1
f (n)  <-  f (n-1) + f (n-2)
``````

If evaluated directly, it will be very slow. But, imagine we have a list that records all the results,

``````fibs !! n  <-  f (n)
``````

Then

``````                  ┌──────┐   ┌──────┐   ┌──────┐
│ f(0) │   │ f(1) │   │ f(2) │
fibs  ->  0 : 1 : │  +   │ : │  +   │ : │  +   │ :  .....
│ f(1) │   │ f(2) │   │ f(3) │
└──────┘   └──────┘   └──────┘

┌────────────────────────────────────────┐
│ f(0)   :   f(1)   :   f(2)   :  .....  │
└────────────────────────────────────────┘
->  0 : 1 :               +
┌────────────────────────────────────────┐
│ f(1)   :   f(2)   :   f(3)   :  .....  │
└────────────────────────────────────────┘
``````

This is coded as:

``````fibn n = fibs !! n
where
fibs = 0 : 1 : map f [2..]
f n = fibs !! (n-1) + fibs !! (n-2)
``````

Or even as

``````GHCi> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
GHCi> take 10 fibs
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
``````

`zipWith` makes a list by applying a given binary function to corresponding elements of the two lists given to it, so `zipWith (+) [x1, x2, ...] [y1, y2, ...]` is equal to `[x1 + y1, x2 + y2, ...]`.

Another way of writing `fibs` is with the `scanl` function:

``````GHCi> let fibs = 0 : scanl (+) 1 fibs
GHCi> take 10 fibs
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
``````

`scanl` builds the list of partial results that `foldl` would produce, working from left to right along the input list. That is, `scanl f z0 [x1, x2, ...]` is equal to `[z0, z1, z2, ...] where z1 = f z0 x1; z2 = f z1 x2; ...`.

Thanks to lazy evaluation, both functions define infinite lists without computing them out entirely. That is, we can write a `fib` function, retrieving the nth element of the unbounded Fibonacci sequence:

``````GHCi> let fib n = fibs !! n  -- (!!) being the list subscript operator
-- or in point-free style:
GHCi> let fib = (fibs !!)
GHCi> fib 9
34
`````` PDF - Download Haskell Language for free