This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

More problems with memoization
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Diego Olivier FERNANDEZ PONS 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 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