7

The following function computes the Fibonacci sequence:

fib = 0 : 1 : (zipWith (+) fib (tail fib))

If we run it, we will get an infinite list, but how does the recursion work? Why does it get to print numbers on the screen if it the function keeps calling itself? I would appreciate if you could explain how the compiler manages the calls.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Razvan Meriniuc
  • 182
  • 12

2 Answers2

11

I've drawn a picture, which you might find helpful.
Note that zipWtih op (x:xs) (y:xs) = (op x y):zipWith xs ys, which is how zipWtih appears to "move" right along the list. It's reading elements and spitting out sums:

pic with coloured pointers

Here's a more detailed step-by-step evaluation. (Although I'll paste copies of what's there, there's only one copy in memory.) I'll use .... for things I can't be bothered to write out.

fib = 0:1:zipWith (+) fib (tail fib)
    = 0:1:zipWith (+) (0:1: .... ) (tail (0:1: .... )
    = 0:1:(0+1:zipWith (+) (1:(0+1: .... )) ( 0+1:..... ))
    = 0:1:1:zipWith (+) (1: ....) (......)

notice that now we know that zipWith (+) fib (tail fib) = 1:......

    = 0:1:1:zipWith (+) (1:1: ....) (1:......)
    = 0:1:1:(1+1):zipWith (+) (1:(1+1): .....) ((1+1):....)
    = 0:1:1:2:zipWith (+) (1:2: .....) (2:....)

I'll go a little faster:

    = 0:1:1:2:(1+2):zipWith (+) (2: .....) (....)
    = 0:1:1:2:3     :zipWith (+) (2:3 .....) (3:....)
    = 0:1:1:2:3:(2+3):zipWith (+) (3:(2+3):.....) ((2+3):.....)
    = 0:1:1:2:3:5     :zipWith (+) (3:5:.....) (5:.....)
    = 0:1:1:2:3:5:8    :zipWith (+) (5:8:....) (8:......)
    = 0:1:1:2:3:5:8:13  :zipWith (+) (8:13:....) (13:......)
    = 0:1:1:2:3:5:8:13:21:zipWith (+) (13:21....) (21:......)

At each stage, the last two arguments to the zipWith function are like pointers to (one and two positions) further up the fib list than we are at present.

AndrewC
  • 32,300
  • 7
  • 79
  • 115
3

In a word: laziness. A list in Haskell is more like a generator: it will only compute values when they are demanded by something else.

For instance head [1 , 2+3] will not perform the addition, since it is not needed. Similarly, if we recursively let ones = 1 : ones, then head ones = head (1 : ones) = 1 does not need to evaluate all the tail.

You can try guessing what happens if we print a pair x, defined as follows:

x = (n, fst x + 1)

Above we use a (lazy) pair instead of a (lazy) list, but the reasoning is the same. Don't evaluate anything unless is it needed by something else.

chi
  • 111,837
  • 3
  • 133
  • 218
  • Could you please explain how the function I have provided works for the first few calls? When does it decide to stop calling itself and compute the result? What happens to `zipWith (+) fib (tail fib)` at the last call? The function simply returns 0:1:[]? – Razvan Meriniuc May 15 '16 at 20:28
  • 3
    @RazvanMeriniuc There is no “last call”, nor does it ever “stop calling itself”. The point is that Haskell is *lazy*, so computations won’t be evaluated until they are needed. If you take the first 4 numbers from `fib`, then Haskell will evaluate the expression until it has computed 4 elements, then it will suspend evaluation. If you then take the first 8 numbers, it will *resume* the computation to get the next four, then re-suspend until things are needed. There is no “end” to this process. If you try to take all the numbers (by folding, for example), it will never finish. – Alexis King May 15 '16 at 23:38