fold的抽象訓練

在Java、Scala、Python、JavaScript、Ruby等程式語言中，都有個reduce這個API的存在，凡是要從一組數據中求得特定值，都可以藉由這個API來達到。實際上，reduce的概念來自於函數式程式設計的fold概念，是一種對流程高度抽象化的表現，藉由探討reduce，乃至於fold設計時的種種考量，對流程抽象化思考上，將會是非常紮實的訓練。

對於一組數據，重複地執行某個運算，使之求得某值，這本來就是電腦最初設計之目的。機械語言是一組數字序列，對於想要電腦進行的工作，必須查表知道對應的數字，雖然辛苦，然而一本萬利，因為後續幾天或幾星期的重複動作就可以交給電腦了，不過，由於查表也是個重複的工作，因而有人設計可將指令對照至數字的組譯器（Assembler），再度將重複的工作交給電腦，後續又有人將數學等人類易於理解的符號，對應至機械語言。

如此不斷發展，出現了越來越高階的程式語言，到現在，開發者可以用流程、函式、物件等來思考程式設計，免於那些重複性的算式對照工作。

雖說如此，函式、物件等，其實目的仍是在於抽離重複，後者著重在職責、相依性等重複的抽離，進一步發展出設計模式、框架等更龐大的產物，著重在巨觀的商務流程宣告與實作，最終目的是將重複性商務流程瑣事交給框架本身。

至於前者，則是著重在重複演算流程的抽離，只不過在物件導向盛行的大旗之下，演變成先有職責、再有方法（函式）實作，使得能夠發覺重複演算流程，而將之抽離為單一函式的這個動作，相對地，較少被討論了，較常見的場合，大概就剩下對物件導向程式進行重構的幾個場景。

原因或許在於多數開發者，對發覺重複演算流程而將之抽離為單一函式的這個動作，覺得過於簡單而忽視了，因而經常僅止於觀察程式碼在視覺上的重複，而不是真正思考演算流程上是否重複，因而經常寫出重複性的流程而不自知，看到問題，也就不易從更抽象的角度，來思考演算流程。

在我先前專欄〈List處理模式〉中探討過map、filter、fold等模式，就是對觀察演算流程重複的一種初步訓練。當習慣了map、filter的思考模式，遇見問題時，就能反過來察覺問題中是否存在對照、過濾的子問題，如此就不易馬上陷入條件式、迴圈等細節的設計。
然而，對於fold模式，一般開發者較難理解，因為它比map、filter的抽象程度更高，實際上，map、filter都可以基於fold實現，如Haskell中可如下實現：

filter f xs = foldr (\x lt -> if (f x) then (x:lt) else lt) [] xs
map f xs = foldr (\x lt -> f x : lt) [] xs

非函數式語言中的reduce
並不是函數式語言才會存在fold的概念，非函數式語言存在reduce這類API，基本上就是fold實現，之所以稱為reduce，是因為執行一些消減（Reduction）操作從清單中求值的需求，就可以使用這類API。

例如，Java中計算數字清單numbers加總值，一般會用for (int x : numbers) { sum += x; }這類的方式，實際上若將處理過的元素遮住，這個迴圈就像是在逐步消減numbers清單中的元素，因而，亦可使用numbers.stream().reduce(Integer::sum)來求值。

從頭至尾，循序走訪整個清單，以求得一個值的過程，就像是在逐一消減清單求值的過程，都可以使用reduce來解決，因而，在Python中，存在著可處理iter的reduce函式，Ruby中的Array有reduce方法，JavaScript（ECMAScript 5.1）的Array也可以使用reduce（以及reduceRight）。

這類reduce接受的處理函式，左邊參數接受上一次消減操作的結果，右邊參數是當時要處理的元素，開發者往往不易記憶這兩個參數的順序。

如果知道reduce實際上就是foldleft，就不易困擾，在〈List處理模式〉中就實現過foldLeft，因為演算過程就像是從「左」折紙，每次都要從右邊取得下個元素，這也就是為什麼，非函數式語言中的reduce，接受的處理函式右邊參數經常是當時要處理的元素。

