Haskell:在Continuation Passing Style中完全定义阶乘的问题

Question

我一直试图在一个大blob中强调功能编程,Haskell和Continuation Passing Style,而我的结构化/ 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)"部分 - 这是正确的吗？

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模式",在GHC中默认不再提供IIRC.您可以使用普通模式变量代替"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.