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會依序從傳給他的函數陣列呼叫函數,把要處理的參數傳入,然後把處理過的結果傳給下一個函數。針對同一個資料傳給他不同的函數組合,就可以算出不同結果。
嗯,還是要補充一下,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));
其實結果是一樣的。