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. Cheers, Greg 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 where memo = ..
so that memo is shared across multiple calls like f 1 , f 2 etc.
Regards, Heinrich Apfelmus
-- http://apfelmus.nfshost.com
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe