ocaml - 使用延续传递风格实现一个简单的阶乘函数

Question

我正在尝试实现一个在 OCaml 中返回阶乘的函数，但我不知道我是否真的在使用延续传递样式:

let fact n =
  let rec factorial n cont = match n with
    | 0 -> cont ()
    | _ -> factorial (n-1) (fun () -> cont () * n) in
  factorial n (fun () -> 1)

在我看来，我并没有真正延迟计算，而只是取代了我的代码中的计算。

Answer 1

嗯，实际上你的代码很有趣。它不是很常见，但它是尾递归的，所以它会起作用。我将向您展示执行 CPS 的“常规”方式。通常，您使用延续从函数返回，这就是为什么将延续命名为 return 之类的好主意。 .此外，通常您以恒等函数作为延续的初始值。最后，您将延续用作程序集，在其中构建答案。

let factorial n = 
  let rec loop n return = match n with
    | 0 -> return 1
    | n -> return (loop (n-1) (fun x -> x * n)) in
  loop n (fun x -> x)

所以在这个例子中，我传递了一个将累积并最终构建答案的延续。

总结一下，三个简单的规则:

继续返回

以身份开头

更新每一步的延续。

但无论如何，你的函数是一个有趣的解决方案。 a确实，您正在使用的是构建一个懒惰的闭包列表。在计算的每一步中，您都在创建一个闭包，它使用先前的闭包并将其乘以 n。当您达到 0 时，您将调用此闭包链。因此，这是空间中的 O(n)，但您使用的是堆而不是堆栈。当然，我的解决方案是空间中的 O(n)。我只是澄清一下。