JavaScript实现Y组合子函数

什么是Y组合子函数？

通俗来讲就是用来解决匿名递归函数实现的。

实现过程

我们知道，具名递归函数可以直接通过函数名称来实现自己调用自己，即递归调用，那么匿名函数怎么实现呢？首先来看一段代码：

function Y(g) { return g(g) }

Y函数的参数名称为g，g为函数类型，然后对g进行递归调用。看到这里是否发现了些相似的点，由于匿名函数没有具体名称，因此我们声明一个函数Y对g进行包装，以便函数g可以进行递归调用，接下来我们来看看具体的调用方法：

Y(Y)

很容易意料到，程序会报错。现在看来函数仍是具有名称的，让我们写的更抽象点儿：

(function (g) {
  return g(g);                          
})(function (g) {
  return g(g);                             
})

其实可以看到，我们仅仅是对Y(Y)这种写法进行了改写，他们本质都是相同的。立即执行函数中的参数就是我们之前编写的函数Y，而该立即执行函数中的函数体与我们的Y函数并没有任何联系，在这里，他们仅仅只是代码一样而已，后面我们会看到差别。现在，程序并不能正确的跑起来，让我们以阶乘为例，看看会有怎样的事情发生：

(function (g) {
    return g(g);
})(function (g) {
    return function (x) {
        if (x === 0) {
            return 1;
        }
        return x;
    }
})

在这里，我们简单地改写了一下Y函数的函数体，他返回了另外的一个函数，该函数的功能很简单，如果传入的参数为0，则返回1，否则返回原值，我们可以先来看看这样的执行结果是什么：

(function (g) {
    return g(g);
})(function (g) {
    return function (x) {
        if (x === 0) {
            return 1;
        }
        return x;
    }
})(10)

毫无疑问地，结果为10，当10改为0时，返回的结果为1。在这里，立即执行函数的函数体中的g(g)其实仅仅只调用了一次Y函数，因为我们还没有对Y进行递归处理，接下来看看完整功能的函数是怎样的：

(function (g) {
    return g(g);
})(function (g) {
    return function (x) {
        if (x === 0) {
            return 1;
        }
        return x * g(g)(x - 1);
    }
})

是的，我们将return x改为return x * g(g)(x - 1)，就实现了我们所需要的阶乘功能。想想这是为什么？此处的g(g)(x - 1)是什么意思？其实就像我之前说的那样，g(g)代表我们的Y函数会对自身进行一次递归调用，由于现在Y函数的返回值为一个函数，它需要一个数值作为参数，因为我们将(x - 1)传入了进去，这与我们写具名函数的递归写法时是一样的。

我们能否让这个函数更通用些呢？这里，阶乘的逻辑是与Y函数写在一起的，我们试着将它抽象出来：

function Y(f) {
    return (function (g) {
        return g(g);
    })(function (g) {
        return function (x) {
            return f(x, g(g));
        }
    });
}

function fc(x, g) {
    if (x === 0) {
        return 1;
    }
    return x * g(x - 1);
}

console.log(Y(fc)(4));

顺便一说，忘记之前的Y函数吧，现在的Y函数与之前不一样。可以看到，我们仅仅只是将之前的阶乘逻辑提取出来，定义为fc函数，事实上这依旧不够通用，我们先对fc函数进行修改：

function fc(g) {
    return function (x) {
        return x === 0 ? 1 : x * g(x - 1);
    }
}

所做的是将fc的两个参数变为逐个传递（即柯里化函数），然后立即函数的变化：

function Y(f) {
    return (function (g) {
        return g(g);
    })(function (g) {
        return f(function (x) {
            return g(g)(x);
        });
    });
}

function fc(g) {
    return function (x) {
        return x === 0 ? 1 : x * g(x - 1);
    }
}

console.log(Y(fc)(4));

这里，我们可以看到立即执行函数的参数部分，仅仅只是对自身进行递归调用，逻辑交由外部函数处理。

END.