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

On Thu, Oct 7, 2010 at 8:44 AM, Luke Palmer wrote:

On Thu, Oct 7, 2010 at 6:17 AM, Brent Yorgey 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.