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

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 -----

From: Yue Wang Date: Tue, 5 Oct 2010 21:23:57 -0400 To: Brent Yorgey 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?