Y 组合子详解（The Y Combinator）_y组合子

什么是 Y 组合子

Y 组合子（The Y combinator） , discovered by Haskell B. Curry , is defined as:
λf. (λx. f (x x))(λx. f (x x))
用于计算（高阶）函数的不动点，使得lambda演算可以定义匿名递归函数。 
Let’s see that in action: 
X = (λx. f (x x))(λx. f (x x))
X = f (x x) [x := λx. f (x x)]
X = f ((λx. f (x x)) (λx. f (x x)))
X = f X
In functional programming, the Y combinator can be used to formally define recursive functions in a programming language that does not support recursion. 
It turns out that for any λ-expression f, 
(λx. f (x x))(λx. f (x x)) 
is a fixed-point of f. 
lambda 演算
 
所谓lambda演算是一种计算模型，在这种计算模型中，一切都是函数，连数值都可以没有（用函数表示）。它具有和图灵机等价的计算能力，但是和图灵机偏硬件的描述方式不同，lambda演算（基本上）只依赖两条数学推理规则。 
虽然lambda演算中一切都是函数，但都可以不需要函数名。没有函数名的函数称为「匿名函数」。 
比如平方函数 sqr (x) = x * x ，在lambda演算中写成： 
lambda x . x * x
表明对参数 x 执行自己乘以自己的操作。任何用到 sqr (x) 的地方，直接用这个lambda式子替换就可以。 
α-equivalent：identity function
 
λx. x is known as the identity function 
That is, it takes in some input x, and outputs the same x. 
You might ask, “Isn’t λy. y also the identity function?” Indeed it is! λx. x and λy. y are α-equivalent (alpha-equivalent). In fact, all of the following are α-equivalent: 
λx. x
λy. y
λz. z
λ☃. ☃
constant function
 
And what about 
λx. y 
constant function! it ignores the input x and returns y no matter what. 
Bound vs. free variables
 
For example： 
x is a bound variable in λx.x 
but x is a free variable in (λy. y) x. 
β-reduction：function application
 
(λx. x) y 
上面的表达式：以 y 为入参调用函数 λx. x , 得到的结果就是 y。 
The rules of β-reduction say that a term 
 (λx. t) s 
can be reduced to 
t [x := s]
Line by line, it looks like this: 
(λx. x) s
x [x := s]
For example, take a look at the following term: 
λy.(λx. x) y
… and feed it two inputs, a and b: 
(λy.(λx. x) y) a b
((λx. x) y) [y := a]) b
(λx. x) a b
(x [x := a]) b
Now take a look at the following λ-term: 
(λx. x x)(λx. x x)
What happens when you apply β-reduction to it? 
(λx. x x)(λx. x x)
(x x) [x := (λx. x x)]
(λx. x x)(λx. x x)
从计算阶乘说起
 
数学中的阶乘计算如下： 
  factorial 0 = 1
  factorial 1 = 1 * 1
  factorial 2 = 2 * 1 = 2
  factorial 3 = 3 * 2 * 1 = 6
  factorial 4 = 4 * 3 * 2 * 1 = 24
