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

[Simon Marlow]

On 07/10/2010 14:03, Derek Elkins wrote:
> 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.

Interesting.  You're absolutely right, GHC doesn't respect the report, 
on something as basic as sections!  The translation we use is

   (e op)  ==>  (op) e

once upon a time, when the translation in the report was originally 
written (before seq was added) this would have been exactly identical to 
\x -> e op x, so the definition in the report was probably used for 
consistency with left sections.

We could make GHC respect the report, but we'd have to use

   (e op)  ==>  let z = e in \x -> z op x

to retain sharing without relying on full laziness.

This might be a good idea in fact - all other things being equal, having 
lambdas be more visible to the compiler is a good thing.

Cheers,
	Simon