在前一篇文章中,主要實作了幾個典型的 functional 函式。文章最後也提出一個疑問:為什麼那樣的實作與 F# 之類的函式式語言「不太一樣」?這次就來試試更「函式」的寫法。
同樣地,嘗試對之前實作的函式做一些改動,把 for 迴圈拿掉。怎麼拿掉呢?這裡要先引入集合的歸納法定義:
一個集合要麼是空集,要麼是一個「數」與一個「集合」組成的數對。
從這個定義可以看到,每一個集合都可以看成「一個數 + 一個集合」的對。例如 {1,2,4,5} 可以認為是數 1 與集合 {2,4,5} 組成的一對,寫成 (1, {2,4,5})。遞歸地,{2,4,5} 可以看成 (2, {4,5}),最後則是 (5, ∅)。
按照這樣的理解,我們就可以用遞迴消除迴圈——因為在分解的過程中已經訪問了每一個資料項,而終止條件就是空集。
下面看 filter 函式的另一個實作,原名稱前加 f 前綴以區別:
function ffilter(arr,callback){
var i=arguments[2] || 0,
out = arguments[3] || [];
if(!arr[i]) return arguments[3];
if(callback(arr[i]))
out.push(arr[i]);
return arguments.callee(arr,callback,++i,out);
}
測試:
var arr = [1,2,3,4,5,6,7,8,9,10];
var even = function(item){
if(typeof item !== "number") return false;
return !(item & 1);
};
console.log(ffilter(arr,even));
結果:
[2, 4, 6, 8, 10]
消除迴圈之後,這樣的寫法更貼近數學的歸納定義,顯得更自然。同樣地,再看 fold:
var arr = [1,2,3,4,5,6,7,8,9,10];
var plus = function(a,b){
return a+b;
};
console.log(ffold(arr,plus,3));
結果:
58
其他函式也可以用同樣的方法改寫。這樣就感覺更 functional 了,但能不能再更貼近數學定義呢?下一次再嘗試。
上面提到那些寫法能否與數學定義更加接近,下面就試試使用鏈表。先給出一個定義:
var node = function(){
this.data = 0;
this.tail = null;
};
再初始化一個鏈表:
var n1 = new node(),n2 = new node(),n3 = new node(),n4 = new node(),n5 = new node(); n1.data=1,n1.tail=n2; n2.data=2,n2.tail=n3; n3.data=3,n3.tail=n4; n4.data=4,n4.tail=n5; n5.data=5,n5.tail=null;
fold 的鏈表版本:
function lfold(head,callback,b){
if(!head) return b;
else return callback(head.data,arguments.callee(head.tail,callback,b));
}
輸出結果:
18
按照之前的定義,一個集合要麼是空集,要麼是一個「頭」與一個「尾」(集合)組成的數對。每一次呼叫函式時,就分解為 head 與 tail,直到集合為空。寫完上面的 lfold,實在感覺太完美了——它幾乎就是定義本身。要是程式都能長這樣,註解都不需要了,那真是一種享受。
這樣子算是最近接數學定義的表示了。因為 JavaScript 不支援許多函式式語言的 pattern matching,所以無法「自動」分解,也就不能直接表示歸納定義。
JavaScript 除了以上這些,還可以實現函式式裡面的 partial application,dojo 框架裡面的 hitch 就做到了這個功能,這也是函式式貼近數學的另一個明顯例子,我將在下一篇討論。
作為思維練習,把迴圈改寫成遞迴很有價值——它強迫你想清楚「資料結構的歸納定義」與「遞迴的終止條件」。但實際專案中,上面這幾段程式碼有幾個問題不該忽略:
第一,arguments.callee 已被嚴格模式禁用,而且在 V8 等引擎中會妨礙優化。改寫成具名函式表達式即可:const ffilter = function f(arr, cb, i = 0, out = []) { ... return f(...) }。
第二,用 arguments 當參數通道會污染對外簽名,也失去型別提示。改用預設參數會清楚得多。
第三,遞迴深度有上限。這個 ffilter 每處理一個元素就遞迴一層,對 10 筆資料沒問題,但幾千筆就會撞上 Maximum call stack size exceeded。JavaScript 引擎目前普遍不保證尾端呼叫最佳化,所以這種寫法不能用在真實資料量上。
第四,lfold 的計算順序是「先遞迴到底再回來算」,這對加法沒差別,但對減法、除法或有順序依賴的操作,結果會與 forEach 版本不同。這也是為什麼 reduce 要區分 reduce 與 reduceRight。
結論很明確:這篇的價值在於理解歸納定義與遞迴的對應關係,以及看懂 Array.prototype.reduce 背後的數學來源。真正 production 的程式碼,請直接用原生的 filter、map、reduce——它們經過引擎高度優化,也不會有堆疊溢出的風險。