christopher.howard at frigidcode.com
Mon Jul 22 22:59:19 CEST 2013
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.
Is this behavior codified somewhere? (I can't seem to find it in the GHC
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."
More information about the Haskell-Cafe