起因

学习 CPS 实现过程中对单子的思考。

说明

ConT 主要的优点在于可以传递计算结果,和 monad 下用 lambda 传递不同,这个传递是可以中断的。因为单子约束的类似是 Cont ra 每次计算输入的值,也就是上一次计算的结果值,对最后一层则就是输出的结果,而中间传递的是最后做为输出时计算的最后一步。

相对 readerstate 单子约束的是中间过程传递的环境和状态,但返回值是可变的。因为这个特性,所以 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。换句话说,在 Conta 虽然是输入参数,但同时也会传递过程中的返回值(当然的吧,单子本来就是把上层输出,做为下层输入)。现在问题就在于单子里的 r 是什么了。其实很简单,r(更准确来说是 a -> r)的这个操作 runCont 时输入,类似于 State 里的初始状态和 Reader 里的环境。不同于这两个,这个操作是最后调用的,也就是最后一步对输入如何操作(即对最后的输出再做一步)。因此 idreturn 情况就等于最后一步已经做过了,直接处理成返回值就行。同时也因为有这么一个反复做为参数,所以才能传递下去。定义因为 lambda 表达式的原因看起来有点误解,但下层的 c 是做为最后的参数给上层的 runCont 的。因此构建和 bind 过程需要反复解与包。即把 a -> r,b -> r, c -> r 变成了一个 c -> r 的函数,其中 c 通过 a -> bb -> c 得来。换一种表达,就是单子最开始的 Cont r a 被组合到 Cont r b,再到 Cont r c,最后变换成了 Cont r z。最终结果由这个 z -> r 来得出。

不同于直觉,组合操作把后续的操作包在了上层的外面,因此最早的计算其实是 lambda 的在最里层,而最晚的计算在 lambda 的最外层。而直觉上,单子定义则是先计算的就在外层,后计算的就在里层,最后把最里层的结果一层层返回给外层 (m a -> (a -> b) -> m b)。当然,Cont 这个也是单子,也合这个逻辑,只是有点不太适合我的思考惯性。

计算顺序

更进一步,函数式传递就有两种方式了,一种是把里层函数的值做为外层函数的值来返回,以此来把最里层的计算做为最终结果,如 f = let a; b; c; in f' a b c。第二种是外层是最终的计算,但这个计算是会高度依赖里层计算的结果,如 f = let a = f1 x; b = f2 x; c = f3 x; in fold。也就是前者是先做当前层的计算,拿结果传递给里层来计算结果返回;后者是先返回子计算的值,再来计算这一层的值返回。