使用连续传递风格实现简单的阶乘函数

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)

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

总而言之，三个简单的规则：

1. 返回并继续
2. 从身份开始
3. 更新每个步骤的延续。

但无论如何，you function 是一个有趣的解决方案。事实上，您正在使用的是构建一个惰性的闭包列表。在计算的每一步中，您都会创建一个闭包，它使用之前的闭包并将其乘以 n。当达到 0 时，就称此为闭包链。因此，这是空间上的 O(n)，但您使用的是堆而不是堆栈。当然，我的解决方案在空间上是O(n)。我只是澄清一下。