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