[Haskell-beginners] fibonacci and concurrent recursion

[Christoffer Buchholz]

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 at haskell.org (mailto:Beginners at haskell.org)
> http://www.haskell.org/mailman/listinfo/beginners
> 
> 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121203/37756aac/attachment-0001.htm>