檢視 Fold(高階函式) 的原始碼

佇函式的語言程式設計內底，'''拗疊'''（fold）， 嘛叫做'''歸約'''（reduce）、'''疊累'''（accumulate）、'''聚集'''（aggregate）、'''壓縮'''（compress）抑是'''注入'''（inject）， 指稱一組高階函式，𪜶分析遞迴資料結構並通過使用予定組合運算，共遞迴的處理伊的構成部件、建造一个倒轉去值的結果重組起來。典型的，欲向拗仔提供一个組合函式，一个資料結構的頂五節點，佮可能佇咧特定條件之下使用的某一寡預設值。拗疊了以系統性的方式來使用這个函式，進行組合這个資料結構層級中的元素。

拗落去某一種意義展開（unfold）的嘿尪仔，伊接受一个種子值並共遞迴的應用一个函式，來確定按怎進一步的構造一个共遞迴的資料結構。拗拗迴的分解這个資料結構，佇咧每一个節點應用一个組合函式來算伊的總結值佮遞迴結果之上，用會著這結果替代伊。拗拗是 catamorphism，展開是 anamorphism。

==做結構性變換==

拗冊會當看做是將資料結構的結構性構件一致性的替代為函式和值。若像咧足濟函數式的語言內底，列表是用兩个原底來起的：任何列表欲按怎是一个空串列，通常號做 ` nil `（` [ ] `）， 若是通過將一个元素字首於另外一个列表進前來構造的，通過應用 ` cons ` 函式（佇咧 Haskell 寫為冒號 ` ( : ) `）， 建立所謂的 cons 節點，比如講 ` Cons ( X 一 , Cons ( X 二 , Cons ( . . . ( Cons ( Xn , nil ) ) ) ) ) `。會當將佇列表頂懸的拗看作是將這个列表的尾仔的 ` nil ` 替代為一个特殊的值，用一个特殊函式替代逐个 ` cons `。

使用 Haskell 做例，會當用幾个等式公式化出正拗疊 ` foldr `：

若列表做空，結果是初初 ` z `。若毋是空，應用 ` f ` 佇頭一个元素佮拗疊落列表的結果。這種替代會當圖示如下：


: :

用一致性風格來進行結構性變換的另外一種方式，倒拗拗 ` foldl `：

若列表做空，結果是初初。若毋是空，來共應用 ` f ` 佇咧舊初始值佮第一个元素的結果是新初初，拗疊伊佮餘下列表。這種替代會當圖示如下：


: :

這兩个示意圖展示佇一个列表頂懸的正拗疊和倒拗疊。每一個元素的使用 ` cons ` 構造的列表，逐个節點的左連結是終結值，正經連結是另外一个節點，正拗拗了後保持這个形態。倒拗拗仔疊了，承載函式的每一个節點的正連結是終結值，佇倒連結是另外一个節點。

這兩个示意圖閣吐出來矣如下事實：` id=foldr ( : ) [] ` 是咧列表頂懸的仝一函式（揤 Lisp 講法是「淺層複製」）， 因為替代 ` cons ` 為 ` cons ` 並替代 ` nil ` 為 ` nil ` 無愛改變結果。並提示倒反一个列表的一種簡單的方法：` reverse=foldl ( flip ( : ) ) [] `。注意遮用 ` flip ` 函式將會 ` cons ` 的兩个參數進行矣改變。` flip ` 只在 Haskell 按呢的語言內底需要，伊掀轉予 ` foldl ` 的組合函式的實際參數的次序，無成佇咧 Scheme 中，遮嘿 ` foldl ` 和 ` foldr ` 二者的組合函式使用仝款的實際參數次序。

另外一个易得的結果是，高階函式 map 嘛會當憑藉 ` foldr ` 書寫，通過將愛作用佇元素上的彼个函式來複合著 ` cons `，即是：

遮的點號 ` ( . ) ` 是指示函式複合的算子。

通過演示線頂性列表頂的痕疊函式的構造方式，就會得著啟發佇其他的代數資料類型佮結構比如講各種的樹仔頂頭的設計類似的拗疊函式。咱會當寫一个高階函式，遞迴的將資料類型的構造子替代為所提供的函式，並且將任何這個類型的常數值替代為所提供的值。這種函式一般號做 catamorphism。

==咧列表頂懸==

用加法算子拗疊列表 ` [一 , 二 , 三 , 四 , 五] ` 會得著結果 ` 十五 ` , 伊是這个列表元素的總和。粗略近近的講，拗拗將這个列表中弄號替代變成 ` + ` 運算，會出得矣 ` 一 + 二 + 三 + 四 + 五 `。

