<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>
<br>
You can use a lazy array and make it graph to avoid
recomputation:<br>
<br>
memo :: {Int}<br>
memo =:<br>
{createArray (MaxFib+1) 0<br>
& [1] = 1<br>
, [i] = (memo.[i-1] + memo.[i-2]) rem 10^6 \\ i <-
[2..MaxFib]<br>
}<br>
or<br>
<br>
memo :: {Int}<br>
memo =: {createArray (MaxFib+1) 0 & [i] = f i \\ i <-
[0..MaxFib]}<br>
where<br>
f 0 = 0<br>
f 1 = 1<br>
f i = (memo.[i-1] + memo.[i-2]) rem 10^6<br>
<br>
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.<br>
<br>
The definition of fib remains<br>
<br>
fib j = memo.[j]<br>
<br>
Does this solve you problem?<br>
<br>
Best, Pieter<br>
<br>
</font></font>
<div class="moz-cite-prefix">On 19/08/2012 6:37 PM, Maks Verver
wrote:<br>
</div>
<blockquote
cite="mid:20120819183703.309bf9fe3dbaea66d5b024a1@geocities.com"
type="cite">
<pre wrap="">Hi Pieter,
On Fri, 17 Aug 2012 17:32:12 +0200
Pieter Koopman <a class="moz-txt-link-rfc2396E" href="mailto:pieter@cs.ru.nl"><pieter@cs.ru.nl></a> wrote:
</pre>
<blockquote type="cite">
<pre wrap="">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.
</pre>
</blockquote>
<pre wrap="">
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.
</pre>
</blockquote>
<br>
</body>
</html>