[clean-list] Memoization of recursive functions using Clean arrays

[Pieter Koopman]

Hi Maks,

The problem is that you need inline updates of your array to obtain the 
desired memoization effect. The way to obtain inline updates is to 
create an array and to pass it as a unique object in your function f.
You can obtain an element from a unique array and use the array again as 
an unique object with the operator !.
For instance:

fib j =  memo.[j]
where
     memo :: {#Int}
     memo = f 2 {createArray (max (j+1) 2) 0 & [1] = 1}

     f :: !Int *{#Int} -> *{#Int}
     f i a
         | i > j
             = a
             # (x,a) = a![i-1]
               (y,a) = a![i-2]
             = f (i+1) {a & [i] = (x+y) rem 10^6}

A recursive reference implementation with is O(n) is:

fibrec j = f 0 0 1
where
     f :: !Int !Int !Int -> Int
     f i x y
         | i == j
             = x
             = f (i+1) y ((x+y) rem 10^6)

A simple test to see if this works:

Start = and [fib i == fibrec i \\ i <-[0..1000]]

On may slow laptop this is yields True in 0.01 s.
This is of course rather inefficient: it creates 1001 times an array for 
memoization. It is better to use one memo array for every call to fib 
instead of creating a new one array for each call:

fib j =  memo.[j]

memo :: {#Int}
memo =: f 2 {createArray (max (MaxFib+1) 2) 0 & [1] = 1}
where
     f :: !Int *{#Int} -> *{#Int}
     f i a
         | i > MaxFib
             = a
             # (x,a) = a![i-1]
               (y,a) = a![i-2]
             = f (i+1) {a & [i] = (x+y) rem 10^6}

Have fun,

Pieter



On 17/08/2012 4:19 PM, Maks Verver wrote:
> Hi everyone,
>
> In Haskell, an easy and efficient way to apply memoization to a
> recursive function is to create an array which holds all values in the
> (desired) domain of that function, and index that array instead of
> calling the function directly.
>
> For example, the Fibonacci function modulo 1,000,000 could be
> implemented recursively as:
>
>    fib_slow 0 = 0
>    fib_slow 1 = 1
>    fib_slow i = fib_slow (i - 2) + fib_slow (i - 1) `mod` 1000000
>
> But of course this is very slow for values of i > 25 or so.  If the
> range of the argument is known (for example i <= 1000) then an easy
> solution is to cache values in an array:
>
>    fib = (!)memo
>        where
>            memo = array (0,1000) [ (i, f i) | i <- [0..] ]
>            f 0 = 0
>            f 1 = 1
>            f i = fib (i - 2) + fib (i - 1) `mod` 1000000
>
> Note that the definition of f mirrors that of fib_slow, except that it
> calls the memoized function fib instead of itself.  This is quite fast;
> not just because of memoization but also because array elements are
> only computed when needed.  So f is called at most 1,001 times.
>
> I tried to recreate this pattern in Clean but did not get it to work as
> desired.  For example, consider the following equivalent-looking Clean
> code:
>
>    fib i = memo.[i]
>        where
>            memo :: {Int}
>            memo = { f i \\ i <- [0..1000] }
>            f 0 = 0
>            f 1 = 1
>            f i = (memo.[i - 1] + memo.[i - 2]) rem 1000000
>
> Computing fib 100 takes "forever" (without using much memory) as if no
> memoization applies.  However, making the array strict/unboxed (memo ::
> {!Int} or {#Int}) yields a "Heap full." error as soon as the function
> is called.
>
> So apparently arrays in Clean do not work as I expected/was used to
> from Haskell.  How should I understand what happens here?  Is there a
> way to make memoization work like this in Clean?  If so, how?  If not,
> what is a good alternative?
>
> Kind regards,
> Maks Verver.
> _______________________________________________
> clean-list mailing list
> clean-list at science.ru.nl
> http://mailman.science.ru.nl/mailman/listinfo/clean-list

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.science.ru.nl/pipermail/clean-list/attachments/20120817/a55d2870/attachment.html>