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
[email protected]
http://mailman.science.ru.nl/mailman/listinfo/clean-list
_______________________________________________
clean-list mailing list
[email protected]
http://mailman.science.ru.nl/mailman/listinfo/clean-list
