Recollection in OCaml?

Question

You can improve the raw recursive Fibonacci procedure

Fib[n_] := If[n < 2, n, Fib[n - 1] + Fib[n - 2]] 

from

 Fib[n_] := Fib[n] = If[n < 2, n, Fib[n - 1] + Fib[n - 2]] 

at Wolfram Mathematica.

The first version will suffer from an exponential explosion, and the second - since Mathematica will see repeated calls of functions in expressions and memoize (reuse).

Can I do the same in OCaml?

How to improve

 let rec fib n = if n<2 then n else fib (n-1) + fib (n-2);; 

in the same way?

Answer 1

You pretty much do what the math version does, but manually:

 let rec fib = let cache = Hashtbl.create 10 in begin fun n -> try Hashtbl.find cache n with Not_found -> begin if n < 2 then n else let f = fib (n-1) + fib (n-2) in Hashtbl.add cache nf; f end end 

Here I select a hash table to store the already calculated results, and not to recalculate them. Note that you should still beware of integer overflows, since we are using a regular rather than a large int.

Answer 2

The solution provided by rgrinberg can be generalized so that we can memoize any function. I am going to use associative lists instead of hashtables. But that doesn’t really matter, you can easily convert all my examples to use hashtables.

Firstly, here is the memo function, which takes another function and returns its memoized version. This is what Nlucaroni suggested in one of the comments:

 let memo f = let m = ref [] in fun x -> try List.assoc x !m with Not_found -> let y = fx in m := (x, y) :: !m ; y 

The memo f function stores a list of m results computed so far. When asked to calculate fx , he first checks m to see if fx has already been calculated. If so, it returns the result, otherwise it actually computes fx , stores the result in m and returns it.

The problem with the above memo in case f is recursive. When memo calls f to evaluate fx , any recursive calls made to f will not be caught by memo . To solve this problem, we need to do two things:

• In the definition of such a recursive f we need to substitute recursive calls with calls to the function that will be provided later (this will be the memoized version of f ).

• In memo f we need to provide f promised function that you must call when you want to make a recursive call. "

This leads to the following solution:

 let memo_rec f = let m = ref [] in let rec gx = try List.assoc x !m with Not_found -> let y = fgx in m := (x, y) :: !m ; y in g 

To demonstrate how this works, let's recall the naive Fibonacci function. We need to write it down so that it takes an additional argument, which I will call self . This argument is what the function should use instead of recursively calling itself:

 let fib self = function 0 -> 1 | 1 -> 1 | n -> self (n - 1) + self (n - 2) 

Now, to get memoized fib , we will calculate

 let fib_memoized = memo_rec fib 

You can try to see that fib_memoized 50 returns instantly. (This is not the case for memo f , where f is the usual naive recursive definition.)