[Haskell-cafe] Re: Memoization in Haskell?
apfelmus at quantentunnel.de
Sat Jul 10 04:46:06 EDT 2010
Gregory Crosswhite wrote:
> Heinrich Apfelmus wrote:
>> Gregory Crosswhite wrote:
>>> You're correct in pointing out that f uses memoization inside of
>>> itself to cache the intermediate values that it commutes, but those
>>> values don't get shared between invocations of f; thus, if you call
>>> f with the same value of n several times then the memo table might
>>> get reconstructed redundantly. (However, there are other strategies
>>> for memoization that are persistent across calls.)
>> It should be
>> f = \n -> memo ! n
>> memo = ..
>> so that memo is shared across multiple calls like f 1 , f 2 etc.
> That actually doesn't work as long as memo is an array, since then it
> has fixed size; you have to also make memo an infinitely large data
> (but lazy) structure so that it can hold results for arbitrary n. One
> option for doing this of course is to make memo be an infinite list, but
> a more space and time efficient option is to use a trie like in MemoTrie.
Oops, silly me! I erroneously thought that the code was using f
instead of (memo !) in the definition of the array, like this
f :: (Integral a, Ord a, Ix a) => a -> a
f n = memo ! n
memo = array (0,n) $ (0,0) :
[(i, max i (f (i `quot` 2)
+ f (i `quot` 3) + f (i `quot` 4)))
| i <- [1 .. n]]
But since memo depends on n , it cannot be lifted outside the lambda
More information about the Haskell-Cafe