[Haskell-beginners] fibonacci and concurrent recursion

[Christoffer Buchholz]

This link that Zbigniev Stanasiuk sent me explains it very well. I think I understand it know. 

The link: http://stackoverflow.com/questions/6273621/understanding-a-recursively-defined-list-fibs-in-terms-of-zipwith 

-- 
Christoffer Buchholz


On Monday den 3. December 2012 at 21.38, Brent Yorgey wrote:

> On Mon, Dec 03, 2012 at 08:10:00PM +0100, Christoffer Buchholz wrote:
> > 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?
> > 
> 
> 
> Think about it hard. Read a lot. Play with some examples. Ask
> questions.
> 
> > 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`?
> > 
> 
> 
> No, in
> 
> f = 0 : f'@(1 : f''@(1 : zipWith (+) f' f''))
> 
> I mean that 
> 
> f' = 1 : 1 : zipWith (+) f' f''
> 
> and
> 
> f'' = 1 : zipWith (+) f' f''
> 
> Also, note that 'tail f' cannot be 1:1:2, since that does not even
> type check. It is 1:1:2:<some unevaluated expression>, where in
> particular the unevaluated expression involves zipWith and refers back
> to f' and f''.
> 
> -Brent
> 
> > 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/23e51b22/attachment.htm>