[Haskell-cafe] Eta-expansion destroys memoization?

[Luke Palmer]

On Thu, Oct 7, 2010 at 6:17 AM, Brent Yorgey <byorgey at seas.upenn.edu> wrote:
> The source code seems to be easy to read, but I don't think I understand that. For me I think if I change the first line from
> fib = ((map fib' [0 ..]) !!)
> to
> fib x = ((map fib' [0 ..]) !!) x
> It should do the same thing since I think the previous version is just an abbreviation  for the second one.

Semantically, yes.  And it's possible that ghc -O is clever enough to
notice that.  But at least under ghci's naive evaluation strategy,
lambdas determine the lifetime of expressions. Any expression within a
lambda will be re-evaluated each time the lambda is expanded.  Thus:

  fib = (map fib' [0..] !!)        -- fast
  fib = \x -> map fib' [0..] !! x        -- slow
  fib = let memo = map fib' [0..] in \x -> memo !! x -- fast

The section works because "(a %^&)"  (for some operator %^&) is short
for "(%^&) a" and "(%^& a)" is short for "flip (%^&) a".  Sections
don't expand into lambdas.

In other words, in the middle expression, there is a new "map fib'
[0..]" for each x, whereas in the others, it is shared between
invocations.

Does that make sense?

Luke