All right, thanks for clearing up my misconceptions! I'm trying to understand, but I still don't think I do. Any idea how I can get to understand it? When I look at your "illustration" where you named the parts, it does seem more clear, but I don't get how e.g. at the third number `(tail f)` equals f'' equals 1? f'' clearly equals 1, but `(tail f)` would equal 1:1, wouldn't it? Same at the fourth number, f'' clearly equals 2, but `(tail f)` would equal 1:1:2, wouldn't it? Or am I misunderstand what `f`? -- Christoffer Buchholz On Monday den 3. December 2012 at 16.31, Brent Yorgey wrote:
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 (mailto:Beginners@haskell.org) http://www.haskell.org/mailman/listinfo/beginners