More problems with memoization
 Diego Olivier FERNANDEZ PONS
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20060930 (18:21) 
From:  Diego Olivier FERNANDEZ PONS <diego.fernandez_pons@e...> 
Subject:  More problems with memoization 
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 righthand 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