Haskell：在繼續傳遞樣式中完全定義階乘的問題

Question

我一直在試圖解釋函數編程，Haskell和Continuation傳遞樣式在一個大的blob和我的結構化/ OOP背景給我一個很難。

根據this我瞭解以下應該是階乘的CPS風格的一個正確的定義：

factorial n = fact n id where id = \x -> x 
    fact 0 cont = cont n 
    fact (n+1) cont = fact n * (n + 1) 

，但我不知道有關「*（N + 1）」的結尾部分- 那是對的嗎？

Answer 1

這是不正確的（並不爲我編譯）;價值n+1是正確的，但它不是以正確的方式使用。也許你打算使用操作員部分？

factorial n' = fact n' id 
where 
    id = \x -> x 
    fact 0 cont = cont 1 
    fact (n+1) cont = fact n (cont . (* (n+1))) 

這是相同的（但比更鈍）以下

factorial n' = fact n' id 
where 
    id = \x -> x 
    fact 0 cont = cont 1 
    fact (n+1) cont = fact n (\ret -> cont (ret * (n+1))) 

有幾件事我會在這裏改變。首先，id是一個標準函數，所以你不需要重新定義它。其次，這些例子使用「n + k模式」，其中IIRC在GHC中默認不再可用。您可以使用正常模式變量，而不是「n + k模式」。請注意，我使用1作爲基本案例;這是簡單的推理，如果你從n倒計時，並延續功能應在計算中的每一步（你把它丟在感應步驟）被應用。考慮到這些，你可以寫

factorial n' = fact n' id 
where 
    fact 0 cont = cont 1 
    fact n cont = fact (n-1) (cont . (* n)) 

我會考慮或多或少地道。

編輯：我個人不喜歡n + k模式，但我想我會花一點時間來解釋它們。如果你想到一個基礎案例和一個歸納步驟的數學歸納法，我發現它更容易遵循。基本案例是fact 0 ...。然後通過從基本步驟繼續定義其他值：「對於任何fact n k，通過此關係確定fact (n+1) k」。這是我怎麼想的正常模式變量的不同，那是自上而下，而不是自下而上這裏，但我認爲它解釋的動機，爲什麼有些人喜歡的風格。

我不喜歡N + K模式的原因很簡單，因爲我覺得定義比較凌亂，但情況因人而異。