[Haskell-cafe] Re: Memoization in Haskell?

[Gregory Crosswhite]

  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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe