使用延續傳遞風格

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）在太空中。我只是澄清。