OCaml 中的记忆和参考列表

Question

我正在学习 OCaml。我知道 OCaml 为我们提供了命令式编程风格和函数式编程。

我在 OCaml 中计算第 n 个斐波那契数的课程中遇到了这段代码

let memoise f =
  let table = ref []
  in
  let rec find tab n =
    match tab with
    | []           -> 
            let v = (f n)
            in
            table := (n, v) :: !table;
            v
    | (n', v) :: t -> 
            if n' = n then v else (find t n)
  in
  fun n -> find !table n

let fibonacci2 = memoise fibonacci1

其中函数fibonacci1的标准实现方式如下：

let rec fibonacci1 n =
  match n with
  | 0 | 1 -> 1
  |     _ -> (fibonacci1 (n - 1)) + (fibonacci1 (n - 2))

现在我的问题是我们如何在 fibonacci2 中实现记忆。 table 已在函数 fibonacci2 中定义，因此，我的逻辑表明在函数完成计算后，列表 table 应该丢失，并且在每次调用后 table 将再次构建并且再次.

我运行一些简单的测试，我在 OCaml REPL 中调用函数 fibonacci 35 两次，第二次函数调用返回答案的速度明显快于第一次调用函数（与我的期望）。

我认为如果使用 ref 声明一个变量默认情况下赋予它一个全局范围，这可能是可能的。

所以我尝试了这个

let f y = let x = ref 5 in y;;
print_int !x;;

但这给了我一个错误，说 x 的值是无界的。

为什么会这样？

Answer 1

函数memoisereturns一个值，称它为f。（f 恰好是一个函数）。该值的一部分是 table。每次调用 memoise 都会得到不同的值（具有不同的 table）。

在示例中，返回值 f 的名称为 fibonacci2。所以，名为 fibonacci2 的东西里面有一个 table 可以被函数 f.

使用

默认情况下没有全局范围，那将是一团糟。无论如何，这是一个生命周期的问题，不在范围之内。 OCaml 中的生命周期持续到可以以某种方式到达对象为止。在 table 的情况下，它可以通过返回的函数到达，因此只要函数存在，它就会持续。

在您的第二个示例中，您正在测试 x 的范围（不是生命周期），实际上 x 的范围仅限于其 let 的子表达式。（即，它只在表达式 y 中没有被使用时才有意义。）在原始代码中，table 的所有使用都在其 let 中，因此没有问题。

虽然引用有点棘手，但 OCaml 的底层语义来自 lambda 演算，并且非常干净。这就是为什么用 OCaml（恕我直言）编写代码如此令人愉快。

OCaml 中的记忆和参考列表

Memoisation in OCaml and a Reference List

recursion

ocaml

functional-programming