<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font size="-1"><font face="Helvetica, Arial, sans-serif">Hi Maks,<br>
<br>
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.<br>
You can obtain an element from a unique array and use the array
again as an unique object with the operator !. <br>
For instance:<br>
<br>
fib j = memo.[j]<br>
where<br>
memo :: {#Int}<br>
memo = f 2 {createArray (max (j+1) 2) 0 & [1] = 1}<br>
<br>
f :: !Int *{#Int} -> *{#Int}<br>
f i a<br>
| i > j<br>
= a<br>
# (x,a) = a![i-1]<br>
(y,a) = a![i-2]<br>
= f (i+1) {a & [i] = (x+y) rem 10^6}<br>
<br>
A recursive reference implementation with is O(n) is:<br>
<br>
fibrec j = f 0 0 1<br>
where<br>
f :: !Int !Int !Int -> Int<br>
f i x y<br>
| i == j<br>
= x<br>
= f (i+1) y ((x+y) rem 10^6)<br>
<br>
A simple test to see if this works:<br>
<br>
Start = and [fib i == fibrec i \\ i <-[0..1000]]<br>
<br>
On may slow laptop this is yields True in 0.01 s.<br>
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:<br>
<br>
fib j = memo.[j]<br>
<br>
memo :: {#Int}<br>
memo =: f 2 {createArray (max (MaxFib+1) 2) 0 & [1] = 1}<br>
where<br>
f :: !Int *{#Int} -> *{#Int}<br>
f i a<br>
| i > MaxFib<br>
= a<br>
# (x,a) = a![i-1]<br>
(y,a) = a![i-2]<br>
= f (i+1) {a & [i] = (x+y) rem 10^6}<br>
<br>
Have fun,<br>
<br>
Pieter<br>
<br>
<br>
<br>
</font></font>
<div class="moz-cite-prefix">On 17/08/2012 4:19 PM, Maks Verver
wrote:<br>
</div>
<blockquote
cite="mid:20120817161923.6a15a684f3737f64d8986785@geocities.com"
type="cite">
<pre wrap="">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
<a class="moz-txt-link-abbreviated" href="mailto:clean-list@science.ru.nl">clean-list@science.ru.nl</a>
<a class="moz-txt-link-freetext" href="http://mailman.science.ru.nl/mailman/listinfo/clean-list">http://mailman.science.ru.nl/mailman/listinfo/clean-list</a>
</pre>
</blockquote>
<br>
</body>
</html>