2022年2月10日 (四) 03:23 Rmolives

2022-02-10T03:23:24Z

新页面

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

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

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

== 证明 ==
<math>(\textsf{Y}\ g)</math>

<math>= (\lambda f.(\lambda x.(f (x\ x))\ \lambda x.(f\ (x\ x)))\ g)</math>

<math>= (\lambda x.(g\ (x\ x))\ \lambda x.(g\ (x\ x)))</math>

<math>= (\lambda y.(g\ (y\ y))\ \lambda x.(g\ (x\ x)))</math>

<math>= (g\ (\lambda x.(g\ (x\ x))\ \lambda x.(g\ (x\ x))))</math>

<math>= (g\ (\textsf{Y}\ g))</math>

== 实现 ==
在实际中也可以顺利的实现它，比如编程语言'''Scheme'''：
<syntaxhighlight lang="racket" line>
(define Y
(lambda (f) ((lambda (x) (f (lambda (y) ((x x) y))))
(lambda (x) (f (lambda (y) ((x x) y)))))))
</syntaxhighlight>

== 用处 ==
用来实现递归

=== 编程 ===

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

正常情况下我们可以给函数命名来实现：
<syntaxhighlight lang="racket" line>
(define f (lambda (n) (cond ((= n 0) 1)
(else (* n (f (- n 1)))))))
(print (f 10))
</syntaxhighlight>

但是在函数不能被命名的情况下，就用到了Y组合子：
<syntaxhighlight lang="racket" line>
(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))
</syntaxhighlight>
或者：
<syntaxhighlight lang="racket" line>
(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))
</syntaxhighlight>

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

[[Category:计算机]]

Y组合子 - 版本历史

2022年2月10日 (四) 03:23 Rmolives