[Haskell-cafe] Re: Memoization in Haskell?

[Heinrich Apfelmus]

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
>>         where
>>         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
       where
       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 
abstraction.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com