Haskell：在连续传递风格中完全定义阶乘的问题

Question

我一直试图在一大堆内容中理解函数式编程、Haskell 和延续传递风格，而我的结构化/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 模式，但我想我需要花点时间来解释它们。我发现如果你考虑带有基本情况和归纳步骤的数学归纳法，就更容易理解。基本情况是事实 0 ...。然后，您可以从基本步骤开始定义其他值：“对于任何fact n k，通过此关系确定fact (n+1) k”。这与我对正常模式变量的看法不同，即自上而下而不是像这里一样自下而上，但我认为它解释了动机以及为什么有些人喜欢这种风格。

我不喜欢 n+k 模式的原因只是因为我发现定义更混乱，但是 YMMV。