[clean-list] Memoization of recursive functions using Clean arrays
Maks Verver
maksverver at geocities.com
Fri Aug 17 16:19:23 MEST 2012
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.
More information about the clean-list
mailing list