JavaScript中的y组合子:

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

编辑: 通过查看代码，我学到了很多东西，但是如果没有一些背景知识，这个代码有点难以理解——对此我感到抱歉。有了其他答案提供的一些常识，你就可以开始分析正在发生的事情了。

The Y function is the "y-combinator". Now take a look at the var factorial line where Y is used. Notice you pass a function to it that has a parameter (in this example, recurse) that is also used later on in the inner function. The parameter name basically becomes the name of the inner function allowing it to perform a recursive call (since it uses recurse() in it's definition.) The y-combinator performs the magic of associating the otherwise anonymous inner function with the parameter name of the function passed to Y.

关于Y如何变魔术的完整解释，请查看链接文章(顺便说一下，不是我写的)。

this运算符可以简化你的生活:

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

这样就避免了额外的函数:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

最后，调用fac(5)。

作为一个组合子的新手，我发现Mike Vanier的文章(感谢Nicholas Mancuso)真的很有帮助。我想写一个总结，除了记录我的理解，如果它能对其他人有所帮助，我将非常高兴。

从糟糕到不那么糟糕

以factorial为例，我们使用下面的almost-factorial函数来计算number x的阶乘:

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

在上面的伪代码中，almost-阶乘接受函数f和数字x (almost-阶乘是curry的，所以它可以被视为接受函数f并返回一个1-arity函数)。

当almost-factorial计算x的阶乘时，它将x - 1的阶乘计算委托给函数f，并将该结果与x相加(在本例中，它将(x - 1)的结果与x相乘)。

它可以被看作是almost-阶乘接受了一个蹩脚的阶乘函数(它只能计算到数字x - 1)，并返回一个不那么蹩脚的阶乘(计算到数字x)。如下形式:

almost-factorial crappy-f = less-crappy-f

如果我们反复地将阶乘的不那么糟糕的版本传递给almost阶乘，我们最终会得到我们想要的阶乘函数f。其中可以考虑为:

almost-factorial f = f

Fix-point

几乎阶乘f = f意味着f是几乎阶乘函数的定点。

这是一种非常有趣的方式来看待上述函数之间的关系，对我来说是一个顿悟的时刻。(如果你还没读过，请阅读Mike关于fix-point的文章)

三个函数

概括地说，我们有一个非递归函数fn(就像我们的几乎阶乘)，我们有它的定点函数fr(就像我们的f)然后Y所做的是当你给Y fn, Y返回fn的定点函数。

总之(通过假设fr只有一个参数来简化;X退化为X - 1, X - 2…在递归):

我们将核心计算定义为fn: def fn fr x =…将x与result from (fr (- x1))累加，这是一个几乎有用的函数-尽管我们不能直接在x上使用fn，但它很快就会有用。这个非递归fn使用一个函数fr来计算它的结果 fnfr = fr, fr是Fn的定点，fr是有用的函数，我们可以用fr作用于x来得到结果 Y fn = fr, Y返回一个函数的定点，Y把我们几乎有用的函数fn变成有用的fr

推导Y(不含)

我将跳过Y的推导，直接去理解Y。Mike Vainer的帖子有很多细节。

Y的形式

Y定义为(lambda微积分格式):

Y f = λs.(f (s s)) λs.(f (s s))

如果我们替换函数左边的变量s，我们得到

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

所以(yf)的结果就是f的定点。

(yf)为什么成立?

根据f的特征，(Y f)可以是任意arity的函数，为了简化，我们假设(Y f)只带一个参数，就像我们的阶乘函数一样。

def fn fr x = accumulate x (fr (- x 1))

因为fn fr = fr，我们继续

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

当最里面的(fn fr 1)是基本情况并且fn在计算中不使用fr时，递归计算终止。

再看一下Y:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

So

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

对我来说，这种设置的神奇之处在于:

fn and fr interdepend on each other: fr 'wraps' fn inside, every time fr is used to calculate x, it 'spawns' ('lifts'?) an fn and delegates the calculation to that fn (passing in itself fr and x); on the other hand, fn depends on fr and uses fr to calculate result of a smaller problem x-1. At the time fr is used to define fn (when fn uses fr in its operations), the real fr is not yet defined. It's fn which defines the real business logic. Based on fn, Y creates fr - a helper function in a specific form - to facilitate the calculation for fn in a recursive manner.

它帮助我现在这样理解Y，希望有帮助。

顺便说一句，我还发现《通过Lambda微积分介绍函数式编程》这本书非常好，我只读了一部分，事实上，我无法理解书中的Y，这让我想到了这篇文章。

y组合子实现匿名递归。所以与其

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

你可以这样做

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

当然，y-combinator只适用于按名字命名的语言。如果你想在任何正常的值调用语言中使用它，那么你将需要相关的z-combinator (y-combinator将发散/无限循环)。

下面是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);

我想知道从头开始建立这个系统是否有任何用处。让我们来看看。这是一个基本的递归阶乘函数:

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);
    };
});