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

[Maks Verver]

Hi Pieter,

On Mon, 20 Aug 2012 12:54:38 +0200
Pieter Koopman <pieter at cs.ru.nl> wrote:
> By using =: in the definition of memo instead of =, you create a
> graph that is evaluated at most once.

Thanks, I had overlooked the differences between graphs/constants and
global/local definitions.  Using =: does allow me to solve my problems,
but it also raises a couple more questions.

I've now rewritten my code like this:

  fib_rec :: (Int -> Int) Int -> Int
  fib_rec _ 0 = 0
  fib_rec _ 1 = 1
  fib_rec f i = (f (i - 2) + f (i - 1)) rem 1000000

  memoize :: ((Int -> Int) -> Int -> Int) Int -> (Int -> Int)
  memoize f max = g
      where
          g = select memo
          memo :: {Int}
          memo = { f g i \\ i <- [0..max] }

  fib =: memoize fib_rec 10000

The =: in the last line is required to prevent the memo from being
recomputed unnecessarily.  However, there are a couple of weird
things about this code:

 1. My program segfaults when I try to call fib with an argument
outside the range of the array, even when compiling with -ci.  Of
course that can't work, but I'd expect an array-index-out-of-bounds
error in that case.  Could this be a bug in the code generator?

 2. I'd like the type of `memoize' to be ((Int -> a) -> Int -> a) Int ->
(Int -> a).  But in that case I don't know how to type memo; {a} is not
allowed, and omitting the type of memo entirely fails due to unresolved
overloading.  Is there a solution for this?

 3. The desired sharing of memo seems to occur only if I define g as a
partially applied function.  For example, defining:
    g i = memo.[i]
or:
    g i = select memo i
or:
    g =: \i -> memo.[i]
... results in the memo being recomputed for every invocation of g (and
thus exponential runtime).  But if I use a list instead of an array
for the memo, this doesn't occur: `g i = memo!!i' works fine.

Apparently (\y -> f x y) isn't equivalent to (f x).  That's really
surprising!

 - Maks.