[Haskell-beginners] fibonacci and concurrent recursion

[Brent Yorgey]

Hi Chris,

On Mon, Dec 03, 2012 at 04:05:28PM +0100, Christoffer Buchholz wrote:
> Hi 
> 
> I have been looking at this fibonacci implementation:
> 
> f = 0:1:(zipWith (+) f (tail f))
> 
> and I have been trying to fit it inside my head. I am not quite there yet, though.
> 
> And it is easy to see that it works, but what I do not understand is how the two recursive applications progress. How do they evolve concurrently? For each execution of `f`, `f` will be executed twice. So how does all these results end up in the same list?

f is not 'executed'.  And it certainly is not executed twice for each
execution, or anything like that.

f is simply a *name* for an *expression*.  All three occurrences of f
in the code above refer to the *same* expression.  They do not "evolve
concurrently", they simply *are* the same thing.  Operationally, they
are all represented by pointers to the exact same list structure in
memory.  Note also that simply referring to an expression does not
'do' anything; when I said 'Hi Chris' above, it did not cause you to
be 'executed'.  I simply referred to you, and you went on being the
same person you were all along.

The thing to think about is not execution but the *process of
evaluation*.  Unlike people, Haskell expressions can be partially
evaluated, and the process of evaluation happens on demand.
Unfortunately it is very difficult to show the process of evaluation
in an email because for this expression it really requires thinking
about the expression as a *graph*, and those are hard to draw in an
email.

At first f looks like this:

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

Now, if we demand to know the next element of the list, we need to
evaluate the call to zipWith.  zipWith, in turn, demands to know the
first elements of its arguments.  Well, we can see that the first
element of f is 0, and the first element of (tail f) is 1.  So the
next element of the list is (0+1) = 1.  At this point f looks like
this:

  f = 0 : f'@(1 : f''@(1 : zipWith (+) f' f''))

Here's where a picture would be really helpful.  Instead of drawing a
graph I have given certain parts of the expression names.  You can see
that the arguments to zipWith are really just pointers back to
subexpressions of f itself.  Continuing, the next step would look like
this:

  f = 0 : 1 : f'@(1 : f''@(2 : zipWith (+) f' f''))

And so on.

I hope that was at least somewhat helpful, though I suspect you will
probably still be confused.  That's OK though; embrace the confusion
and keep asking questions. =)

-Brent