初探Y Combinator
算法 

以前逛技术社区的时候偶尔会看到一些比较炫酷的Y Combinator,觉得挺神奇的,比如说能够不用递归和循环实现阶乘函数等一些以往需要递归实现的算法。但是毫无基础完全看不懂源码。今天终于明白了它的原理。

函数式编程基础

首先,我们需要一些了解一下函数式变成的基础概念:

lambda 演算(Calculus)

lambda又写作希腊字母\(λ\),lambda演算的基本形式是λ变量. 函数体其实就相当于JS中的变量 => 函数体。lambda演算需要注意的有亮点:

  1. 函数也能够作为参数传入另外一个函数。(函数也是一等公民)
  2. lambda演算是匿名的,无法赋值(define),因此传统递归写法是不能实现的。
  3. lambda演算只有一个参数,需要多个参数的时候只能嵌套。比如: (x,y) => x+y应当写成x => y => x+y(函数柯里化)。

α-转换(α-conversion)

alpha转换是一个重命名操作,意思是变量名不影响函数含义。很容易理解,比如:

λx . if (= x 0) then 1 else x ^ 2 

等价于

λy . if (= y 0) then 1 else y ^ 2 

β归约(β-reduction)

beta规约的意思是你可以将传入的参数应用到函数中去。表达比较抽象,但是实际上很好理解,比如:

(λy . (λx . x + y)) q

我们可以将传入参数带入到函数中,返回一个新的函数:

λx . x + q 

上面两个表达式其实实等价的。beta规约其实就是一个代入操作。

η-转换(η-conversion)

eta转化的意思是如果两个函数对于所有相同的传入的参数都能得到一样的结果,则两个函数相等。

YCombinator

YCombinator的最终形式如下:

$$λf.(λx.f(x x))(λx.f(x x))$$

那么这个表达式究竟怎么来的呢,下面以求阶乘为例来尝试推导一下:

首先,一个普通的求阶乘的递归写法如下:

fact = n => n == 1? 1 : n * fact(n-1)

很简单明了,对吧?但是在lambda演算过程中,我们没法给函数命名的,因此在函数执行过程中,我们访问不到fact这个值

fact = n => n == 1? 1 : n * ???(n-1)

访问不到的话,怎么办呢? 那把原函数通过参数传进来吧:

fact = f => n => 1? 1: n * f(f)(n-1)

所以现在我们只需要把函数自身fact作为参数f穿进去我们就可以得到一个正确的求阶乘函数了:

fact(fact)

用函数本体替换掉函数名(lambda演算中不允许存在函数名):

Y = (f => n => n ==1? 1 : n * f(f)(n-1))(f => n =>n == 1? 1 : n * f(f)(n-1))

上面得到一个可以运行的函数,我们暂且称它为Y,那么我们可以使用Y来计算5的阶乘了:

Y(5)
// (f => n => n == 1? 1 : n * f(f)(n-1))(f => n =>n == 1? 1 : n * f(f)(n-1))(5)

完美,所以这就是Y组合子了吧?并不是,这个式子虽然正确,但是缺乏一般情况下的抽象性,我们称它为: 穷人的Y组合子

所以我们还需继续将式子进行变化,看看能不能找出更为普遍的规律:

首先为了简化推导过程,我们设置一个w函数并将它带入到之前的式子中:

w = f = f(f)
w(fact)
w(f => n => n == 1? 1 : n * f(f)(n-1))

由于lambda演算内部不能使用函数名,因此我们需要将上面式子里面的f(f)提取出来: 将f(f)当作参数g提取出去(逆向beta规约)

w(f => (g => n => n == 1? 1 : n *g(n-1))(f(f)))

可以看到中间括号内的g => n => n == 1? 1 : n * g(n-1)就是我们需要的阶乘函数原型(g代表函数本身),因此我们继续逆向beta规约将它作为参数提取出来:

w((s => f => s(f(f)))(g => n => n==1? 1 : n * g(n-1)))

应用逆向beta规约将函数原型继续提取到w函数外测:

(h => w( (s => f => s(f(f)))(h) ) )(g => n => n == 1? 1 : n * g(n-1))

ok,函数原型前面就是大名鼎鼎的Y Combinator了。即:

h => w( (s => f => s(f(f))) (h) )
//应用beta规约,等价于
h => w( (f => h(f(f))) )
//去掉w函数
h => ( f => h(f(f)) )( f => h(f(f)) )
// alpha转换:
f => ( x => f(x(x)) )( x => f(x(x)) )

上述表达式即之前所说的Y Combinator最终形式:

$$λf.(λx.f(x x))(λx.f(x x))$$

大功告成,但是值得注意的是在js中(不支持Lazy求值)上述表达式会造成死循环。只要应用eta变化一下即可:

f => ( x => f( v => x(x)(v) ))( x => f( v => x(x)(v) ))