CPS

终于看完 yaht 第 4 章了，才知道原来类型系统都能玩这么多花样，而且末节 CPS 更体现了函数式编程的精髓。下面一些例子都是源于书中。

CPS 是 Continuation Pass Style 的缩写。而 Continuation 和递归有点关系。

函数的每次 call，都会把调用者的状态压一次栈。直到结尾处，才自己调用自己的函数是尾递归。

一般递归可以 ... 变成只调用自己一次的递归，然后 ... 就变成了尾递归。
——慢着，这马赛克是什么回事？
——因为地方太少写不下，只好用点点代替省掉的 n 行 ╮(╯﹏╰）╭ （群众纷纷扔番茄）
——OK、OK……其实我是这么想的：某天总会有人搜到这篇文章，看见 3 个点，以为是搜索引擎省略的，打开来，才发现这确实是 3 个点……（群众放下番茄，开始扔砖头）

尾递归有什么好处呢？

设 f1， f2 都是 f 的“实例”，f1 在尾部 调用 f2。这里用“shi力”指代它的局部变量和参数蹲在调用栈中、所占用的那个坑。
f1 调 f2 的时候，f1 要拉的都拉完了，所以我们可以将占坑不拉的 f1 赶出来，让 f2 宽衣入坑——满塞！一个坑解决所有问题！此谓之“尾递归优化”。
如此下去，就算递归个几亿重，也不会"坑溢出"（stack overflow）。

可惜的是，由于 ... 的原因，大部分非函数式语言的编译器、运行时不支持尾递归优化，还有实现了又删掉的……（群众继续扔砖头）

幸好我们还有更彻底的方法：把 f1 改头换面，当成 f2 。这种代工拉 shi，把 f1 数据当成 f2 数据的方式 启发了某些大牛 ，终于提出了 Continuation 这个东西。

Continuation 看起来像个循环或者递归，但只有1个“shi力”，而且每次调用只走一步。
中文名？个人以为借用柏格森的 绵延 就很好，也体现了单shi力“如滔滔江水，绵延不绝”的强大……

于是大部分语言都有了自己的“绵延”，以显示生命和灵性所在(柏格森你是个大忽悠……)。这个貌似有状态的东西，数学上应该不能是个函数吧？
嗯，有个温馨的东西(Monad)就是干这个的，但是还有 CPS 可以做这种工作 —— 它是 Style 而非 Type —— 的确是普普通通，来来去去的那道菜 —— 函数。

看看书上的 CPS fold：

cfold' f z [] = z
cfold' f z (x:xs) = f x z (\y -> cfold' f y xs)

我觉得“尾行函数”更加符合道学（Taoist (x:xs) practices），那一撇毛更是可有可无，就改成了：

cfold ::
  [x] ->
  acc ->                                 -- accumulator type
  (x -> acc -> (acc -> acc) -> acc) ->   -- 尾行函数 type
  acc

cfold   []   acc f = acc

--最后两个 acc 可以用 t 或者什么符号代替，但是想个新名字又何苦呢
cfold (x:xs) acc f = f x acc (\acc -> cfold xs acc f)

练习1. 请一口气读完：参数叁是参数叁是函数的叁参数函数的叁参数函数。

这种“超适应齿轮”，可以让我们组装各种新函数，如foldl：

nfoldl :: [x] -> acc -> (x -> acc -> acc) -> acc
nfoldl list acc f = cfold list acc (\x acc g -> f x (g acc))

试试nfoldl：

nfoldl [1,2,3] [] (:)
-- -> [1,2,3]

但直接用才体现了那个……给它指定如何去连接循环它才会循环……

cfold [1..10] [] (\x acc cfold -> cfold (x : acc))
-- -> [10,9,8,7,6,5,4,3,2,1]，先构造表再调用
cfold [1..10] [] (\x acc cfold -> x : (cfold acc))
-- -> [1,2,3,4,5,6,7,8,9,10]，先调用再构造表

2009.4.6 补充：
tangtong 问我为什么体现了“精髓”，我觉得是避免了Monad，使代码看起来更 FP 吧……

最后找个台阶：初学Haskell，很多东西也是一知半解……这个东西还是蛮抽象的
补充： 之所以把 f 放到最后，是因为ruby的习惯，于是这个东西也能很容易的写成ruby

柏格森的绵延是Duration