Y Combinator

現代開發者，對於函數式程式設計，多多少少都有接觸過了吧！如果程式語言支援一級函式，也就是函數本身也是個值，可以指定給變數、傳入函式或從函式中傳回，那麼在進行函數式程式設計時會方便許多，若是一級函式的語法簡潔，那麼寫來就會更加輕鬆愉快！

例如，JavaScript 支援一級函式，而且支援箭號函式（Arrow function）語法，使得撰寫一級函式輕鬆許多（雖然技術面上，箭號函式與 function 有些微不同），那麼，試著來寫個 Y Combinator 吧！

從遞迴函式開始

先來個簡單的開始，如何用遞迴寫個計算階乘的函式？

function fact(n) {
    return n < 2 ? 1 : n * fact(n - 1);
}

這樣是定義一個 fact 函式，現在要求用匿名函式來實現，那麼可以寫成：

let fact = function(n) {
    return n < 2 ? 1 : n * fact(n - 1);
};

有 function 又有 return，寫起來或閱讀起來就是麻煩，那麼來用箭號函式：

let fact = n => n < 2 ? 1 : n * fact(n - 1);

接下來要求必須是完全匿名，也就是不能有 fact 變數，只寫 n => n < 2 ? 1 : n * fact(n - 1) 顯然是不行的，因為 fact 沒有定義，怎麼辦呢？那就再來層箭號函式：

fact => n => n < 2 ? 1 : n * fact(n - 1);

這個箭號函式就合法了，只是想執行這個箭號函式時怎麼辦？誰來給這個箭號函式一個真正的遞迴函式，以便讓 fact 參數可以參考？

總之，先來看看階乘時會需要的函式是什麼，假設定義為 y 好了：

function y(f) {
    // 假設存在一個 fact
    return f(fact);
}

這邊希望 y 可以傳回函式，也就是希望 y(fact => n => n < 2 ? 1 : n * fact(n - 1)) 傳回的會是函式，此函式可以套用數值 n 來取得階乘結果，也就是相當於必須能 f(fact)(n) 來取得階乘結果，因此 fact 可以定義為：

function y(f) {
    let fact = n => f(fact)(n);
    return f(fact);
}

只是多了個變數 fact 而已，這樣算什麼呢？y 函式有沒有辦法全部用匿名函式實現？假設有個 get_fact 能做到這點，那麼就可以變成這樣：

function y(f) {
    function get_fact() {
        // 假設都用匿名函式實現 ...
    }
    return get_fact();
}

實際上，get_fact 看來像個騙子，只是把問題藏到裏頭而已：

function y(f) {
    function get_fact() {
        let fact = n => f(fact)(n);
        return f(fact);
    }
    return get_fact();
}

要騙就騙到底好了，既然 f(fact) 就是 get_fact() 的傳回結果，那麼就改成這樣：

function y(f) {
    function get_fact() {
        let fact = n => get_fact()(n);
        return f(fact);
    }
    return get_fact();
}

咦？好像不用 fact 變數了，那就改成這樣：

function y(f) {
    function get_fact() {
        return f(n => get_fact()(n));
    }
    return get_fact();
}

只不過，get_fact 依舊是個具名的遞迴函式，這樣下去沒完沒了的，假設 get_fact 函式有個 get_fact 參數，那麼就可以把傳進來的參數再傳給自己：

function y(f) {
    function get_fact(get_fact) {
        return f(n => get_fact(get_fact)(n));
    }
    return get_fact(get_fact);
}

然後改為箭號函式版本：

function y(f) {
    let get_fact = get_fact => f(n => get_fact(get_fact)(n));
    return get_fact(get_fact);
}

接下來不需要 get_fact 變數，直接使用箭號函式：

function y(f) {
    return (get_fact => f(n => get_fact(get_fact)(n)))(get_fact => f(n => get_fact(get_fact)(n)));
}

咦？沒有變數了？只剩下參數 get_fact 了？名稱有點長，改成 x 好了：

function y(f) {
    return (x => f(n => x(x)(n)))(x => f(n => x(x)(n)));
}

順便也把 y 改成箭號函式：

let y = f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)));

y 的實現全都是匿名函式！可以這麼使用它來產生一個可遞迴的階乘函式：

y(fact => n => n < 2 ? 1 : n * fact(n - 1))(5) // 120

要不要自己試著也來推導一個可傳回遞迴費式數計算的函式呢？結果其實會是相同的，也就是說，上頭這個 y 也可以用來產生計算費式數的遞迴函式，例如：

y(fib => n => (n ==0 || n == 1) ? n : fib(n - 1) + fib(n - 2))(10) // 55

Y Combinator 看來很神奇，像是可以運行程式的程式（a program that runs programs），美國有間創投公司命名為 Y Combinator，因為他們覺得自己就類似可運行程式的程式 Y Combinator，只不過他們是間協助新創公司的公司。

至於搞 Y Combinator 做什麼？就現代程式語言來說，搞 Y Combinator 不太能有實際的作用，然而，如果想試著用箭號函式（也就是一種 lambda 表示式）來表達程式意圖的話，那麼 Y Combinator 會是必要的元素之一！