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

8 Oct 2010

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

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

Simon Marlow