从“函数”的角度来看，y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子，如果他们听说过的话。
什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?
当前回答
我想知道从头开始建立这个系统是否有任何用处。让我们来看看。这是一个基本的递归阶乘函数:
function factorial(n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
让我们重构并创建一个名为fact的新函数，它返回一个匿名的阶乘计算函数，而不是执行计算本身:
function fact() {
return function(n) {
return n == 0 ? 1 : n * fact()(n - 1);
};
}
var factorial = fact();
这有点奇怪，但这没什么问题。我们只是在每一步生成一个新的阶乘函数。
这个阶段的递归仍然相当明确。事实函数需要知道自己的名字。让我们参数化递归调用:
function fact(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
}
function recurser(x) {
return fact(recurser)(x);
}
var factorial = fact(recurser);
这很好，但是递归仍然需要知道自己的名字。让我们把它参数化:
function recurser(f) {
return fact(function(x) {
return f(f)(x);
});
}
var factorial = recurser(recurser);
现在，我们不直接调用递归器(recurser)，而是创建一个包装器函数，返回它的结果:
function Y() {
return (function(f) {
return f(f);
})(recurser);
}
var factorial = Y();
现在我们可以完全去掉递归的名字;它只是Y内部函数的一个参数，可以用函数本身替换:
function Y() {
return (function(f) {
return f(f);
})(function(f) {
return fact(function(x) {
return f(f)(x);
});
});
}
var factorial = Y();
唯一仍然引用的外部名称是fact，但现在应该清楚了，它也很容易参数化，创建完整的，通用的解决方案:
function Y(le) {
return (function(f) {
return f(f);
})(function(f) {
return le(function(x) {
return f(f)(x);
});
});
}
var factorial = Y(function(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
});
其他回答
我想知道从头开始建立这个系统是否有任何用处。让我们来看看。这是一个基本的递归阶乘函数:
function factorial(n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
让我们重构并创建一个名为fact的新函数，它返回一个匿名的阶乘计算函数，而不是执行计算本身:
function fact() {
return function(n) {
return n == 0 ? 1 : n * fact()(n - 1);
};
}
var factorial = fact();
这有点奇怪，但这没什么问题。我们只是在每一步生成一个新的阶乘函数。
这个阶段的递归仍然相当明确。事实函数需要知道自己的名字。让我们参数化递归调用:
function fact(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
}
function recurser(x) {
return fact(recurser)(x);
}
var factorial = fact(recurser);
这很好，但是递归仍然需要知道自己的名字。让我们把它参数化:
function recurser(f) {
return fact(function(x) {
return f(f)(x);
});
}
var factorial = recurser(recurser);
现在，我们不直接调用递归器(recurser)，而是创建一个包装器函数，返回它的结果:
function Y() {
return (function(f) {
return f(f);
})(recurser);
}
var factorial = Y();
现在我们可以完全去掉递归的名字;它只是Y内部函数的一个参数，可以用函数本身替换:
function Y() {
return (function(f) {
return f(f);
})(function(f) {
return fact(function(x) {
return f(f)(x);
});
});
}
var factorial = Y();
唯一仍然引用的外部名称是fact，但现在应该清楚了，它也很容易参数化，创建完整的，通用的解决方案:
function Y(le) {
return (function(f) {
return f(f);
})(function(f) {
return le(function(x) {
return f(f)(x);
});
});
}
var factorial = Y(function(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
});
我认为回答这个问题的最好方法是选择一种语言，比如JavaScript:
function factorial(num)
{
// If the number is less than 0, reject it.
if (num < 0) {
return -1;
}
// If the number is 0, its factorial is 1.
else if (num == 0) {
return 1;
}
// Otherwise, call this recursive procedure again.
else {
return (num * factorial(num - 1));
}
}
现在重写它，使它不使用函数内部的函数名，但仍然递归地调用它。
函数名factorial唯一应该看到的地方是在调用位置。
提示:不能使用函数名，但可以使用参数名。
解决这个问题。不要去查。一旦你解决了它，你就会明白y组合子解决了什么问题。
下面是Y-Combinator和Factorial函数的JavaScript实现(来自Douglas Crockford的文章，可在http://javascript.crockford.com/little.html上找到)。
function Y(le) {
return (function (f) {
return f(f);
}(function (f) {
return le(function (x) {
return f(f)(x);
});
}));
}
var factorial = Y(function (fac) {
return function (n) {
return n <= 2 ? n : n * fac(n - 1);
};
});
var number120 = factorial(5);
其他答案对此提供了相当简洁的答案，但没有一个重要的事实:你不需要用任何实用语言以这种令人费解的方式实现定点组合子，这样做没有任何实际目的(除了“看，我知道y组合子是什么”)。这是一个重要的理论概念，但没有什么实际价值。
如果你准备好长篇大论，Mike Vanier有一个很好的解释。长话短说，它允许您在一种不一定支持递归的语言中实现递归。
