延续传递风格与 monad 的比较

Question

连续传递风格 (cps) 和 monad 之间有什么区别。

Answer 1

正如函数式编程的本质中提到的：

使用 monad 编程很容易让人想起延续传递风格 (CPS)，本文探讨了两者之间的关系。从某种意义上来说，它们是等价的：CPS 作为 monad 的一个特例出现，任何 monad 都可以通过改变答案类型嵌入到 CPS 中。但一元方法提供了额外的洞察力并允许更精细的控制。

这篇论文相当严谨，实际上并没有很好地阐述 CPS 和 monad 之间的关系。在这里，我尝试给出一个非正式但说明性的例子：（

注意：下面是一个新手（我自己）对 Monad 的理解，尽管写完后它看起来确实像那些高代表用户的答案之一。请这样做 考虑一下

经典的 Maybe monad

-- I don't use the do notation to make it 
-- look similar to foo below

bar :: Maybe Int
bar =
    Just 5 >>= \x ->
    Just 4 >>= \y ->
    return $ x + y

bar' :: Maybe Int
bar' =
    Just 5 >>= \x ->
    Nothing >>= \_ ->
    return $ x

GHCi> bar
Just 9
GHCi> bar'
Nothing

因此，一旦遇到 Nothing ，计算就会停止，这里没有什么新内容。让我们尝试使用 CPS 来模拟这样的单子行为：

这是我们使用 CPS 的普通 add 函数。我们在这里使用所有 Int 而不是代数数据类型，以使其更容易：

add :: Int -> Int -> (Int -> Int) -> Int
add x y k = k (x+y)

GHCi> add 3 4 id
7

注意它与 monad

foo :: Int
foo =
    add 1 2 $ \x -> -- 3
    add x 4 $ \y -> -- 7
    add y 5 $ \z -> -- 12
    z

GHCi> foo
12

OK 多么相似。假设我们希望计算上限为 10。也就是说，当下一步结果大于 10 时，任何计算都必须停止。这有点像说“Maybe 计算必须停止并返回 Nothing” 只要链中的任何值都是 Nothing），让我们看看如何通过编写“CPS 转换器”来做到这一点。

cap10 :: (Int -> Int) -> (Int -> Int)
cap10 k = \x ->
    if x <= 10 
    then 
        let x' = k x in 
        if x' <= 10 then x' else x
    else x

foo' :: Int
foo' =
    add 1 2 $ cap10 $ \x -> -- 3
    add x 4 $ cap10 $ \y -> -- 7
    add y 5 $ cap10 $ \z -> -- 12
    undefined

GHCi> foo'
7

请注意，最终返回值可能是 undefined< /code>，但这很好，因为评估在第三步停止（z）。

我们可以看到 cap10 用一些额外的逻辑“包装”了正常的延续。这与 monad 的作用非常接近——将计算与一些额外的逻辑结合在一起

：

(>>==) :: ((Int -> Int) -> Int) -> (Int -> Int) -> Int
m >>== k = m $ cap10 k

foo'' :: Int
foo'' =
    add 1 2 >>== \x -> -- 3
    add x 4 >>== \y -> -- 7
    add y 5 >>== \z -> -- 12
    undefined

GCHi> foo''
7

刚刚发明了 Cap10 monad！

哇！也许我们 a href="https://google.com/codesearch#A3NG3tctuIg/core/libraries/mtl/Control/Monad/Cont.hs&q=package%3aghc%20Cont">Cont的源代码，我们看到Cont 是

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

runCont 的类型，

Cont r a -> (a -> r) -> r
((a -> r) -> r) -> (a -> r) -> r

它与我们的 >>== 的类型非常吻合

现在来实际回答这个问题

现在，在输入所有这些内容后，我重新阅读了原来的问题。 OP 要求“差异”：P

我猜差异是 CPS 为调用者提供了更多控制权，而通常 monad 中的 >>= 完全由 monad 的作者控制。

Answer 2

您可能想看看这个 http://blog.sigfpe.com/2008 /12/mother-of-all-monads.html

Answer 3

探讨这个问题的一篇有趣的论文是 “命令式函数编程”，作者：Peyton Jones 和 Wadler。

该论文介绍了单子 IO，并且与包括 CPS 在内的其他方法进行了比较。

作者得出结论：

所以单子比延续更强大，但这只是因为类型！目前尚不清楚这是否只是 Hindley-Milner 类型系统的一个产物，或者这些类型是否揭示了根本重要性的差异（我们自己的直觉是后者 - 但这只是一种直觉。）

Answer 4

没有任何关系，因此这个问题与询问蓝色和冥王星之间的差异一样有意义。