Re: [Caml-list] More problems with memoization

[Andrej Bauer <Andrej.Bauer@fmf.uni-lj.si>]

Diego Olivier FERNANDEZ PONS wrote:
> In my first example you keep the type of [fib] and add a second function 
> [fib_mem]. You can use anyone indifferently and hide the latter with the 
> .mli
> val fib : int -> int = <fun>
> val fib_mem : int -> int = <fun>

If you want to keep the same type for fib, and have the memoized one, as 
well as to have locality you can do something like this:

let make_memo f = ...

let rec make_rec f x = f (make_rec f) x

let fib, fib_mem =
   let fib' self = function
     | 0 -> 0
     | 1 -> 1
     | n -> self (n - 1) + self (n - 2)
   in
     make_rec fib', make_mem fib

(You will notice that make_rec is just the Y combinator.)

> When you compare your solution with what I am trying to do you see there 
> is a big difference in locality and transparency

I fail to see this big difference, frankly, since all you're doing is 
just a beta-reduction of what Jon and I suggested.

A recursive function _is_ the fixed point of a non-recursive one with an 
"extra" argument. You may hide this fact if you wish, but I think it's 
more honest to admit it to yourself. The "untied" version of fib has the 
advantage that you can do many cool things to it: memoizing is just one 
possibility.

Andrej