使用延续传递风格

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的方法。通常情况下，你使用continuation从函数返回，为什么最好命名为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. 更新每一步的延续。

但无论如何，你的功能是一个有趣的解决方案。 aIndeed，你正在使用的是建立一个懒惰的关闭列表。在计算的每一步中，都会创建一个闭包，它使用前一个闭包并将其乘以n。当你达到0时，你称之为封闭链。所以，这是一个O（n）的空间，但不是堆栈，而是使用堆。当然，我的解决方案是O（n）在太空中。我只是澄清。