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." _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe