Re: [Haskell-cafe] Eta-expansion destroys memoization?

On Thu, Oct 7, 2010 at 9:33 AM, Jan-Willem Maessen 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 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 wrote:

...

----- Forwarded message from Yue Wang -----

From: Yue Wang 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