fibonacci and concurrent recursion
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. I have been tracing the steps manually like this 0:1 [0,1] [1] 0:1:1 [0,1,1] [1,1] 0:1:1:2 [0,1,1,2] [1,1,2] 0:1:1:2:3 [0,1,1,2,3] [1,1,2,3] 0:1:1:2:3:5 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? I guess a more general way of asking my question is how does concurrent recursion on the same result-set work? -- Christoffer Buchholz
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
On 2012-12-03T10:31-0500, Brent Yorgey wrote:
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.
I think this is a good example of using ghc-vis, so I just added it to my examples, in case anyone wants to see the graph version: http://felsin9.de/nnis/ghc-vis/#fibonacci Dennis
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
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@haskell.org (mailto:Beginners@haskell.org) http://www.haskell.org/mailman/listinfo/beginners
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-defin... -- 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@haskell.org (mailto:Beginners@haskell.org) http://www.haskell.org/mailman/listinfo/beginners
participants (3)
-
Brent Yorgey -
Christoffer Buchholz -
Dennis Felsing