recursion - OCaml 中的内存和引用列表

Question

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

我在 OCaml 中计算第 n 个斐波那契数的类(class)中遇到了这段代码

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 应该丢失，并且在每次调用后都会构建表一次又一次。

我运行了一些简单的测试，在 OCaml REPL 中调用函数 fibonacci 35 两次，第二次函数调用返回答案的速度明显快于第一次调用该函数(与我的预期相反) )。

我认为，如果使用 ref 声明一个变量，默认情况下它会具有全局作用域，那么这可能是可能的。

所以我尝试了这个

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

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

为什么会这样？

Answer 1

函数memoise返回一个值，称之为f。 (f 恰好是一个函数)。该值的一部分是表格。每次调用 memoise 时，您都会获得不同的值(使用不同的表)。

在该示例中，返回值 f 的名称为 fibonacci2。因此，名为 fibonacci2 的东西内部有一个表，可供函数 f 使用。

默认情况下没有全局作用域，那将是一个巨大的困惑。无论如何，这是一个生命周期的问题，而不是范围的问题。 OCaml 中的生命周期只要能够以某种方式到达对象就持续存在。对于表来说，可以通过返回的函数访问它，因此它的持续时间与函数一样长。

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

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