functional-programming - OCaml 中 let rec 的限制

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'

其中，memoize 是一个函数，它接受一个函数并将其转换为带有 Hashtable 的记忆版本。很明显，OCaml 对“let rec”右侧结构的使用有一些限制，但我真的不明白，有人能解释一下吗？

Answer 1

允许受约束的表达式类型在手册的第 8.1 节let rec中进行了描述。具体来说，不允许涉及已定义名称的函数应用。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按照 Alain 的提醒使用：

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