Limitations of let rec in OCaml

Question

I'm studying OCaml these days and came across this:

OCaml has limits on what it can put on the righthand side of a let rec. Like this one

let memo_rec f_norec =
let rec f = memoize (fun x -> f_norec f x) in
f;; 
Error: This kind of expression is not allowed as right-hand side of `let rec'

in which, the memoize is a function that take a function and turns it into a memorized version with Hashtable. It's apparent that OCaml has some restriction on the use of constructs at the right-hand side of 'let rec', but I don't really get it, could anyone explain a bit more on this?

Answer 1

The kind of expressions that are allowed to be bound by let rec are described in section 8.1 of the manual. Specifically, function applications involving the let rec defined names are not allowed.

A rough summary (taken from that very link):

Informally, the class of accepted definitions consists of those definitions where the defined names occur only inside function bodies or as argument to a data constructor.

Answer 2

You can use tying-the-knot techniques to define memoizing fixpoints. See for example those two equivalent definitions:

let fix_memo f =
  let rec g = {contents = fixpoint}
  and fixpoint x = f !g x in
  g := memoize !g;
  !g

let fix_memo f =
  let g = ref (fun _ -> assert false) in
  g := memoize (fun x -> f !g x);
  !g

Or using lazy as reminded by Alain:

let fix_memo f =
  let rec fix = lazy (memoize (fun x -> f (Lazy.force fix) x)) in
  Lazy.force fix