咧講的這个例中間，` + ` 是結合律運算，所有的最終的結果不管如何加括號攏是仝款的，儘管括號致使的特定計算次序是無仝的。佇咧非結合律二元運算的一般情況下，組合元素的次序會當影響上尾的結果值。咧列表之上，有兩个面向的咧進行這个工作的方式：欲按怎組合第一个元素佮交迴的組合下列表的結果（叫做正摺摺）， 欲按怎組合交迴的組合除了最後一个元素的所有元素的結果佮最後一个元素（叫做倒拗拗）。 著著應於一个二元算子愛多是正結合的愛哪會是左結合的，採用矣 Haskell 抑是 Prolog 的術語。使用正拗疊，合計將加括號做 ` 一 + ( 二 + ( 三 + ( 四 + 五 ) ) ) `，而使用倒拗疊伊會加括號做 ` ( ( ( 一 + 二 ) + 三 ) + 四 ) + 五 `。

實際上，咧使用正拗疊的狀況下有一个初初值同列表的最後一个元素組合，佇咧使用倒拗疊的狀況下有一个初初的值同佮列表的頭一个元素組合，是方便佮自然的。咧講的這个例中間，值 ` 零 `（加法單位元）會當選擇做初初，嘿著正拗拗會著 ` 一 + ( 二 + ( 三 + ( 四 + ( 五 + 零 ) ) ) ) `，嘿著倒拗拗會著 ` ( ( ( ( 零 + 一 ) + 二 ) + 三 ) + 四 ) + 五 `。對乘法，選擇 ` 一 `（乘法單位元）作為初始值，這將會出 ` 一 * 一 * 二 * 三 * 四 * 五=百二=五 ! `。

佇組合函式 ` f ` 伊的類型是毋是稱呼的狀況下，比如講 ` a-> b-> b `，就是講若結果彼个類型無仝列表元素的類型，使用初始值是必須的。愛使一个線性的應用鏈成做可能，使用的這个初初值的類型著愛仝 ` f ` 的結果的類型。毋管是正拗抑是倒拗拗，伊的類型攏確定做組合函式的參數所預期的類型。若第二个參數著愛佮結果仝類型，著 ` f ` 會當予人看做是正結合的，若是第一个參數則為倒結合的。遐的使用對稱類型二元運算的拗疊，伊的兩个參數的類型佮伊的結果的類型著愛相𫝛。

===樹狀拗仔===

佇組合函式是一个原群的狀況下，就是講伊的類型是一个對稱的，比如講 ` a-> a-> a `，就是講結果的類型佮列表元素的類型，會當用任意方式共你囥括號，因為建立岫狀子表達式的「樹」，比如講 ` ( ( 一 + 二 ) + ( 三 + 四 ) ) + 五 `。若是二箍運算乎 ` f ` 是結合律的，則這个值將是良好定義的，就是對任何加括號情形，攏是相仝的，就算講按怎計算伊的運算細節會是無仝款的。若是 ` f ` 是非嚴格求值的，這可能佇效能有一个影響真正的。
線性拗這是向節點，並且用一致方式來對列表的逐个節點進行運算；伊彼樹狀拗拗是彼面向規个列表的，並且用一致的方式迒過節點「群」進行運算。

列表按呢會當揤樹狀風格來摺摺，分別對有限佮不明確定義的列表二者：

佇咧 ` foldi ` 函式的狀況下，為著避免佇咧不明確定義的列表頂懸失控求值，函式 ` f ` 著愛「無總是」需求伊的第二个參數的值，上少毋是講所有的攏愛，抑是毋是隨著愛。

===非空串列的特殊拗疊===

人四常希望選擇 ` f ` 的單位元作為初始值 ` z `。佇咧無合的初初咧值的時陣，譬如講佇想欲共伊的兩个參數的極大值的函式，拗落來到一个非空串列以上，來得著這个列表的極大值，會用得 ` foldr ` 和 ` foldl ` 的變體，𪜶分別使用這列表的上尾仔一个和頭一个元素作為初初開始值。佇咧 Haskell 佮其他一寡彼號語言內底，𪜶叫做 ` foldr 一 ` 和 ` foldl 一 `，遮的「一」所指出來是自動提供初初的元素，佮𪜶所應用著的列表至少愛有一个元素的事實。

===例===

使用 Haskell 直譯器，拗疊進行的結構性變換會當用構造一字串來展示：

