这就是 Cont monad 的定义方式:
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
instance Monad (Cont r) where
return a = Cont ($ a)
m >>= k = Cont $ \c -> runCont m $ \a -> runCont (k a) c
你能解释一下它是如何以及为什么起作用的吗?它在做什么?
这就是 Cont monad 的定义方式:
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
instance Monad (Cont r) where
return a = Cont ($ a)
m >>= k = Cont $ \c -> runCont m $ \a -> runCont (k a) c
你能解释一下它是如何以及为什么起作用的吗?它在做什么?
关于 continuation monad,首先要意识到的是,从根本上说,它根本没有真正做任何事情。这是真的!
一般来说,延续的基本思想是它代表计算的其余部分。假设我们有这样的表达式:foo (bar x y) z
. 现在,只提取带括号的部分,bar x y
--这是整个表达式的一部分,但它不仅仅是我们可以应用的函数。相反,我们需要将函数应用于. 因此,在这种情况下,我们可以将“剩余的计算”称为存在\a -> foo a z
,我们可以将其bar x y
应用于重构完整的形式。
现在,碰巧这个“计算的其余部分”的概念很有用,但使用起来很尴尬,因为它超出了我们正在考虑的子表达式。为了让事情更好地工作,我们可以把事情从里到外:提取我们感兴趣的子表达式,然后将它包装在一个函数中,该函数接受一个表示其余计算的参数:\k -> k (bar x y)
.
这个修改后的版本给了我们很大的灵活性——它不仅从它的上下文中提取一个子表达式,而且它允许我们在子表达式本身内操作那个外部上下文。我们可以将其视为一种暂停计算,让我们明确控制接下来会发生什么。现在,我们如何概括这一点?好吧,子表达式几乎没有变化,所以让我们将它替换为由内向外函数的参数,给我们\x k -> k x
- 换句话说,无非是函数应用程序, reversed。我们可以很容易地编写flip ($)
或添加一点异国情调的外语风味并将其定义为运算符|>
。
现在,将表达式的每一个片段都翻译成这种形式会很简单,尽管很乏味而且非常令人困惑。幸运的是,有更好的方法。作为 Haskell 程序员,当我们考虑在后台上下文中构建计算时,我们认为接下来会说,这是一个 monad 吗?在这种情况下,答案是肯定的,是的。
为了把它变成一个 monad,我们从两个基本的构建块开始:
m
,类型的值表示可以在 monad 的上下文中m a
访问类型的值。a
在这种情况下可以访问某种类型的东西意味着什么a
?这只是意味着,对于某些值x :: a
,我们已经应用flip ($)
到x
,给了我们一个函数,该函数接受一个接受类型参数的函数a
,并将该函数应用于x
. 假设我们有一个挂起的计算持有一个 type 的值Bool
。这给了我们什么类型的?
> :t flip ($) True
flip ($) True :: (Bool -> b) -> b
所以对于挂起的计算,类型的m a
结果是(a -> b) -> b
......这可能是一个反高潮,因为我们已经知道 的签名Cont
,但现在请幽默。
这里要注意的一件有趣的事情是,一种“反转”也适用于 monad 的类型:Cont b a
表示一个函数,该函数接受一个函数a -> b
并计算为b
. 由于延续代表计算的“未来”,因此a
签名中的类型在某种意义上代表“过去”。
那么,替换(a -> b) -> b
为Cont b a
,我们的反向函数应用程序的基本构建块的一元类型是什么?a -> (a -> b) -> b
转换为a -> Cont b a
...相同的类型签名return
,事实上,这正是它的本质。
从现在开始,几乎所有内容都直接从类型中分离出来:>>=
除了实际实现之外,基本上没有明智的实现方式。但它实际上在做什么?
在这一点上,我们回到我最初所说的:continuation monad 并没有真正做任何事情。简单地通过将作为参数提供给挂起的计算来Cont r a
简单地等价于type的某些东西。这可能会导致人们问,如果是一个 monad 但转换是如此微不足道,那么是否不应该单独也是一个 monad?当然这不能按原样工作,因为没有类型构造函数可以定义为实例,但是假设我们添加了一个简单的包装器,比如. 这确实是一个单子,即身份单子。a
id
Cont r a
a
Monad
data Id a = Id a
身份单子有什么作用>>=
?类型签名是Id a -> (a -> Id b) -> Id b
,相当于a -> (a -> b) -> b
,又是简单的函数应用。确定了 与Cont r a
的简单等价后Id a
,我们可以推断在这种情况下,(>>=)
也只是函数应用程序。
当然,Cont r a
这是一个疯狂的倒置世界,每个人都有山羊胡子,所以实际发生的事情涉及以令人困惑的方式将事物洗牌,以便将两个暂停的计算链接在一起成为一个新的暂停计算,但本质上,实际上并没有什么不寻常的事情发生上!将函数应用于参数,哼哼,又是函数式程序员生活中的一天。
这是斐波那契:
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
想象一下,你有一台没有调用堆栈的机器——它只允许尾递归。如何fib
在那台机器上执行?您可以轻松地将函数重写为线性工作,而不是指数时间,但这需要一点点洞察力并且不是机械的。
使其尾递归的障碍是第三行,其中有两个递归调用。我们只能打一个电话,这也必须给出结果。这是延续进入的地方。
我们将fib (n-1)
使用附加参数,该参数将是一个指定计算结果后应该做什么的函数,调用它x
。当然,它会增加fib (n-2)
它。所以:要计算,然后fib n
计算fib (n-1)
,如果调用 result x
,则计算fib (n-2)
,然后,如果调用 result y
,则返回x+y
。
换句话说,你必须告诉:
如何进行以下计算:“ fib' n c
=计算fib n
并应用于c
结果”?
答案是您执行以下操作:“计算fib (n-1)
并应用于d
结果”,其中d x
表示“计算fib (n-2)
并应用于e
结果”,其中e y
表示c (x+y)
. 在代码中:
fib' 0 c = c 0
fib' 1 c = c 1
fib' n c = fib' (n-1) d
where d x = fib' (n-2) e
where e y = c (x+y)
等效地,我们可以使用 lambda:
fib' 0 = \c -> c 0
fib' 1 = \c -> c 1
fib' n = \c -> fib' (n-1) $ \x ->
fib' (n-2) $ \y ->
c (x+y)
要获得实际的斐波那契使用身份:fib' n id
. 您可以认为该行将fib (n-1) $ ...
其结果传递x
给下一个。
最后三行闻起来像do
块,实际上
fib' 0 = return 0
fib' 1 = return 1
fib' n = do x <- fib' (n-1)
y <- fib' (n-2)
return (x+y)
根据 monad 的定义,直到新类型都是一样的Cont
。注意差异。There's\c ->
在开头,而不是x <- ...
there's... $ \x ->
和c
而不是return
.
尝试factorial n = n * factorial (n-1)
使用 CPS 以尾递归风格编写。
如何>>=
工作?m >>= k
相当于
do a <- m
t <- k a
return t
以与 中相同的样式进行翻译fib'
,您将得到
\c -> m $ \a ->
k a $ \t ->
c t
简化\t -> c t
为c
m >>= k = \c -> m $ \a -> k a c
添加你得到的新类型
m >>= k = Cont $ \c -> runCont m $ \a -> runCont (k a) c
这是在这个页面的顶部。这很复杂,但是如果您知道如何在do
表示法和直接使用之间进行转换,则无需知道 ! 的确切定义>>=
。如果你看一下 do-blocks,继续单子会更清楚。
单子和延续
如果你看一下 list monad 的这种用法......
do x <- [10, 20]
y <- [3,5]
return (x+y)
[10,20] >>= \x ->
[3,5] >>= \y ->
return (x+y)
([10,20] >>=) $ \x ->
([3,5] >>=) $ \y ->
return (x+y)
看起来像继续!实际上,(>>=)
当您应用一个参数时,其类型(a -> m b) -> m b
为Cont (m b) a
. 有关解释,请参阅 sigfpe 的所有单子之母。我认为这是一个很好的 continuation monad 教程,尽管它可能并不意味着它。
由于 continuation 和 monad 在两个方向上都密切相关,我认为适用于 monad 的东西也适用于 continuation:只有努力工作才能教会你它们,而不是阅读一些墨西哥卷饼的隐喻或类比。
编辑:文章迁移到下面的链接。
我已经写了一个直接解决这个主题的教程,我希望你会觉得有用。(它确实有助于巩固我的理解!)它有点太长了,无法舒适地融入 Stack Overflow 主题,所以我将它迁移到了 Haskell Wiki。
请参阅:引擎盖下的 MonadCont
我认为掌握Cont
monad 的最简单方法是了解如何使用它的构造函数。我现在将假设以下定义,尽管transformers
包的实际情况略有不同:
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
这给出了:
Cont :: ((a -> r) -> r) -> Cont r a
所以要构建一个类型的值Cont r a
,我们需要给一个函数Cont
:
value = Cont $ \k -> ...
现在,k
它本身有 type a -> r
,而 lambda 的主体也需要有 type r
。一个显而易见的事情是应用k
一个类型的值a
,并获得一个类型的值r
。我们可以做到这一点,是的,但这只是我们可以做的许多事情之一。请记住,在 中value
不必是多态的r
,它可能是类型Cont String Integer
或其他具体的东西。所以:
k
type 的多个值a
,并以某种方式组合结果。k
到 type 的值a
,观察结果,然后k
根据它决定应用到其他东西。k
,只自己产生一个类型的值r
。但这一切意味着什么?k
最终成为什么?好吧,在一个 do-block 中,我们可能会有这样的东西:
flip runCont id $ do
v <- thing1
thing2 v
x <- Cont $ \k -> ...
thing3 x
thing4
这是有趣的部分:在我们的脑海中,有些非正式地,我们可以在构造函数出现时将 do-block 一分为二,并将其之后Cont
的整个计算的其余部分视为其本身的值。但是等等,它是什么取决于它是什么,所以它实际上是一个从类型值到某个结果值的函数:x
x
a
restOfTheComputation x = do
thing3 x
thing4
事实上,粗略地说,这restOfTheComputation
就是最终的结果。换句话说,您调用一个值,该值成为您的计算结果,其余的计算运行,然后生成的作为调用的结果返回到您的 lambda 。所以:k
k
x
Cont
r
k
k
多次调用,其余的计算将多次运行,并且可以根据您的意愿组合结果。k
,整个计算的其余部分将被跳过,封闭的runCont
调用只会给你返回r
你设法合成的任何类型的值。也就是说,除非计算的其他部分从他们的 调用你,并搞乱结果...... k
如果您此时仍在我身边,应该很容易看出这可能非常强大。为了说明一点,让我们实现一些标准类型类。
instance Functor (Cont r) where
fmap f (Cont c) = Cont $ \k -> ...
我们得到了一个Cont
绑定结果x
为 type的值a
和一个函数f :: a -> b
,我们想要创建一个Cont
绑定结果f x
为 type的值b
。好吧,要设置绑定结果,只需调用k
...
fmap f (Cont c) = Cont $ \k -> k (f ...
等等,我们从哪里来x
?好吧,它将涉及c
我们尚未使用的 。记住它是如何c
工作的:它被赋予一个函数,然后使用它的绑定结果调用该函数。我们想调用我们的函数并f
应用于该绑定结果。所以:
fmap f (Cont c) = Cont $ \k -> c (\x -> k (f x))
多田!接下来,Applicative
:
instance Applicative (Cont r) where
pure x = Cont $ \k -> ...
这个很简单。我们希望绑定结果是x
我们得到的。
pure x = Cont $ \k -> k x
现在,<*>
:
Cont cf <*> Cont cx = Cont $ \k -> ...
这有点棘手,但使用与 fmap 中基本相同的想法:首先从 first 获取函数Cont
,方法是制作一个 lambda 供它调用:
Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ...
然后x
从第二个中获取值,并制作fn x
绑定结果:
Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x)))
Monad
大致相同,尽管需要runCont
或案例或让解包新类型。
这个答案已经很长了,所以我不再赘述ContT
(简而言之:它与 完全一样Cont
!唯一的区别在于类型构造函数的类型,所有内容的实现都是相同的)或callCC
(一个有用的组合器提供了一种方便的忽略方式k
,实现了从子块中提前退出)。
对于一个简单且合理的应用程序,请尝试 Edward Z. Yang 的博客文章实现标记的 break 并在 for 循环中继续。
试图补充其他答案:
嵌套 lambda 的可读性很差。这正是 let... in... 和 ... where ... 存在的原因,通过使用中间变量来摆脱嵌套的 lambda。使用这些,绑定实现可以重构为:
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
instance Monad (Cont r) where
return a = Cont ($ a)
m >>= k = k a
where a = runCont m id
这有望使正在发生的事情更加清晰。带有延迟应用的返回实现框值。使用 runCont id 将 id 应用于装箱值,返回原始值。
对于任何可以简单地拆箱任何装箱值的 monad,通常有一个简单的 bind 实现,即简单地拆箱值并对其应用 monadic 函数。
要获得原始问题中的混淆实现,首先将 ka 替换为 Cont $ runCont (ka) ,然后可以将其替换为 Cont $ \c-> runCont (ka) c
现在,我们可以将 where 移动到子表达式中,这样我们就剩下
Cont $ \c-> ( runCont (k a) c where a = runCont m id )
括号内的表达式可以脱糖为 \a -> runCont (ka) c $ runCont m id。
最后,我们使用 runCont 的属性 f ( runCont mg) = runCont m (fg),我们回到原来的混淆表达式。