CPS & Y-combinator

周末看了一篇"The Evolution of a Haskell Programmer"，里面列举了Haskell程序员写阶乘函数fac的各种实现方法，可以用两个成语来形容：琳琅满目、叹为观止。虽然感觉上有点类似孔乙己在纠缠茴香豆的茴字有几种写法，不过内容还真的挺有意思。其中有两个实现方法可以稍微聊一聊：1. CPS；2.利用Y combinator。

1. CPS - Continuation-passing style
   CPS是Gerald Jay Sussman和Guy L. Steele在1975年创建Scheme语言时提出的，其大意是处理的结果并不是像平时习惯的那样直接给出，而是给出一个临时结果。比如，写parser时，假设输入很复杂，我们不必一下给出解析的结果，而是步步为营。我们可以写出许多很简单，容易测试的小parser，比如parseNumber, parseString, 等等。每一步尝试一种解析，直到剩下的输入都不能被解析的为止。下面是个CPS风格的fac函数：
   > facCps k 0 = k 1
   > facCps k n = facCps (k . (n*)) (n - 1)
   > fac = facCps id
   
   
   
   • `.'在Haskell中是个函数组合算子，比如f (g x) = (f . g) x
   
   
   • (*) 在Haskell中是个函数，有两个参数，求得乘积。(n*)也是个函数，只有一个参数，如果给定m，则返回n*m -- 这叫做currying，Haskell中所有函数都是currying的。
   
   
   • 函数id直接返回输入参数本身，比如id 3 = 3, id fac = fac
   
   
   
   


2. Y combinator
   Y combinator是递归函数理论中的重要概念，说它是计算机科学的奠基性基础理论也不为过 -- MIT的计算机科学系的系徽就是它。它的数学形式是Y(f )= f (Y (f))，也就是说给定一个函数f，Y会求出该函数的不动点。有很多教程教你怎样一步步推导出Y函数，然而在Haskell中几乎直接原样照搬就行：
   > y f = f (y f)
   > fac = y (\f n -> if  n == 0 then 1 else n * f (n-1))
   
   
   
   • Haskell是lazy的，所以上面的递归定义没问题；
   
   
   • Haskell中函数名不能用大写字母开头，大写字母开头的是类名，类型名及其构造方法。
   
   
   
   

我以上帝的名义发誓，昨天我人品爆发居然写了个求平方根函数sqr = y (\f x -> x / f x)，因为y = x/y的不动点y'就是x的平方根，我敲了个sqr 3，居然得到1.732050... 精确到小数点后十几位 -- 后来不能重现，每次都stack overflow -- 而用稍微瞄一眼就知道这是应该的，因为这次没有递归结束条件，会无穷无尽递归下去。我确信没有误敲sqrt，从而调用了系统内置的平方根函数。莫非那是上帝开的小玩笑？:-)