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