在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由所提供,有別於物件導向方向的抽象訓練。

作者簡介


Advertisement

更多 iThome相關內容