On Thu, Oct 7, 2010 at 9:33 AM, Jan-Willem Maessen <jmaes...@alum.mit.edu> wrote: > There's no evaluation magic here---all that's happening is GHC is > executing the program exactly as written. It can't float the list out > of the function, as that can lead to unexpected space leaks (if you > didn't intend to keep the list of fibs around forever).
To echo Jan-Willem a bit, the impact of let floating can be seen by compiling the eta expanded version (i.e. fib x = map fib' [0..] !! x) with different options. $ ghc --make -O -fforce-recomp FibMemo.hs [1 of 1] Compiling Main ( FibMemo.hs, FibMemo.o ) Linking FibMemo ... $ ./FibMemo 5 3 2 4 5 $ ghc --make -O -fforce-recomp FibMemo.hs -fno-full-laziness [1 of 1] Compiling Main ( FibMemo.hs, FibMemo.o ) Linking FibMemo ... $ ./FibMemo 5 3 2 4 2 3 2 5 My understanding is that this is just a case where GHCi is able to float a binding in the partial application formulation because the dependency analysis is trivial due to there being no name for the binding. Looking at the core for the optimized version of the eta expanded code, there is a a top-level function for building a list of fibonacci numbers, a top-level value of type [Type.Integer] set to an application of the builder function to zero, and finally the fib function that indexes into that list. The version with -fno-full-laziness leaves the let binding under the lambda as expected. So the optimizer is clever and can see through the lambda, but we make the interpreter's job easier by not putting a lambda over its eyes to begin with. Anthony On Thu, Oct 7, 2010 at 9:33 AM, Jan-Willem Maessen <jmaes...@alum.mit.edu> wrote: > What people seem to be missing here is that the location of the > where-binding with respect to the lambda changes in each case. As a > result, I think the forgoing explanations were rather confusing; > there's no magic going on here. > > On Thu, Oct 7, 2010 at 8:17 AM, Brent Yorgey <byor...@seas.upenn.edu> wrote: > >> ----- Forwarded message from Yue Wang <yulew...@gmail.com> ----- >> >> From: Yue Wang <yulew...@gmail.com> >> Then there is a clever way to do that on haskell wiki: >> >> fib = ((map fib' [0 ..]) !!) >> where >> fib' 0 = 0 >> fib' 1 = 1 >> fib' n =trace(show(n)) fib (n - 1) + fib (n - 2) > > This is indeed equivalent to: > fib = > let fib' 0 = 0 > fib' 1 = 1 > fib' n = fib (n-1) + fib (n-2) > in (map fib' [0..] !!) > > But adding the argument embeds the let inside the function call: > fib x = > let fib' 0 = 0 > fib' 1 = 1 > fib' n = fib (n-1) + fib (n-2) > in (map fib' [0..] !!) > > Now we create a new fib' for each invocation of fib. Not efficient at > all! (Much *less* efficient the the recursive fib). > > There's no evaluation magic here---all that's happening is GHC is > executing the program exactly as written. It can't float the list out > of the function, as that can lead to unexpected space leaks (if you > didn't intend to keep the list of fibs around forever). > > -Jan-Willem Maessen > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe