OCaml中的记忆和参考列表

我正在学习OCaml。我知道OCaml为我们提供了编程和函数式编程的强制性风格。OCaml中的记忆和参考列表

我碰到这个代码来为我的课程来计算OCaml中

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以标准方式实现的第n个Fibonacci数的部分内容如下：

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

现在我的问题是，我们如何实现fibonacci2中的memoisation。 table已在函数fibonacci2中定义，因此，我的逻辑规定函数完成计算后，列表table应该丢失，并且在每次调用之后，表将一次又一次地建立。

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

我虽然这可能是可能的，如果声明变量使用ref默认给它一个全局范围。

所以，我想这个

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

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

为什么这样表现？

来源

2016-04-14 Banach Tarski

功能memoise返回一个值，称之为f。（f恰好是一个函数）。该值的一部分是表格。每当您拨打memoise时，您将获得不同的价值（使用不同的表格）。

在此示例中，返回值f的名称为fibonacci2。所以，名为fibonacci2的东西里面有一个表格，可以被功能f使用。

默认情况下没有全局范围，这将是一个巨大的混乱。无论如何，这是一个不是范围的问题。 OCaml中的生命周期只要能够以某种方式达到目标。在表格的情况下，它可以通过返回的函数到达，因此它只要函数一直持续下去。

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

尽管引用有点棘手，OCaml的底层语义来自lambda微积分，并且非常干净。这就是为什么在OCaml（恕我直言）中编写代码非常愉快。

来源

2016-04-14 16:23:32

你说这个返回的值'f'是一个函数，但你也可以说这个值的一部分就是这个表。我不确定这意味着什么。 –

函数与函数的所有自由变量（所有未在函数中定义的名称）的值捆绑在一个闭包中。所以，一个函数（或者一个闭包）实际上可以有任意的东西。 “memoise”返回的封闭内有表格。 –

OCaml中的记忆和参考列表

回答

相关问题