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

_______________________________________________

Beginners mailing list

Beginners@haskell.org

http://www.haskell.org/mailman/listinfo/beginners