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

[Pieter Koopman]

Hi Maks,


You can use a lazy array and make it graph to avoid recomputation:

memo :: {Int}
memo =:
     {createArray (MaxFib+1) 0
     & [1] = 1
     , [i] = (memo.[i-1] + memo.[i-2]) rem 10^6 \\ i <- [2..MaxFib]
     }
  or

memo :: {Int}
memo =: {createArray (MaxFib+1) 0 & [i] = f i \\ i <- [0..MaxFib]}
where
     f 0 = 0
     f 1 = 1
     f i = (memo.[i-1] + memo.[i-2]) rem 10^6

By using =: in the definition of memo instead of =, you create a graph 
that is evaluated at most once. Since it is a lazy array the array 
elements are only calculated when they are needed. By changing the type 
of memo to {#Int} you create a unboxed array which is strict but stored 
more efficiently.

The definition of fib remains

fib j =  memo.[j]

Does this solve you problem?

Best, Pieter

On 19/08/2012 6:37 PM, Maks Verver wrote:
> Hi Pieter,
>
> On Fri, 17 Aug 2012 17:32:12 +0200
> Pieter Koopman <pieter at cs.ru.nl>  wrote:
>> 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.
> Thanks for the suggestion!  I suppose that works, but that's a strict
> computation.  A really nice property of the Haskell version of the code
> is that it's still a lazy computation; array values are computed only
> if/when they are needed.
>
> Making the array elements boxed/non-strict in your version of the code
> doesn't achieve the same effect because computing the final array value
> still requires expanding all function calls (parts of which may be left
> uncomputed, but that just means you use a lot of memory in addition to
> a lot of time -- the worst of both worlds).
>
> Maybe the way I originally phrased my question was misleading way,
> because some further experimentation reveals that my problem doesn't
> apply to arrays specifically, but values in Clean not being shared
> when I expect them to.
>
> For example, this implementation:
>
>    fib i = memo!!i
>
>    memo = map f [0..]
>
>    f 0 = 0
>    f 1 = 1
>    f i = fib (i - 2) + fib (i - 1) rem 1000000
>
> ... seems to have comparable (exponential-time) performance.  I'd
> expect the value of `memo' to be shared so that its elements aren't
> recomputed but apparently that doesn't happen.  Why not?  Is there a
> way to make Clean behave more like Haskell in this regard?
>
>   - Maks.

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