just for fun...

Y組合子（Y Combinator）是一個很有趣的結構，利用他可以協助函數做遞迴。也許是因為這個結構非常奇妙而有趣，所以某hacker聚集的網站也用這個名稱吧？

以前在blog中分享過要怎樣利用Y Combinator讓匿名函數可以遞迴，不過也有人批評這樣好像在玩弄文字遊戲。所以除了數學運算（費氏數列）這樣的例子，也來想想到底還能怎樣使用Y組合子。
（如果從來沒發現Javascript可以做functional programming，建議可以用javascript functional programming等關鍵字找找。其實，在學習Javascript中會碰到的一些東西，例如anonymous function、higher order function等也都是functional programming的重要特性之一。）

關於Combinator相關的主題，也不妨上wikipedia看看，跟Y Combinator相關的主題是「不動點組合子」：http://en.wikipedia.org/wiki/Fixed_point_combinator，英文版中還有一個Javascript版本的Y Combinator程式可以參考。

首先來看一下wiki上面提供的範例（稍微改了一下讓他閱讀性好一點）：

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

把它一層一層剝開，會發現他其實就是return一個即時執行的匿名函數的結果，而且這個匿名函數的body跟傳進去的參數是完全一樣的函數結構。在這個函數結構中，會return傳給Y函數的函數f的執行結果，傳給f的還是一個函數，不過透過他可以接受真正要處理的參數v，然後處理他。

要傳給Y的函數，必須用一個固定的方法改寫，這樣才能讓Y幫你做遞迴，例如費氏數列函數：

function fact(n) {
    if(n===0) return 1;
    else return n * fact(n-1);
}

需要把它用一個匿名函數包覆一下，才可以透過Y來做遞迴：

var fact = Y(
    function(f) {
        return function(n) {
            if(n===0) return 1;
            else return n * f(n-1);
        };
    }
);

傳給上述函數的f，就是return的那個函數，所以可以用f來做遞迴。

在應用上，我想先試試做函數的組合。組合，或者可以說是嵌套，其實就把一個函數的結果當做另一個函數的參數。例如有a, b, c三個函數，那這樣的程式就是組合：

a(b(c(3)));

有一個常見的Design Pattern: Decorator，在Javascript中就可以利用函數組合的方式來實作。不過有時候以a(b(c(4)))這樣的方式寫死，在應用上並不方便。例如我寫好了一堆Decorator，然後希望用程式來控制，依照要處理的狀況來彈性組合函數，這樣就有點難辦，這時候就可以應用函數組合。

之前也寫過用來這樣組合函數的function，但是邏輯比較複雜：

function Compositor(f){
    return function(n) {
        var req = function(x) {
            if(f.length>0){
                return x(req(f.pop()));
            } else {
                return x(n);
            }
        };
        return req(f.pop());
    };
}

利用Y組合子，程式就會更簡潔，只需要專注在邏輯，不需要花時間設計複雜的遞迴：

function composite(f) {
    return Y(
        function(g) {
            return function(n) {
                if(f.length === 1) return f.shift()(n);
                else {
                    return g(f.shift()(n));
                }
            };
        }
    );
}

這樣只要記住，Y會把要遞迴的函數透過g傳進來，所以就不用自己設計複雜的遞迴方法。

然後寫個簡單的測試：

var toolkit = {
    "add1":function(n){return n+1;},
    "mul3":function(n){return n*3;},
    "add5":function(n){return n+5;}
};

var a = composite([
    toolkit.add1,
    toolkit.mul3
]);

console.log(a(4));//15

var b = composite([
    toolkit.mul3,
    toolkit.add5
]);

console.log(b(4));//17

composite會依序從傳給他的函數陣列呼叫函數，把要處理的參數傳入，然後把處理過的結果傳給下一個函數。針對同一個資料傳給他不同的函數組合，就可以算出不同結果。