[Haskell-beginners] fibonacci and concurrent recursion

[Brent Yorgey]

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
> > 
> > 
> 
>