-
13-10-2019 - |
题
延续传递风格(CPS)和单调之间有什么区别。
解决方案
如前所述 功能编程的本质:
带有单调的编程强烈让人联想到延续 - 超越风格(CPS),本文探讨了两者之间的关系。从某种意义上说,它们是等效的:CPS作为单子的特殊情况出现,任何单子可以通过更改答案类型将CP嵌入CPS中。但是,Monadic方法提供了更多的见识,并允许更优质的控制程度。
该论文非常严格,实际上它并没有完全扩展CPS和Monads之间的关系。在这里,我试图举一个非正式但说明性的例子:
(注意:下面是对新手(我自己)的单调的理解,尽管在写作后,它看起来确实像是那些高级用户的答案之一。请用一吨盐来服用)
考虑经典 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的功能。我们正在使用所有 Int
在这里而不是代数数据类型,以使其更容易:
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的值时,必须停止任何计算 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
单子!
现在,如果我们看 续的源代码, ,我们看到 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为呼叫者提供了更多的控制,通常 >>=
在单子中,由单子作者完全控制。
其他提示
探索问题的有趣论文是 “命令式编程”, ,佩顿·琼斯(Peyton Jones)和沃德勒(Wadler)。
这是引入Monadic IO的论文,并与包括CPS在内的替代方法进行了比较。
作者得出结论:
因此,单调比连续性更强大,但这仅仅是因为类型!目前尚不清楚这是否只是Hindley-Milner类型系统的工件,还是类型是否揭示了基本重要性的差异(我们自己的直觉是后者 - 但这只是直觉。)
没有关系,因此问题与询问颜色蓝色和冥王星之间的差异一样有意义。