[Haskell-cafe] memoization

[Christopher Howard]

On 07/22/2013 06:16 AM, Andreas Abel wrote:
> On 22.07.2013 09:52, Chris Wong wrote:
>
> True, but the essential thing to be memoized is not memoized_fib,
> which is a function, but the subexpression
>
>   map fib [0..]
>
> which is an infinite list, i.e., a value.
>
> The rule must be like "in
>
>   let x = e
>
> if e is purely applicative, then its subexpressions are memoized."
> For instance, the following is also not memoizing:
>
> fib3 :: Int -> Integer
> fib3 = \ x -> map fib [0 ..] !! x
>    where fib 0 = 0
>          fib 1 = 1
>          fib n = fib3 (n-2) + fib3 (n-1)
>
> 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.
>
> Cheers,
> Andreas
>

Is this behavior codified somewhere? (I can't seem to find it in the GHC
user guide.)

The memoize package from hackage, interestingly enough, states that
"[Our memoization technique] relies on implementation assumptions that,
while not guaranteed by the semantics of Haskell, appear to be true."