[Haskell-cafe] Re: Memoization in Haskell?
gcross at phys.washington.edu
Fri Jul 9 12:45:45 EDT 2010
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.
On 7/9/10 12:50 AM, 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.
> Heinrich Apfelmus
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe