listhaskellrecursionfibonacciinfinite

Haskell infinite recursion


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.


Solution

  • I've drawn a picture, which you might find helpful.
    Note that zipWith op (x:xs) (y:xs) = (op x y):zipWith xs ys, which is how zipWith 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.