[Haskell-cafe] Eta-expansion destroys memoization?

[Daniel Fischer]

On Thursday 07 October 2010 14:17:18, Brent Yorgey wrote:
> Hi all,
>
> See below for this message from one of my students which has me
> stumped.  Just when you think you understand Haskell... ;)
>
> I've cc'ed him on this message; please include him on any replies as I
> don't think he is subscribed to -cafe.
>
> -Brent

cf. http://www.haskell.org/pipermail/haskell-cafe/2009-October/067811.html

If fib is defined without a type signature, the monomorphism restriction 
also kicks in, when fib is bound via a function binding,

fib x = ...

fib has polymorphic type (Num a) => Int -> a
and that prevents sharing the list (since there are lists for all Num 
types). If bound via a simple pattern binding,

fib = (map fib' [0 .. ] !!)
  where
    ...

and the MR is not disabled, fib gets the monomorphic type Int -> Integer
and that allows the list to be shared.

If you give fib an explicit monomorphic type

fib :: Int -> Integer

the list will still not be shared if it's bound via a function binding 
because fib' and the list are bound inside the lambda:

fib = \k -> let fib' ... in (map fib' [0 .. ] !!) k

fib' is not a constant, so it's not floated out of the lambda, so it's not 
shared (and a fortiori map fib' [0 .. ] isn't shared).

if fib is bound via a simple pattern binding (and no explicit lambda is 
given), fib' and the list are bound outside the lambda and hence shared:

fib = let fib' = ...; lst = map fib' [0 .. ] in \k -> lst !! k

Note however that using the list as "map fib' [0 .. ]" is more brittle than 
giving it a name and binding it explicitly in the where clause:

fib :: Int -> Integer
fib = (fibList !!)
  where
    fibList = map fib' [0 .. ]
    fib' 0 = 0
    ...

For the time being, GHC treats both the same, but the latter is less likely 
to break.

>
> ----- Forwarded message from Yue Wang <yulewang at gmail.com> -----
>
> From: Yue Wang <yulewang at gmail.com>
> Date: Tue, 5 Oct 2010 21:23:57 -0400
> To: Brent Yorgey <byorgey at seas.upenn.edu>
> Subject: store evaluated values
>
> Hi, Anthony (or Brent):
>
> Last time (in Anthony's TA office hour) we talked about how to store
> evaluated values in the program for later used. I googled for a while
> and wrote some code. But I still encountered two problems. Can you take
> a look? Thanks.
>
> First, let's write the naive fib function:
>
> naive_fib 0 = 0
> naive_fib 1 = 1
> naive_fib n = trace(show(n))
>               naive_fib (n - 1) + naive_fib (n - 2)
>
> this works good except it tries to calculate the same expression many
> times. So when we evaluate it ghci will show the following: *Main>
> naive_fib 5
> 5
> 4
> 3
> 2
> 2
> 3
> 2
> 5
>
> Then there is a clever way to do that on haskell wiki:
>
> fib = ((map fib' [0 ..]) !!)
>     where
>       fib' 0 = 0
>       fib' 1 = 1
>       fib' n =trace(show(n)) fib (n - 1) + fib (n - 2)
>
> When we evaluate the same expression we can see it does not evaluate the
> redundant expression over and over: *Main> fib 5
> 5
> 4
> 3
> 2
> 5
>
> 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. But After I change that, *Main> fib
> 5
> 5
> 4
> 3
> 2
> 2
> 3
> 2
> 5
>
> So why does the x here matters?