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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
