The preceding implementation looks deceptively simple, and it works! This is one of the highlights of Haskell. It provides a very elegant language construct to write such compact and meaningful programs in.
The heart of fiblist is the use of the zipWith function. The zipWith has the following signature:
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
The zipWith function takes a function f and two lists. The zipWith function takes out an element from each list and applies the funcion f on these two elements. The zipWith function recursively continues this operation until either of the input lists are exhausted. In fact, zipWith is implemented in Prelude as follows:
zipWith f [] _ = [] -- Either input is empty, the result is empty
zipWith f _ [] = [] --
zipWith f (x:xs) (y:ys) = f x y : zipWith xs ys
Let's see how fiblist is able to represent an infinite number of fibonacci numbers. fiblist is defined as follows:
fiblist = 0 : 1 : zipWith (+) fiblist (tail fiblist)
The first two elements are the initial fibonacci numbers, 0, and 1, respectively. The rest of the elements are evaluated only when asked for. Otherwise, it remains as an unevaluated expression. For example, if we need to evaluate fiblist until five fibonacci numbers, it will be done as follows. The inputs to zipList is fiblist itself and the tail of fiblist (all but the first element). Since the first two elements are already there, we can use them. Hence, they are the only numbers highlighted in the initial fiblist expression. Hence, using Haskell's laziness carefully and cleverly, we can write an elegant routine to calculate fibonacci numbers:
fiblist = 0 : 1 : zipWith (+) [0,1...] [1,...]
-- Use first two elements of the list passed to zipWith and add
them
= 0 : 1 : (0 + 1) : zipWith (+) [1,1...] [1,..]
-- zipWith now recurses to process remaining elements of fiblist
-- and tail of fiblist.
= 0 : 1 : 1 : (1 + 1) : zipWith (+) [1,2..] [2..]
-- Thus zipWith keeps on supplying elements to fiblist, and it
itself uses -- this list to evaluate further.
= 0 : 1 : 1 : 2 : (1 + 2) : zipWith (+) [2,3...] [3..]
= 0 : 1 : 1 : 2 : 3 : (2 + 3) : zipWith (+) [3, 5...] [5...]
= 0 : 1 : 1 : 2 : 3 : 5 : zipWith (+) [3, 5...] [5..]
Note how zipWith uses initial values to evaluate and feed fibonacci numbers to itself.
The evaluation of lazy list can be shown graphically here:
