[Haskell-cafe] Eta-expansion destroys memoization?
Daniel Fischer
daniel.is.fischer at web.de
Thu Oct 7 09:10:45 EDT 2010
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?
More information about the Haskell-Cafe
mailing list