公式化的定义就是： 
factorial(0) = 1
factorial(n) = n*factorial(n-1) (n>0)
用 Lisp 实现代码如下： 
(defun factorial (n)
      (if (= 0 n) 1
       (* n (factorial (- n 1))))
(factorial 4)
这个函数在内部递归调用了自身，调用自身需要函数本体的名字，这个函数叫 factorial 。 
从上面的例子可以看出，递归函数的一个关键点就在于调用自身，而调用自身必须要知自身的函数名，这样才能通过作用域链访问到函数对自己的声明和定义。 
BUT, λ-calculus does not allow this kind of self-reference, at least not directly. 
匿名递归函数
 
函数在内部递归调用了自身，这就叫递归。 
至今为止，我们提到的函数，都是有名字的。 
回到一开始提出的问题：如何实现一个匿名递归函数？ 
但是当需要定义的函数含有递归时，比如阶乘 factorial，我们习惯的方式是 (Kotlin 语言)： 
package com.light.sword.ycombinator
fun factorial(n: Int): Int {
    return when (n) {
        0 -> 1
        else -> n * factorial(n - 1)
fun main() {
    val a = factorial(4)
    println(a) // 24
上面的阶乘函数 factorial 直接写成lambda演算则是 
factorial (x) = lambda x. (x == 0) ? 1 : 
                                     x * factorial (x - 1)
这时候函数的定义部分引用了函数自身，但是，没有函数名意味着用无法直接引用函数自身。怎么办呢？ 
The Y combinator：终结
 
她又来了： 
 λf. (λx.f (x x))(λx.f(x x)) 
希望你现在看她觉得熟悉了。 
现在让我们回到阶乘函数 factorial . 如果函数可以引用自身，那么递归就很简单： 
f := λx.(if x == 0 then 1 else x * f (x–1))
但是，我们知道 λ 演算中不许这么做。 
那我们换个角度思考一下吧。 
我们来定义一个高阶函数 F ， 入参是函数 f : 
F := λf. λx.(if x == 0 then 1 else x * f (x–1))
然后，我们想求解 F 的不动点： 
F(f) = f
这样我们就可以使用 F(f) 进行“间接自引用” 来实现递归。 
我们已经知道，对任意 λ-expression f 
 (λx. f (x x))(λx. f (x x)) 
is a fixed-point of f. 
Let’s see that in action again: 
 X = (λx.f (x x))(λx.f (x x))
 X = f (x x) [x := λx. f (x x)]
 X = f ((λx. f (x x)) (λx. f *(x x)))
 X = f X 
As you can see, for any arbitrary function f, the input X remains unchanged. 
Given this, we can build a function that returns a fixed-point for any function f by taking the function in as an argument: 
 λf. (λx.f (x x))(λx.f (x x)) 
And that right there is the Y combinator. 
各大编程语言实现 Y combinator 函数
 
编程语言的另一个重要分界线是静态类型和动态类型。 
静态类型语言是在编译时确定所有表达式类型的语言，任何类型错误都会导致编译失败。 
动态类型语言直到运行时才进行任何类型检查，并且如果将函数应用于无效类型的参数（*例如，*通过尝试将整数和字符串相加，然后报告错误。 
在常用的编程语言中，C，C ++和Java是静态类型的，Perl，Python和Ruby是动态类型的。Scheme（我们将用于示例的语言）也是动态类型的。（也有跨越静态类型和动态类型之间边界的语言） 
人们经常听到静态类型，称为强类型和动态类型，称为弱类型，但这是滥用术语。强类型只是意味着语言中的每个值都只有一种类型，而弱类型意味着某些值可以有多种类型。因此，动态类型的Scheme也是强类型的，而静态类型的C是弱类型的（因为您可以将指向一种对象的指针转换为指向另一种类型的对象而不改变指针的值） 。 
事实证明，在动态类型语言中定义Y组合器要简单得多。可以用许多静态类型语言定义Y组合子，但是这样的定义通常需要一些hackery，因为Y组合子本身没有简单的静态类型。 
Common Lisp
 
实现 Y 组合子： 
(defun Y (f)
  ((lambda (g) (funcall g g))
   (lambda (g)
     (funcall f (lambda (&rest a)
		  (apply (funcall g g) a))))))
用 Y 组合子实现阶乘与斐波那契数列： 
(defun fac (n)
  (funcall
   (Y (lambda (f)
       (lambda (n)
         (if (zerop n)
	   (* n (funcall f (1- n)))))))
(defun fib (n)
  (funcall
   (Y (lambda (f)
       (lambda (n a b)
         (if (< n 1)
           (funcall f (1- n) b (+ a b))))))
   n 0 1))
(mapcar #'fac '(1 2 3 4 5 6 7 8 9 10))
(1 2 6 24 120 720 5040 40320 362880 3628800))
(mapcar #'fib '(1 2 3 4 5 6 7 8 9 10))
(1 1 2 3 5 8 13 21 34 55)
C doesn’t have first class functions, so we demote everything to second class to match. 
#include <stdio.h>
#include <stdlib.h>
/* func: our one and only data type; it holds either a pointer to
   a function call, or an integer.  Also carry a func pointer to
   a potential parameter, to simulate closure                   */
typedef struct func_t func;
typedef struct func_t {
        func (fn) (func, func);
        func _;
        int num;
} func_t;
func new(func(f)(func, func), func ) {
        func x = malloc(sizeof(func_t));
        x->fn = f;
        x-> = _;       /* closure, sort of */
        x->num = 0;
        return x;
func call(func f, func n) {
        return f->fn(f, n);
func Y(func(*f)(func, func)) {
        func g = new(f, 0);
        g->_ = g;
        return g;
func num(int n) {
        func x = new(0, 0);
        x->num = n;
        return x;
func fac(func self, func n) {
        int nn = n->num;
        return nn > 1   ? num(nn * call(self->_, num(nn - 1))->num)
                        : num(1);
func fib(func self, func n) {
        int nn = n->num;
        return nn > 1
                ? num(  call(self->, num(nn - 1))->num +
                        call(self->, num(nn - 2))->num )
                : num(1);
void show(func n) { printf(" %d", n->num); }
int main() {
        int i;
        func f = Y(fac);
        printf("fac: ");
        for (i = 1; i < 10; i++)
                show( call(f, num(i)) );
        printf("\n");
        f = Y(fib);
        printf("fib: ");
        for (i = 1; i < 10; i++)
                show( call(f, num(i)) );
        printf("\n");
        return 0;
Output: 
fac: 1 2 6 24 120 720 5040 40320 362880
 fib: 1 2 3 5 8 13 21 34 55 
JavaScript
 
var Y = f => (x => x(x))(y => f(x => y(y)(x)));
var fac = Y(f => n => n > 1 ? n * f(n-1) : 1);
fac(10)
3628800
Kotlin
 
package com.light.sword.ycombinator
 * FP: Y Combinator
 * lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))
 * Created by jack on 2017/7/9.
typealias G<T, R> = (T) -> R
interface F<T, R> : Function1<F<T, R>, G<T, R>>
fun <T, R> f(block: (F<T, R>) -> G<T, R>) = object : F<T, R> {
    // 调用函数自身
    override fun invoke(g: F<T, R>) = block(g)
typealias E<T, R> = Function1<G<T, R>, G<T, R>>
 * Y 组合子函数
 * @param e :E 入参，是一个函数类型 Function1<G<T, R>, G<T, R>>
fun <T, R> Y(e: E<T, R>) = ({ g: F<T, R> -> g(g) })(f { g ->
    e { x -> g(g)(x) }
 * 用 Y 组合子实现 factorial 阶乘函数
val factorial: (Int) -> Int = Y { f ->
    { x ->
        if (x == 0) 1 else x * f(x - 1)
 * 用 Y 组合子实现 fibonacci 数列函数 fib: (T)->R
 * Y(fib) = fib
 * 可以推断： Y(Y(fib)) = Y(fib) = fib
val fib: (Int) -> Int = Y { f ->
    { x ->
        if (x == 1 || x == 2) 1 else f(x - 1) + f(x - 2)
fun main() {
    println(fib(10)) // 55
    println(factorial(10)) // 3628800
The Y Combinator (no, not that one) A crash-course on lambda calculus： 
https://medium.com/@ayanonagon/the-y-combinator-no-not-that-one-7268d8d9c46 
The Y Combinator (Slight Return)： 
https://mvanier.livejournal.com/2897.html 
Y combinator: 
https://rosettacode.org/wiki/Y_combinator#Kotlin 
在前面的几个帖子里，我已经建立了如何把lambda演算变成一个有用的系统的点点滴滴。 我们已经有了数字，布尔值和选择运算符。我们唯一欠缺的是重复。
这个有点棘手。lambda演算使用递归实现循环（递归的解释可以看这里）。 但是，由于在lambda演算里函数没有名字，我们得采取一些非常手段。这就是所谓的Y组合子，又名lambda不动点运算符。
让我们先来看看lambda演算之外的一个简单的递归函数。阶乘函数，这是标准的例子：
factorial(n) = 1 if n = 0 
				在这个例子中，我们展示了使用QueryFusionRetriever的两种方法，这两种方法旨在改进互惠秩融合（Reciprocal Rank Fusion）。互惠秩融合是一种用于合并多个排序列表的技术，特别是在信息检索领域，它通过考虑每个列表中项目的排名位置来综合不同来源的结果。QueryFusionRetriever则可能是指一种更先进的工具或算法，它实现了对查询结果进行融合的新方法，以期获得比传统互惠秩融合更好的效果。
请提供更多的上下文或者具体说明您想了解的内容，以便我能为您提供更准确的翻译和解释。
Y组合子的用处
作者：王霄池链接：https://www.zhihu.com/question/21099081/answer/18830200来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Y组合子的用处是使得 lambda 表达式不需要名字。
如你所说，阶乘函数可以这样定义：
let F = lambda n. n==0 ? 1 : n*(F...
        ( * n (factorial ( - n 1 ))))))
 请注意，在定义阶乘函数时，我们进行了递归调用。 我们将这种定义称为显式递归定义。 您很快就会看到我们所说的隐式递归定义（扰流器：通过非递归方法生成的递归函数）。
目标-消除明确的递归
如果我们被限制进行递归调用，我们仍然可以实现阶乘函数吗？ 答案是肯定的，这将使我们直接进入Y-Combinator。
什么是Y组合器？它
				推导Y组合子
这篇文章的创作动机是：之前一直不理解Y组合子是怎么被想出来的，查这方面的资料看到了重新发明 Y 组合子 JavaScript(ES6) 版，但是写得不太清楚，于是决定在本文彻底讲清楚。
本文的主要内容是在递归函数的非递归定义中引入omega组合子和Y组合子，并推导他们的形式。本文分为三个部分：
在FP中通常用递归的方式定义阶乘函数，本文首先对其给出了一个非递归的定义。
对上述过程，...
				Y 组合子
lambda函数是匿名函数，也就是没有名字的函数，那么如何用lambda函数实现递归呢？
因为python的匿名函数表示方法局限性很大，所以我使用了scheme语言讲解。
下面看一个递归求阶乘的函数：
(define fac
  (lambda (x)
    (if (= 0 x)
        (* x (fac (- x 1))))))
如果不要第一行的命...
				Y combinator本身是一个无状态函数，当用于另一个无状态的函数时，将返回该函数的递归版本。比如定义Y：（为了说明方便，用λi代替lambda关键字）
(defun y (f) 
    ((λ1 (x) (funcall x x))
     (λ2 (y)
         (funcall f (λ3 (&rest
 args) 
             (apply (
				上次发表了VS2008亮点：用Lambda表达式进行函数式编程这篇文章后，有些人提出希望看C#版。其实我本来想等大家多尝试下能否自己实现的，可惜没有太多人实际思考这个问题，是不是觉得函数式编程离我们的日常生活太远……不管怎么说，这次我将公布强类型语言C#实现不动点组合子Y的方法，以及类型推导的全过程。不喜欢强类型思考的朋友看本文一定要做好头晕的准备……
首先复习一下不动点组合子，它就是这样的东西...
				Y结合子（Y Combinator，也译作Y组合子），是在原生不支持递归的编程语言中利用lambda演算实现递归的一种方式，Y结合子在支撑递归的语言中没有什么实际的用途，更多是为了锻炼大家的程序逻辑思维，通过推演充分理解lambda和闭包。下面我们利用Javascript来一步步推导Y结合子。
先一个经典的递归算法——斐波那契数列讨论，以下是Javascript原生支撑的递归