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
