[Haskell-cafe] Eta-expansion destroys memoization?

[Jan-Willem Maessen]

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 <byorgey at seas.upenn.edu> wrote:

> ----- Forwarded message from Yue Wang <yulewang at gmail.com> -----
>
> From: Yue Wang <yulewang at 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