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

[Maks Verver]

On Tue, 21 Aug 2012 13:16:51 +0200
Pieter Koopman <pieter at cs.ru.nl> wrote:
> 1) Most likely you have to recompile _SystemArray with the -ci flag 
> (throw away the .o object file).

That's it.  For future reference, I did this:

  make -C path-to-clean-dir CLMFLAGS+=-ci cleanup install


> 2) For instance
> memoize :: ((Int -> e) -> (Int -> e)) Int -> (Int -> e)
> memoize f max = select (memo f max)
> where
>      memo :: ((Int -> e) -> (Int -> e)) Int -> {e}
>      memo f max = array
>      where array = { f (select array) i \\ i <- [0..max] }

I see.  That's a useful trick, though in this case you've reshuffled
the definitions considerably.

In this case I can also fix my problem by introducing a function to
restrict the kind of array used:

  lazyArray :: u:{a} -> u:{a}
  lazyArray a = a

And then stay relatively close to the original, simpler definition:

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

> The standard solution is to add an argument to fix the the type.

I can't imagine that's always a nice solution, considering that adding
an argument to a constant expression apparently affects the efficiency
of the resulting program.


> 3) It is essential to define the memo object as a local constant,
> that is a definition without arguments. In that way it will become a
> local graph which is shared in all compuations. Each local definition
> with arguments is a function. Functions are lifted to the global
> level by the compiler an evaluated for each argument all over again.
> This is exactly what you try to avoid.

This sounds reasonable but I still have trouble applying this to
concrete programs.  For example, it doesn't explain why this is fast,
even though I use a lambda-closure:

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

... while adding a type to memo makes it slow:

  memoize :: ((Int -> Int) -> Int -> Int) Int -> (Int -> Int)
  memoize f max = g
      where
          g = \i -> memo.[i]
          memo :: {Int}  // <-- only added this
          memo =: lazyArray { f g i \\ i <- [0..max] }

What is the type inferred by the compiler in the first case that would
result in a completely different kind of evaluation?

Or does adding a type declaration turn `memo' from a graph into a
(constant) function?  In that case, shouldn't the compiler reject my
use of `=:' instead of `='?

 - Maks.