[Haskell-cafe] Eta-expansion destroys memoization?

[Derek Elkins]

On Thu, Oct 7, 2010 at 8:44 AM, Luke Palmer <lrpalmer at gmail.com> wrote:
> 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?

In general, f is not semantically equivalent to \x -> f x in Haskell.
However, that is not what Brent said.  The Report -defines- (m !!) as
\x -> m !! x.  GHC simply does not follow the Report here.  You can
witness this via: (() `undefined`) `seq` 0.  By the Report this should
evaluate to 0, in GHC it evaluates to undefined.

As for the rest... The operational behavior of the above is
implementation dependent, but GHC, and I imagine most implementations,
more or less do the natural thing.  The Report gives no way to control
sharing behavior, but being able to control it is rather important, so
predictable behavior here is desirable.