Ограничения let rec в OCaml

Question

Я изучаю OCaml в эти дни и столкнулся с этим:

OCaml имеет ограничения на то, что он может поместить на правой стороне let rec. Как этот

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'

в котором памятка - это функция, которая берет функцию и превращает ее в запомненную версию с помощью Hashtable. Очевидно, что в OCaml есть некоторые ограничения на использование конструкций в правой части 'let rec', но я не понимаю, может кто-нибудь объяснить немного больше об этом?

Answer 1

Вид выражений, которые могут быть связаны let rec описаны в разделе 7.3 руководства. В частности, функциональные приложения, включающие let rec определенные имена не допускаются.

Грубое резюме (по той же ссылке):

Неформально класс принятых определений состоит из тех определений, в которых определенные имена встречаются только внутри тел функций или в качестве аргумента для конструктора данных.

Answer 2

Вы можете использовать методы привязки к узлу для определения запоминающих точек фиксации. Посмотрите, например, эти два эквивалентных определения:

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

Или используя lazy как напомнил Ален:

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

Answer 3

Это четко объяснено в разделе Memoization and Dynamic Programming в https://realworldocaml.org/v1/en/html/imperative-programming-1.html