More problems with memoization

[Diego Olivier FERNANDEZ PONS <diego.fernandez_pons@etu.upmc.fr>]

     Bonjour,

I wrote the following (classical) memoized code for the fibonacci  
function and I have been unsuccessfully trying to generalize it with a  
higher order function.

let rec fib = function
   | 0 -> 0
   | 1 -> 1
   | n -> fib_mem (n - 1) + fib_mem (n - 2)
and fib_mem =
   let table = ref [] in
     function n ->
       try
	List.assoc n !table
       with Not_found ->
	let f_n = fib n in
	  table := (n, f_n) :: !table;
	  f_n

# val fib : int -> int = <fun>
# val fib_mem : int -> int = <fun>

It works: fib 35 answers instantaneously.

Now I want to achieve the same result with a higher order function  
[make_memo] and apply it to fib

let make_mem = function f ->
   let table = ref [] in
     function n ->
       try
	List.assoc n !table
       with Not_found ->
	let f_n = f n in
	  table := (n, f_n) :: !table;
	  f_n

#val make_mem : ('a -> 'b) -> 'a -> 'b

Very well. Notice that it has one less parameter than the code posted  
by Andrej Bauer which has type memo_rec : (('a -> 'b) -> 'a -> 'b) ->  
'a -> 'b. The only difference is the line

let f_n = f n in ...
with respect to
let f_n = f g n in ... where g is the anonymous function itself

in the same way Bauer's [fib_memo] uses an extra parameter [self]

let fib_memo =
   let rec fib self = function
     | 0 -> 1
     | 1 -> 1
     | n -> self (n - 1) + self (n - 2)
   in
     memo_rec fib


Now I try to apply make_mem to but it does not work

let rec fib = function
   | 0 -> 0
   | 1 -> 1
   | n -> fib_mem (n - 1) + fib_mem (n - 2)
and fib_mem = make_mem fib

# This kind of expression is not allowed as right-hand side of `let rec'

Ok... usually one only need to expand to avoid the problem

let rec fib = function
   | 0 -> 0
   | 1 -> 1
   | n -> fib_mem (n - 1) + fib_mem (n - 2)
and fib_mem = function n ->
   let f = make_mem fib in
     f n

# val fib : int -> int = <fun>
# val fib_mem : int -> int = <fun>

But know fib 35 takes several minutes to be computed !

I believe I understand why: I am computing a different fib_mem for  
each value of n and applying it just after, while I wanted a single  
fib_mem to be used for all computations. In the process, the  
tabulation vanishes.

The only work around I found is to lift the table argument in [make_mem]

let make_mem = fun table f ->
   function n ->
     try
       List.assoc n !table
     with Not_found ->
       let f_n = f n in
	table := (n, f_n) :: !table;
	f_n

# val make_mem : ('a * 'b) list ref -> ('a -> 'b) -> 'a -> 'b = <fun>

And build fib in the following way

let fib_mem = function n ->
   let table = ref [] and
       fib = function
	| 0 -> 0
	| 1 -> 1
	| n -> fib_mem (n - 1) + fib_mem (n - 2)
   in make_mem table fib n

# fib_mem 35: instantaneous

The problem is that the memoization is much more intrusive, which is  
what I was trying to avoid.

         Diego Olivier