Y组合子

Y组合子（Y Combinator），是在无类型Lambda演算中计算其他函数的一个不动点的高阶函数。

对于Y组合子来说，我们有[math]\displaystyle{ \textsf{Y}\ f = f }[/math]。使得对于任何函数都有[math]\displaystyle{ \textsf{Y}\ f = f\ (\textsf{Y}\ f) }[/math]

定义

通常我们使用Lambda将Y组合子定义为[math]\displaystyle{ \textsf{Y} = \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)) }[/math]

证明

[math]\displaystyle{ (\textsf{Y}\ g) }[/math]

[math]\displaystyle{ = (\lambda f.(\lambda x.(f (x\ x))\ \lambda x.(f\ (x\ x)))\ g) }[/math]

[math]\displaystyle{ = (\lambda x.(g\ (x\ x))\ \lambda x.(g\ (x\ x))) }[/math]

[math]\displaystyle{ = (\lambda y.(g\ (y\ y))\ \lambda x.(g\ (x\ x))) }[/math]

[math]\displaystyle{ = (g\ (\lambda x.(g\ (x\ x))\ \lambda x.(g\ (x\ x)))) }[/math]

[math]\displaystyle{ = (g\ (\textsf{Y}\ g)) }[/math]

实现

在实际中也可以顺利的实现它，比如编程语言Scheme：

(define Y
  (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y))))
    (lambda (x) (f (lambda (y) ((x x) y)))))))

用处

用来实现递归

编程

我们还是用语言Scheme为例子，实现一个阶乘

正常情况下我们可以给函数命名来实现：

(define f (lambda (n) (cond ((= n 0) 1)
                            (else (* n (f (- n 1)))))))
(print (f 10))

但是在函数不能被命名的情况下，就用到了Y组合子：

(define Y
  (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y))))
    (lambda (x) (f (lambda (y) ((x x) y)))))))
(print ((Y (lambda (f) (lambda (n) (cond ((= n 0) 1)
                            (else (* n (f (- n 1)))))))) 10))

或者：

(print (((lambda (f) ((lambda (x) (f (lambda (y) ((x x) y))))
    (lambda (x) (f (lambda (y) ((x x) y)))))) (lambda (f) (lambda (n) (cond ((= n 0) 1)
                            (else (* n (f (- n 1)))))))) 10))

Lambda

Lambda是匿名函数，Y组合子是为了解决递归时不能用名称指代原始函数的问题的。