Fold (高階函式)

在函數語言程式設計中，摺疊，指稱一組高階函式，它們分析遞迴資料結構並透過使用給定組合運算，將遞迴的處理它的構成部件、建造一個返回值的結果重組起來。典型的，要向摺疊提供一個組合函式，一個數據結構的頂端，和可能的在特定條件下使用的某些預設值。摺疊接著以系統性方式使用這個函式，進行組合這個資料結構的層級中的元素。摺疊在某種意義上是的對偶，它接受一個種子值並共遞迴的應用一個函式，來確定如何進一步的構造一個共遞迴的資料結構。摺疊遞迴的分解這個資料結構，在每個節點應用一個組合函式於它的終結值和遞迴結果之上，用得到這個結果替代它。摺疊是，而展開是。作為結構性變換.摺疊可以視為是將資料結構的結構性構件一致性的替代為函式和值。例如在很多函式式語言中，列表是用兩個原語建造的：任何列表要麼是一個空列表，通常叫做codice_1，建立所謂的cons，比如codice_5。可以將在列表上的摺疊看作是將這個列表的末端的codice_1替代為一個特殊的值，並用一個特殊函式替代每個codice_3。使用Haskell作為例子，可以用幾個等式公式化出右摺疊codice_8：foldr :: (a -&gt; b -&gt; b) -&gt; b -&gt; [a] -&gt; bfoldr f z [] = zfoldr f z (x:xs) = f x (foldr f z xs)如果列表為空，結果是初始值codice_9。如果不是空，應用codice_10於第一個元素和摺疊餘下列表的結果。這種替代可以圖示如下：以一致性風格進行結構性變換的另一種方式，左摺疊codice_11：foldl :: (b -&gt; a -&gt; b) -&gt; b -&gt; [a] -&gt; bfoldl f z [] = zfoldl f z (x:xs) = foldl f (f z x) xs如果列表為空，結果是初始值。如果不是空，將應用codice_10於舊初始值和第一個元素的結果作為新初始值，摺疊它和餘下列表。這種替代可以圖示如下：這兩個示意圖展示在一個列表上的右摺疊和左摺疊。逐個元素的使用codice_3構造的列表，每個節點的左連結是終結值，而右連結是另一個節點，右摺疊之後保持這種形態。左摺疊之後，承載函式的每個節點的右連結是終結值，而左連結是另一個節點。這兩個示意圖還突出瞭如下事實：是在列表上的同一函式，因為替代codice_3為codice_3並替代codice_1為codice_1不改變結果。並提示了逆轉一個列表的一種容易的方法：。注意這裡用codice_18函式將給codice_3的二個引數進行了翻轉。codice_18只在Haskell這樣的語言中需要，它翻轉給codice_11的組合函式的實際引數的次序，不像在Scheme中，這裡對codice_11和codice_8二者的組合函式使用相同的實際引數次序。另一個易得的結果是，高階函式map也可以憑藉codice_8書寫，透過將要作用在元素上的那個函式複合於codice_3，即是：map f = foldr ((:) . f) []這裡的點號codice_26是指示的運算元。透過演示線上性列表上的摺疊函式的構造方式，就會得到啟發在其他代數資料型別和結構比如各種樹之上設計類似的摺疊函式。我們可以寫一個高階函式，遞迴的將資料型別的構造子替代為所提供的函式，並將任何這個型別的常量值替代為所提供的值。這種函式一般稱為。在列表上.用加法運算元摺疊列表codice_27會得到結果codice_28, 它是這個列表元素的總和。粗略近似的說，摺疊將這個列表中逗號替代成了codice_29運算，得出了codice_30。在上述的例子中，codice_29是結合律運算，所有最終的結果不管如何加括號都是相同的，儘管括號導致的特定計算次序是不同的。在非結合律二元運算的一般情況下，組合元素的次序可以影響最終的結果值。在列表之上，有二個面向的進行這個工作的方式：要麼組合第一個元素和遞迴的組合餘下列表的結果。著對應於一個二元運算元要麼是右結合的要麼是左結合的，採用了Haskell或Prolog的術語。使用右摺疊，合計將加括號為codice_32，而使用左摺疊它將加括號為codice_33。實際上，在使用右摺疊的情況下有一個初始值同列表的最後一個元素組合，在使用左摺疊的情況下有一個初始值同和列表的第一個元素組合，是方便和自然的。在上述的例子中，值codice_34作為初始值，這將得出codice_38。在組合函式codice_10的型別是不對稱的情況下，比如codice_40，就是說如果結果的型別不同於列表元素的型別，使用初始值是必需的。要使一個線性的應用鏈成為可能，使用的這個初始值的型別必須同於codice_10的結果的型別。不管是右摺疊還是左摺疊，它的型別都確定為組合函式的引數所預期的型別。如果第二個引數必須與結果相同型別，則codice_10可以被看作是右結合的，如果是第一個引數則為左結合的。那些使用對稱型別二元運算的摺疊，它的二個引數的型別和它的結果的型別必須相同。樹狀摺疊.在組合函式是個原群的情況下，就是說它的型別是對稱的，比如codice_43，就是說結果的型別同於列表元素的型別，則可以用任意方式放置括號，因而建立巢狀子表示式的“樹”，比如codice_44。如果二元運算codice_10是結合律的，則這個值將是良好定義的，就是對於任何加括號情況，都是相同的，儘管如何計算它的運算細節會是不同的。如果codice_10是非嚴格求值的，這可能在效能上有重大影響。線性摺疊是面向節點的，並以一致方式對列表的每個節點進行運算；而樹狀摺疊是面向整個列表的，並以一致方式跨越節點“群”進行運算。列表可以按樹狀風格來摺疊，分別對於有限和不明確定義的列表二者：foldt :: (a -&gt; a -&gt; a) -&gt; a -&gt; [a] -&gt; afoldt f z [] = zfoldt f z [x] = f x zfoldt f z xs = foldt f z (pairs f xs)foldi :: (a -&gt; a -&gt; a) -&gt; a -&gt; [a] -&gt; afoldi f z [] = zfoldi f z (x:xs) = f x (foldi f z (pairs f xs))pairs :: (a -&gt; a -&gt; a) -&gt; [a] -&gt; [a]pairs f (x:y:t) = f x y : pairs f tpairs _ t = t在codice_47函式的情況下，為了避免在不明確定義的列表上失控求值，函式codice_10必須“不總是”需求它的第二個引數的值，至少不是所有都要，或者不是立即就要。非空列表的特殊摺疊.人們經常希望選擇codice_10的單位元作為初始值codice_9。在沒有合適的初始值的時候，例如在想要把計算它的二個引數的極大值的函式，摺疊到一個非空列表之上，來得到這個列表的極大值，可以用codice_8和codice_11的變體，它們分別使用這個列表的最後一個和第一個元素作為初始值。在Haskell和其他一些語言中，它們叫做codice_53和codice_54，這裡的“1”所指的是自動提供初始元素，和它們所應用到的列表至少要有一個元素的事實。foldl1 f [x] = xfoldl1 f (x:y:xs) = foldl1 f (f x y : xs)foldr1 f [x] = xfoldr1 f (x:xs) = f x (foldr1 f xs)foldt1 f [x] = xfoldt1 f (x:y:xs) = foldt1 f (f x y : pairs f xs)foldi1 f [x] = xfoldi1 f (x:xs) = f x (foldi1 f (pairs f xs))例子.使用Haskell直譯器，摺疊進行的結構性變換可以用構造一個字串來展示：λ&gt; foldr (\x y -&gt; concat ["(",x,"+",y,")"]) "0" (map show [1..13])"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"λ&gt; foldl (\x y -&gt; concat ["(",x,"+",y,")"]) "0" (map show [1..13])"(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"λ&gt; foldt (\x y -&gt; concat ["(",x,"+",y,")"]) "0" (map show [1..13])"(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)"λ&gt; foldi (\x y -&gt; concat ["(",x,"+",y,")"]) "0" (map show [1..13])"(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"無限樹狀摺疊，可以用Haskell的透過埃拉託斯特尼篩法的遞迴素數生成來演示：primes = 2 : _Y ((3 :) . minus [5,7..] . foldi (\(x:xs) ys -&gt; x : union xs ys) []. map (\p-&gt; [p*p, p*p+2*p..]))_Y g = g (_Y g) -- = g . g . g . g . ...這裡的函式codice_55以本地方式運算於有序列表之上來高效的產生它們的並集，而codice_56 做它們的集合差。對於有限列表，歸併排序可以使用樹狀摺疊輕易的定義為：mergesort xs = foldt merge [] x  f) undefined (repeat undefined)