[clean-list] Memoization of recursive functions using Clean arrays

[Maks Verver]

Hi Pieter,

On Fri, 17 Aug 2012 17:32:12 +0200
Pieter Koopman <pieter at cs.ru.nl>  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.