無限樹狀拗疊，會用得 Haskell 的通過埃拉托斯特尼篩法的遞迴素數生成來演示：

遮的函式 ` union ` 以這个地方式運算是有序列表面起來是高效的產生𪜶的併集，而且 ` minus ` 做𪜶的集合差。

對有限列表，合併排序（和伊的去除這个重複變體 ` nubsort `）會當使用樹狀拗疊輕易的定義做：

用的函式 ` merge ` 是 ` union ` 的保留重複的變體。

函式 ` head ` 和 ` last ` 嘛會當通過拗疊定義做：

===求值次序考慮===

佇採用閣慢性非嚴格求值策略的場合下，` foldr ` 將隨倒轉來 ` f ` 佇列表頭殼和拗疊下跤列表的遞迴案例頂懸的這个應用。所以，若是 ` f ` 會當產生其實結果的一部份，煞無需要參照著遞迴的案例，伊佇咧 ` f ` 的「正」也就是講第二个實際的參數上，賰的結果永遠無需要，遐爾仔交迴就會停止，譬如講上節定義的 ` head ` 函式。這允准正拗疊會當運算佇無限列表頂懸。佮之相反，` foldl ` 將隨的呼叫具有新參數的家己本身，到甲伊有達到矣列表的尾溜。彼尾遞迴會當高效的編譯為迴圈，毋過根本就袂當處理無限列表，伊會永久遞迴於無限迴圈。

已經到達列表的尾仔了後，` foldl ` 有效的起造一个「表達式」，伊是岫狀的左深化 ` f ` 應用，伊予提供予呼叫者進行求值。若函式的 ` f ` 代先參照伊的第二个參數，並且會當產生其實結果的一部份，煞無需要參照著遞迴的案例，遮是佇伊的「倒」也就是講第一个實際的參數上，遐爾仔交迴會停止，譬如講上節定義的 ` last ` 函式。這意味著就算 ` foldr ` 遞迴「佇正手爿」，伊允准伊性組合函式來對左至右檢查列表的元素；顛倒反起來，就算講 ` foldl ` 遞迴「佇倒爿邊仔」，伊允准伊性組合函式對正至左檢查列表的元素。

倒反一个列表嘛是尾遞迴的，伊會當使用 ` rev=foldl ( \ ys x-> x : ys ) [ ] ` 實現。佇有限列表頂懸，這意味倒拗疊和倒斡會當複合起來以尾遞迴方式進行正拗疊，通過修改 ` f ` 使伊倒反其參數的次序，比如講 ` foldr f z==foldl ( flip f ) z . rev `，按呢尾遞迴的建造出的一个表達式的表示仝款正拗所起的。

額外的中央列表結構會當通過形似傳達續體風格的手段去除：` foldr f z xs==foldl ( \ k x-> k . f x ) id xs z `；另外一个咧嘛類似：` foldl f z xs==foldr ( \ x k-> k . flip f x ) id xs z `。𪜶嘛定定予人寫為：

另外一个工夫愛點是，佇咧使用伊貧性求值得的倒拗疊的情況下，新初初開始化參數咧進行遞迴呼叫進前是無被求值的。佇咧達到列表的尾溜並且試計算結果的誠大的表達式的時陣，這可能致使疊甲滿位。為此，這種語言不時提供倒拗摺的閣較嚴格變體，伊咧進行遞迴呼叫進前強制的求值初始化參數。佇咧 Haskell 中伊是 Data . List 庫里的 ` foldl'` 函式（注意這个撇號讀做「prime」）。 需要意識著一个事實，強制一个值用慢性資料構造子建造，其實袂自動的強制伊的構件。結合佇咧尾遞迴，這種拗疊接近了迴圈的效率，佇閣慢性求值的最後結果是無可能抑無可取的時陣，確定著愛恆定空間算。

==佇各種的語言內底==

==普遍性==

拗式的是多型函式。對於有如下按呢定義的任何 ` g `：

` g ` 攏會當表達為：

閣有，無法度組合子會當通過拗拗實現，證明迵天會當予人歸約做摺摺：

==參見==

* 聚集函式
* 迵天代二箍關係
* Map ( 高階函式 )
* Filter ( 高階函式 )
* 字條和
* 遞迴資料類型
* 遞迴算子
* 遞迴 ( 電腦科學 )

==參照==

==外部連結==

* " Unit 六 : The Higher-order fold Functions "
* HaskellWiki : Fold

[[分類: 待校正]]