2

我一直试图在一个大块中理解函数式编程、Haskell 和延续传递风格，而我的结构化/OOP 背景让我很难过。

据此，我理解以下应该是 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）”部分 - 这是正确的吗？

4

1 回答 1

6

这不太正确（并且不适合我）；该值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 模式的原因仅仅是因为我发现定义更混乱，但是 YMMV.

于 2011-01-23T14:16:38.253 回答