Here's a post from Don Syme on a Fibonacci programming thread with the same programming issue . It was posted on the OCaml weekly news mailing list (please delete this post if there's any kind of problem with that).

==================

Don Syme said:
You may be interested in the approach to this kind of problem discussed
in [link:dx.doi.org] (see also tech report

at [link:research.microsoft.com]).

Under that approach you get to write the code in a natural way as shown
below: fib_mem is defined recursively, but the "cache" function has the
natural "(a -> b) -> (a -> b)" type and is abstract and reusable (no
details as to the nature of the internal table are revealed).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

let rec fib_mem = 
   cache (function 
            | 0 -> 0 
            | 1 -> 1 
            | n -> fib_mem (n - 1) + fib_mem (n - 2)) 

The use of a computation on the right of a "let rec" is allowed by
systematically introducing initialization holes using lazy values and
forces. There are disadvantages to this approach, as it introduces a
potential for initialization unsoundness somewhat similar to those in
most designs and implementations of recursive modules. However the
paper argues that in the balance it is not unreasonable for a strict
language to accept this in order to gain modularity and localize the
potential for unsoundness. It is even more compelling when often
working with abstract APIs such as Java and .NET GUI libraries.
While this isn't OCaml, and may not ever be the right design for OCaml,
I've found it a useful technique to know even when doing C#, C++ and
OCaml programming, as a broad range of recursion puzzles can be
addressed by modelling the problem the "natural" way (e.g. more like
Haskell) and then using a translation that introduces initialization
holes systematically. The translation of your sample into OCaml using
"lazy" initialization holes is shown below (for single recursion you can
also just use a "option ref"). Note "cache" does not change,
maintaining the property that the caching function is abstract and
reusable.

1
2
3
4
5
6
7
8
9

let (!!) x = Lazy.force x 

let rec fib_mem' = lazy 
   cache (function 
            | 0 -> 0 
            | 1 -> 1 
            | n -> !!fib_mem' (n - 1) + !!fib_mem' (n - 2)) 

let fib_mem = !!fib_mem' 

FWIW it is well known that laziness can be used in essentially this way,
e.g. see Michel Mauny's early papers on laziness in OCaml. However I've
not seen a paper that argues the case for making this the default
interpretation of "let rec" in a strict language.