既然有fold left，是否有fold right？確實是有！實際上，方才Haskell實現filter、map時使用的foldr，就是fold right，因為其演算過程就像是從「右」折紙，每次都要從左邊取得下個元素，這也就是其接受的lambda，左邊參數是當時要處理的元素之故。

從左折，還是從右折？

非函數式語言常會提供具有fold left概念的reduce API，實際上，從頭至尾循序走訪，是左結合（Left associative）操作。

例如，對內容為1到4的清單做加總，過程相當於(((1 + 2) + 3) + 4)，指定reduce進行加法，總是重複地結合左邊的兩個元素，實際上，加法操作具有結合性（Associative），也就是(((1 + 2) + 3) + 4)與(1 + (2 + (3 + 4)))結果會相同。對於具有結合性的操作，不需要關心使用fold left或fold right。

然而，對於不具結合性的操作，就要留意一下該使用fold left或fold right。例如減法，(((1 - 2) - 3) - 4)與(1 - (2 - (3 - 4)))結果就不同，方才實現filter與map時，若使用foldl，結果就會與一般對filter、map期待的順序相反了；另一個考量是左結合或右結合時，可能造成效率不同的問題，例如，上頭的filter、map，確實是也可以改用foldl：

filter f xs = foldl (\lt x -> if (f x) then (lt ++ [x]) else lt) [] xs
map f xs = foldl (\lt x -> lt ++ [f x]) [] xs

然而在Haskell中，++操作會走訪其左邊的清單，因而在左清單越來越長時，這個版本效率會變差；在Haskell中，foldr還具有處理無限長清單的能力，例如foldr (\ele y -> ele) 0 [1 ..]結果會是1，因為結果與y完全無關，雖是無限清單，然而往最左邊看結果就是1，若是換成了foldl，往右看沒有盡頭，只會跑個沒完沒了，因此，可以使用foldr設計一個可處理無限長清單的any f = (foldr (||) False) . (map f)，執行any (> 3) [1 ..]的運算，然而換成foldl實現，照樣會跑個沒完沒了。

在非函數式語言中，經常處理從頭至尾循序走訪清單的問題，因此，開發者多半不會留意左或右結合問題，然而在平行運算時，就要注意處理指定的函式操作，必須具有結合性的問題，因為清單可能會被切割為數個子清單來處理，例如，在Java中對1到10000的清單做相減處理，使用stream與parallelStream兩者結果就不會相同，因為減法並不具結合律。

恆等值作為起始值的考量

無論是非函數式語言中的reduce，或者是Haskell中的foldl、foldr等，都有可接受起始值設定的版本，在非平行處理的環境中，單純設置一個起始值沒有問題，例如，lt.stream().reduce(5, Integer::sum)，表示以5開始對清單中元素進行相加，然而，在平行環境中就會產生錯的結果，因為清單會被分為子清單，子清單會重複用5做為起始值，使得結果錯誤。

在平行環境中，reduce的值必須是恆等值（Identity），因此，上面的需求可以改為5 + lt.parallelStream().reduce(0, Integer::sum)，這樣結果就會是正確的，因為對於加法這個操作來說，0無論與任何元素結合，結果該是等於該元素，這就是恆等值的定義，類似地，對於乘法操作來說，1就可做為恆等值，如此在平行環境中對子清單進行相乘操作，也不致於發生重複運算問題。

從使用foldr來實現map、filter，到reduce消減求值、考量左結合、右結合，結合律以及恆等值等的過程，都可以從高階的角度來思考待處理的問題，然後反回來讓fold結合某個具體操作，解決實際的問題。

就像方才的any函式，就結合了foldr、||，並與map合成，而達到了想要的結果。高階的抽象思考使得可重用的部份抽取出來，並在必須解題時結合必要實作使之具體化，這是fold由所提供，有別於物件導向方向的抽象訓練。