Fold_(高阶函数)

在函式語言程式設計中，**摺疊**（fold），也稱為**歸約**（reduce）、**積累**（accumulate）、**聚集**（aggregate）、**壓縮**（compress）或**注入**（inject），指稱一組高階函式，它們分析遞迴資料結構並通過使用給定組合運算，將遞迴的處理它的構成部件、建造一個返回值的結果重組起來。典型的，要向摺疊提供一個組合函式，一個資料結構的頂端節點，和可能的在特定條件下使用的某些預設值。摺疊接著以系統性方式使用這個函式，進行組合這個資料結構的層級中的元素。

摺疊在某種意義上是展開（unfold）的對偶，它接受一個種子值並共遞迴的應用一個函式，來確定如何進一步的構造一個共遞迴的資料結構。摺疊遞迴的分解這個資料結構，在每個節點應用一個組合函式於它的終結值和遞迴結果之上，用得到這個結果替代它。摺疊是 catamorphism，而展開是 anamorphism。

## 作為結構性變換

摺疊可以視為是將資料結構的結構性構件一致性的替代為函式和值。例如在很多函數式語言中，列表是用兩個原語建造的：任何列表要麼是一個空串列，通常叫做 `nil`（`[]`），要麼是通過將一個元素字首於另一個列表之前來構造的，通過應用 `cons` 函式（在 Haskell 中寫為冒號 `(:)`），建立所謂的 cons 節點，比如 `Cons(X1,Cons(X2,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。

## 在列表上

用加法算子摺疊列表 `[1,2,3,4,5]` 會得到結果 `15`, 它是這個列表元素的總和。粗略近似的說，摺疊將這個列表中逗號替代成了 `+` 運算，得出了 `1 + 2 + 3 + 4 + 5`。

在上述的例子中，`+` 是結合律運算，所有最終的結果不管如何加括號都是相同的，儘管括號導致的特定計算次序是不同的。在非結合律二元運算的一般情況下，組合元素的次序可以影響最終的結果值。在列表之上，有二個面向的進行這個工作的方式：要麼組合第一個元素和遞迴的組合餘下列表的結果（叫做右摺疊），要麼組合遞迴的組合除了最後一個元素的所有元素的結果和最後一個元素（叫做左摺疊）。著對應於一個二元算子要麼是右結合的要麼是左結合的，採用了 Haskell 或 Prolog 的術語。使用右摺疊，合計將加括號為 `1 + (2 + (3 + (4 + 5)))`，而使用左摺疊它將加括號為 `(((1 + 2) + 3) + 4) + 5`。

實際上，在使用右摺疊的情況下有一個初始值同列表的最後一個元素組合，在使用左摺疊的情況下有一個初始值同和列表的第一個元素組合，是方便和自然的。在上述的例子中，值 `0`（加法單位元）可以被選擇為初始值，對於右摺疊得到 `1 + (2 + (3 + (4 + (5 + 0))))`，對於左摺疊得到 `((((0 + 1) + 2) + 3) + 4) + 5`。對於乘法，選擇 `1`（乘法單位元）作為初始值，這將得出 `1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!`。 

在組合函式 `f` 的類型是不對稱的情況下，比如 `a -> b -> b`，就是說如果結果的類型不同於列表元素的類型，使用初始值是必需的。要使一個線性的應用鏈成為可能，使用的這個初始值的類型必須同於 `f` 的結果的類型。不管是右摺疊還是左摺疊，它的類型都確定為組合函式的參數所預期的類型。如果第二個參數必須與結果相同類型，則 `f` 可以被看作是右結合的，如果是第一個參數則為左結合的。那些使用對稱類型二元運算的摺疊，它的二個參數的類型和它的結果的類型必須相同。

### 樹狀摺疊

在組合函式是個原群的情況下，就是說它的類型是對稱的，比如 `a -> a -> a`，就是說結果的類型同於列表元素的類型，則可以用任意方式放置括號，因而建立巢狀子表達式的「樹」，比如 `((1 + 2) + (3 + 4)) + 5`。如果二元運算 `f` 是結合律的，則這個值將是良好定義的，就是對於任何加括號情況，都是相同的，儘管如何計算它的運算細節會是不同的。如果 `f` 是非嚴格求值的，這可能在效能上有重大影響。
線性摺疊是面向節點的，並以一致方式對列表的每個節點進行運算；而樹狀摺疊是面向整個列表的，並以一致方式跨越節點「群」進行運算。

列表可以按樹狀風格來摺疊，分別對於有限和不明確定義的列表二者：

在 `foldi` 函式的情況下，為了避免在不明確定義的列表上失控求值，函式 `f` 必須「不總是」需求它的第二個參數的值，至少不是所有都要，或者不是立即就要。

### 非空串列的特殊摺疊

人們經常希望選擇 `f` 的單位元作為初始值 `z`。在沒有合適的初始值的時候，例如在想要把計算它的二個參數的極大值的函式，摺疊到一個非空串列之上，來得到這個列表的極大值，可以用 `foldr` 和 `foldl` 的變體，它們分別使用這個列表的最後一個和第一個元素作為初始值。在 Haskell 和其他一些語言中，它們叫做 `foldr1` 和 `foldl1`，這裡的「1」所指的是自動提供初始元素，和它們所應用到的列表至少要有一個元素的事實。

### 例子

使用 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 6: The Higher-order fold Functions" （頁面存檔備份，存於網際網路檔案館）
* HaskellWiki: Fold （頁面存檔備份，存於網際網路檔案館）