[Haskell-cafe] memoization

[Andreas Abel]

Sorry I screwed up.  The following is indeed memoizing:

fib5 :: Int -> Integer
fib5 = \ x -> fibs !! x
    where fibs = map fib [0 ..]
          fib 0 = 0
          fib 1 = 1
          fib n = fib5 (n-2) + fib5 (n-1)

Here, the eta-expansion does not matter.  But as you say, memoized_fib 
below is not memoizing, since x is in scope in the where clauses, even 
though they do not mention it.  Thus, for each x we get "new" 
definitions of fibs and fib.  Yet, this is only true for -O0.

For -O1 and greater, ghc seems to see that x is not mentioned in the 
where clauses and apparently lifts them out.  Thus, for -O1.. 
memoized_fib is also memoizing.  (I ran it, this time ;-) !)

Cheers,
Andreas

On 22.07.13 11:43 PM, Tom Ellis wrote:
> On Mon, Jul 22, 2013 at 04:16:19PM +0200, Andreas Abel wrote:
>> In general, I would not trust such compiler magic, but just let-bind
>> anything I want memoized myself:
>>
>> memoized_fib :: Int -> Integer
>> memoized_fib x = fibs !! x
>>      where fibs  = map fib [0..]   -- lazily computed infinite list
>>            fib 0 = 0
>>            fib 1 = 1
>>            fib n = memoized_fib (n-2) + memoized_fib (n-1)
>>
>> The eta-expansions do not matter.

I meant to write

   "Then, eta-expansions do not matter."

(In general, they do matter.)

> But this is *not* memoized (run it and see!).  The "eta-expansions" do
> indeed matter (although I don't think they are truly eta-expasions because
> of the desugaring of the where to a let).
>
> What matters is not the let binding, but where the let binding occurs in
> relation to the lambda.  There's no compiler magic here, just operational
> semantics.
>
> Tom
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY

andreas.abel at ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/