iT邦幫忙

7

挑戰函數式Javascript之Y組合子應用

just for fun...

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

以前在blog中分享過要怎樣利用Y Combinator讓匿名函數可以遞迴,不過也有人批評這樣好像在玩弄文字遊戲XD。所以除了數學運算(費氏數列)這樣的例子,也來想想到底還能怎樣使用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會依序從傳給他的函數陣列呼叫函數,把要處理的參數傳入,然後把處理過的結果傳給下一個函數。針對同一個資料傳給他不同的函數組合,就可以算出不同結果。


1 則留言

0
fillano
iT邦超人 1 級 ‧ 2012-05-12 15:19:51

嗯,還是要補充一下,Y組合子其實是在非常嚴格的限制條件下,來讓匿名函數做遞迴時才會用到,說真的在實用上並沒有很大的意義。所以一開頭就說just for fun。(有興趣的話,可以參考維基百科上面關於組合子邏輯以及lambda演算相關的條目)

如果規定要遞迴的匿名函數第一個參數就是會函數自己,第二個參數是要處理的資料,就完全不必這麼複雜:

<pre class="c" name="code">
function Y(f) {
    return function(v) {
        return f(f, v);
    };
}

這個時候,只要調整一下要遞迴的函數:

<pre class="c" name="code">
var fact = Y(
    function(f, n) {
        if(n===0) return 1;
        else return n * f(f,n-1);
    }
);
console.log(fact(5));

其實結果是一樣的。

我要留言

立即登入留言