继续传球风格vs monads

Question

连续传递样式(cps)和monad之间有什么区别.

Answer 1

如功能编程的本质所述:

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

那篇论文非常严谨,实际上并没有完全扩展CPS和monad之间的关系.在这里,我试图给出一个非正式的,但说明性的例子:

(注意:以下是对新手(我自己)的Monad的理解,虽然在写完之后看起来看起来像是那些高代表用户的答案之一.请大量拿盐)

考虑一下经典的Maybemonad

-- 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模仿这种monadic行为:

这是我们add使用CPS 的香草功能.我们在Int这里使用all 而不是algebric数据类型来使它更容易:

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时,任何计算都必须停止.这有点像说"一个可能计算必须停止并且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,但这很好,因为评估在第3步(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

WOA!也许我们刚刚发明了Cap10monad!

现在,如果我们看看续的源代码,我们可以看到,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完全由monad的作者控制.

Answer 2

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

Answer 3

一篇探讨该问题的有趣论文是Peyton Jones 和 Wadler 撰写的“命令式函数式编程”。

这篇论文介绍了 monadic IO，并与其他方法（包括 CPS）进行了比较。

作者得出结论：

所以 monad 比 continuation 更强大，但仅仅是因为类型！目前尚不清楚这是否只是 Hindley-Milner 类型系统的人工制品，或者这些类型是否揭示了根本重要性的差异（我们自己的直觉是后者——但这只是一种直觉。）