memoization hints?
Feuer
feuer@his.com
Fri, 18 Jan 2002 05:33:47 -0500
It seems that under some circumstances it might be good for a programmer
to be able to tell the implementation not to remember something. In
particular, intermediate data structures may be remembered for much
longer than they should be. If I am not mistaken, full laziness (which
I think ghc uses with -O ?) can make this worse. Would it be beneficial
to have some kind of annotations to help deal with this? I don't really
know how it would be implemented.
Take a standard sort of example:
fib n = let
f = 0:1:zipWith (+) f (tail f)
in
f !! n
-- code that first calculates fib 1000, then fib 3, fib 4, then does
some other stuff
I believe that the entire list will be maintained (when compiled with
ghc -O) after calculating fib 1000, despite the fact that it will never
be used again. If I could say instead
fib n = let
forget f = 0:1:zipWith (+) f (tail f)
in
f !! n
and somehow get it to forget about f as often as possible (somehow
suppressing laziness in this case). I would certainly want to forget
about it whenever it goes out of scope, but in this case I would really
want to somehow ensure that the list is never held entirely in memory
(forgetting it as it is built in f !! n).