CPS之2

上一篇总结了一下CPS，感觉还是不够理解，于是继续看wiki book，加深一下体会。

先定义一些缩略语：
CPS: continuation passing style
TR:  tail recursion
TC:  tail call
TCO: tail call optimization

先看一个普通的递归是如何变成 TR 的。

例如一个求和函数：

sum [] = 0
sum (x:xs) = x + (sum xs)

它并不是 TR，因为它的最后一步是 + 。
为了变成 TR，我们可以增加一个自变量来保存结果：

sum' res [] = res
sum' res (x:xs) = sum' (res+x) xs
sum list = sum' 0 list

很不错吧？这样就能保证让编译器进行 TCO 了。
这个trick 被滥用和推广以后——可以增加自变量，当然也能增加函数——就变成了 CPS。

so we get：

这首歌真的很 hot，演唱会上面那个 mm 也很 hot……

练手：先将一个简简单单的函数改成 CPS。

-- origin
f x = ((x + 1) * 2 - 3) * 4
-- cps
f1 x cc = cc (x + 1)
f2 x cc = cc (x * 2)
f3 x cc = cc (x - 3)
f4 x cc = cc (x + 4)
f' x cc = f1 x (\x cc -> f2 x (\x cc -> f3 x (\x cc -> f4 x cc)))
f'cps x = f' x (\x -> x)

感觉良好…… haskell 有专门语法杀括号：（其实还是很难看）

f''cps x = f1 x $
  \x -> f2 x $
  \x -> f3 x $
  \x -> f4 x $
  print

最后一步传一个print，便是打印结果，so sweet~

非常有趣：这个语法糖差不多就是后缀表达式了……

话说CPS一个很经典的用法或许是左右折叠的互换？有没有读之前发你那个F#文件，里面有用fold_right实现的fold_left，以及反过来用fold_left实现的fold_right；其它很多表函数都可以用fold来实现，所以也对应的可以应用CPS。
像LINQ里的Fold就只有左折叠，但通过CPS可以变成右折叠来用。

嗯…… 因为递归可以用 foldr 表示，所以任何东西，包括 foldl 都可以用 foldr 表示……

高阶函数的确很强大