functional-programming - 延续传球风格与单子(monad)

Question

延续传递风格(cps)和单子(monad)有什么区别。

Answer 1

如 The essence of functional programming 中所述:

Programming with monads strongly reminiscent of continuation—passing style (CPS), and this paper explores the relationship between the two. In a sense they are equivalent: CPS arises as a special case of a monad, and any monad may be embedded in CPS by changing the answer type. But the monadic approach provides additional insight and allows a finer degree of control.

那篇论文相当严谨，实际上它并没有完全扩展 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 来模拟这种单子(monad)行为:

这是我们的 Vanilla add使用 CPS 的功能。我们正在使用所有 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

好的。假设我们希望计算上限为 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 ，但这很好，因为评估在第三步(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)!

现在，如果我们查看 source code of 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 为调用者提供了更多控制权，通常是 >>= in a monad 完全由 monad 的作者控制。