本文译自 “Deriving the Y Combinator in 7 Easy Steps“,

原文链接:http://igstan.ro/posts/2010-12-01-deriving-the-y-combinator-in-7-easy-steps.html

在没有原生递归支持的语言中,Y结合子(Y Combinator)是一种实现递归的方式(事实上,它更常被作为一种锻炼程序思维的方式)。要实现Y结合子,要求这种语言支持匿名函数。

此处,我选择JavaScript来推导Y结合子,从递归阶乘函数的定义开始,一步一步进行变换。

Step 1

最初的实现,使用JavaScript内建的递归机制。

1
2
3
4
var fact = function (n) {
    if (n < 2) return 1;
    return n * fact(n - 1);
};

 

Step 2

获得递归的最简单方法是什么?我们可以定义一个函数,它接受它自身作为参数,并且用这个参数作为参数,调用这个参数。当然,这是一个无限循环,会导致栈溢出。

1
2
3
4
5
(function (f) {
    f(f);
})(function (f) {
    f(f);
});

我们的阶乘函数套用上面的模板,再做点改动,阶乘函数接受一个我们还不知道的参数,所以我们要的是返回一个接受该参数的函数。然后这个函数可以被用于计算阶乘。同时,这可以让我们的阶乘函数不会无限循环下去。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
var fact = (function (f) {
    return function (n) {
        // 终止条件
        if (n < 2) return 1;

        //因为f返回一个函数,所以这有一个双重调用。 
        return n * f(f)(n - 1);
    };
})(function (f) {
    return function (n) {
        // 终止条件
        if (n < 2) return 1;

        // 因为f返回一个函数,所以这有一个双重调用。
        return n * f(f)(n - 1);
    };
});

Step 3

此时,我们的代码有一些糟糕的重复,让我们把放进一个名叫recur的辅助函数里。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
var recur = function (f) {
    return f(f);
};

var fact = recur(function (f) {
    return function (n) {
        if (n < 2) return 1;

        // 因为f返回一个函数,所以这有一个双重调用。
        return n * f(f)(n - 1);
    };
});

Step 4

上面这个版本的问题是,它有两重调用(指的是f(f)(n-1))。我们想去除它,让我们的函数跟接近于递归版本。怎么做呢?

我们可以使用一个辅助函数,它接受一个数值参数,进行两重调用。这个trick通过把辅助函数放在可见f的作用域里,所以g可以调用f。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
var recur = function (f) {
    return f(f);
};

var fact = recur(function (f) {
    var g = function (n) {
        return f(f)(n);
    };

    return function (n) {
        if (n < 2) return 1;

        // 没有双重调用了,函数g接受一个数值参数。
        return n * g(n - 1);
    };
});

Step 5

以上版本工作良好,但是它的定义太杂乱了。我们可以把它再清理为一个辅助函数,把阶乘定义尽可能分离出来。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
var recur = function (f) {
    return f(f);
};

var wrap = function (h) {
    return recur(function (f) {
        var g = function (n) {
            return f(f)(n);
        };

        return h(g);
    });
};

var fact = wrap(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});

Step 6

g只调用了一次,让我们把g内联进wrap里。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
var recur = function (f) {
    return f(f);
};

var wrap = function (h) {
    return recur(function (f) {
        return h(function (n) {
            return f(f)(n);
        });
    });
};

var fact = wrap(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});

Step 7

现在,如果我们把recur也内联进wrap里,我们就得到了著名的Y结合子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
var Y = function (h) {
    return (function (f) {
        return f(f);
    })(function (f) {
        return h(function (n) {
            return f(f)(n);
        });
    });
};

var fact = Y(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});

The End

玩的开心!