延续传递风格(cps)和单子有什么区别。
4 回答
正如函数式编程的本质中提到的:
使用 monad 进行编程很容易让人联想到 continuation-passing style (CPS),本文探讨了两者之间的关系。在某种意义上它们是等价的:CPS 是作为 monad 的一种特殊情况出现的,任何 monad 都可以通过改变答案类型嵌入到 CPS 中。但是一元方法提供了额外的洞察力并允许更精细的控制。
那篇论文相当严谨,实际上它并没有完全扩展 CPS 和 monad 之间的关系。在这里,我试图给出一个非正式但说明性的例子:
(注意:下面是一个新手(我自己)对 Monad 的理解,虽然在写完之后它看起来确实像是那些高代表用户的答案之一。请用大量的盐来接受它)
考虑经典的Maybe
单子
-- 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 来模拟这种单子行为:
add
这是我们使用 CPS的 vanilla函数。我们在Int
这里使用 all 而不是代数数据类型以使其更容易:
add :: Int -> Int -> (Int -> Int) -> Int
add x y k = k (x+y)
GHCi> add 3 4 id
7
注意它与单子有多么相似
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
,但这很好,因为评估在第 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
哇!也许我们刚刚发明了Cap10
单子!
现在,如果我们查看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 的作者控制。
一篇探讨这个问题的有趣论文是Peyton Jones 和 Wadler 的“命令式函数式编程”。
这是介绍 monadic IO 的论文,它与包括 CPS 在内的替代方法进行了比较。
作者得出结论:
所以单子比延续更强大,但这仅仅是因为类型!目前尚不清楚这是否只是 Hindley-Milner 类型系统的产物,或者这些类型是否揭示了根本重要性的差异(我们自己的直觉是后者——但这只是一种直觉。)
没有关系,因此这个问题与询问蓝色和冥王星之间的区别一样有意义。