起因 Link to heading
学习 CPS 实现过程中对单子的思考。
说明 Link to heading
ConT 主要的优点在于可以传递计算结果,和 monad 下用 lambda 传递不同,这个传递是可以中断的。因为单子约束的类似是 Cont r
,a
每次计算输入的值,也就是上一次计算的结果值,对最后一层则就是输出的结果,而中间传递的是最后做为输出时计算的最后一步。
相对 reader
和 state
单子约束的是中间过程传递的环境和状态,但返回值是可变的。因为这个特性,所以 Cont
的最后实际上是一个接收一个参数的函数,而这个函数是最后才会被触发的,比如 evalCont
用的 return
(这里 return
并不是对 Cont r a
的,而是 r
。因为这个 return
是传递做为 a -> r
来用的),或是 haskell wikibook 里用的 id
就是直接返回上一层的结果。刚刚说的传递可以中断也是使用这个特性,把后续的函数变成一个不匹配参数就可以把再后续全部打断了(返回一个 Cont r a
,但其中 a -> r
是 \_ -> c r
,类似于 const r
)。callCC
就是这样一个功能的包装,它把这样一个函数做为参数传起来,由我们 call 一下就会可以中断了(返回了 Cont $ \_ -> c r
)。可以这样做的另外一个原因也和 ConT 的构建方式有关,((a -> r) -> r)
中,这个函数是是上一计算后所要求这一次计算的输入,并且可以再接收一个函数把内容传递下去,多层连锁的操作也是基于这个行为做的,在单子中来做这个操作,而计算操作则是在 a -> Cont r b
里,即单子里的 f
。换句话说,在 Cont
里 a
虽然是输入参数,但同时也会传递过程中的返回值(当然的吧,单子本来就是把上层输出,做为下层输入)。现在问题就在于单子里的 r
是什么了。其实很简单,r
(更准确来说是 a -> r
)的这个操作 runCont
时输入,类似于 State
里的初始状态和 Reader
里的环境。不同于这两个,这个操作是最后调用的,也就是最后一步对输入如何操作(即对最后的输出再做一步)。因此 id
或 return
情况就等于最后一步已经做过了,直接处理成返回值就行。同时也因为有这么一个反复做为参数,所以才能传递下去。定义因为 lambda 表达式的原因看起来有点误解,但下层的 c
是做为最后的参数给上层的 runCont
的。因此构建和 bind 过程需要反复解与包。即把 a -> r,b -> r, c -> r
变成了一个 c -> r
的函数,其中 c
通过 a -> b
与 b -> c
得来。换一种表达,就是单子最开始的 Cont r a
被组合到 Cont r b
,再到 Cont r c
,最后变换成了 Cont r z
。最终结果由这个 z -> r
来得出。
不同于直觉,组合操作把后续的操作包在了上层的外面,因此最早的计算其实是 lambda 的在最里层,而最晚的计算在 lambda 的最外层。而直觉上,单子定义则是先计算的就在外层,后计算的就在里层,最后把最里层的结果一层层返回给外层 (m a -> (a -> b) -> m b
)。当然,Cont
这个也是单子,也合这个逻辑,只是有点不太适合我的思考惯性。
计算顺序 Link to heading
更进一步,函数式传递就有两种方式了,一种是把里层函数的值做为外层函数的值来返回,以此来把最里层的计算做为最终结果,如 f = let a; b; c; in f' a b c
。第二种是外层是最终的计算,但这个计算是会高度依赖里层计算的结果,如 f = let a = f1 x; b = f2 x; c = f3 x; in fold
。也就是前者是先做当前层的计算,拿结果传递给里层来计算结果返回;后者是先返回子计算的值,再来计算这一层的值返回。