Fold (高階函數)

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

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

## 作為結構性變換

摺疊可以視為是將數據結構的結構性構件一致性的替代為函數和值。例如在很多函數式語言中，列表是用兩個原語建造的：任何列表要麼是一個空列表，通常叫做`nil`（`[]`），要麼是通過將一個元素前綴於另一個列表之前來構造的，通過應用`cons`函數（在Haskell中寫為冒號`(:)`），建立所謂的cons節點 (電腦科學)，比如`Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil)))))`。可以將在列表上的摺疊看作是將這個列表的末端的`nil`替代為一個特殊的值，並用一個特殊函數替代每個`cons`。

使用Haskell作為例子，可以用幾個等式公式化出右摺疊`foldr`：

```haskell
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)
```

如果列表為空，結果是初始值`z`。如果不是空，應用`f`於第一個元素和摺疊餘下列表的結果。這種替代可以圖示如下：

<image>

以一致性風格進行結構性變換的另一種方式，左摺疊`foldl`：

```haskell
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs
```

如果列表為空，結果是初始值。如果不是空，將應用`f`於舊初始值和第一個元素的結果作為新初始值，摺疊它和餘下列表。這種替代可以圖示如下：

<image>

這兩個示意圖展示在一個列表上的右摺疊和左摺疊。逐個元素的使用`cons`構造的列表，每個節點的左連結是終結值，而右連結是另一個節點，右摺疊之後保持這種形態。左摺疊之後，承載函數的每個節點的右連結是終結值，而左連結是另一個節點。

這兩個示意圖還突出了如下事實：id = foldr (:) 是在列表上的同一函數（按Lisp說法是「淺層複製」），因為替代`cons`為`cons`並替代`nil`為`nil`不改變結果。並提示了逆轉一個列表的一種容易的方法：reverse = foldl (flip (:))。注意這裡用`flip`函數將給`cons`的二個參數進行了翻轉。`flip`只在Haskell這樣的語言中需要，它翻轉給`foldl`的組合函數的實際參數的次序，不像在Scheme中，這裡對`foldl`和`foldr`二者的組合函數使用相同的實際參數次序。

另一個易得的結果是，高階函數map也可以憑藉`foldr`書寫，通過將要作用在元素上的那個函數複合於`cons`，即是：

```haskell
map f = foldr ((:) . f) []
```

這裡的點號`(.)`是指示函數複合 (電腦科學)的算子。

通過演示在線性列表上的摺疊函數的構造方式，就會得到啟發在其他代數數據類型和結構比如各種樹之上設計類似的摺疊函數。我們可以寫一個高階函數，遞歸的將數據類型的構造子替代為所提供的函數，並將任何這個類型的常量值替代為所提供的值。這種函數一般稱為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`是非嚴格求值的，這可能在效能上有重大影響。

線性摺疊是面向節點的，並以一致方式對列表的每個節點進行運算；而樹狀摺疊是面向整個列表的，並以一致方式跨越節點「群」進行運算。

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

```haskell
foldt :: (a -> a -> a) -> a -> [a] -> a
foldt f z []     = z
foldt f z [x]    = f x z
foldt f z xs     = foldt f z (pairs f xs)

foldi :: (a -> a -> a) -> a -> [a] -> a 
foldi f z []     = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))

pairs :: (a -> a -> a) -> [a] -> [a] 
pairs f (x:y:t)  = f x y : pairs f t
pairs _ t        = t
```

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

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

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

```haskell
foldl1 f [x]      = x
foldl1 f (x:y:xs) = foldl1 f (f x y : xs)

foldr1 f [x]      = x
foldr1 f (x:xs)   = f x (foldr1 f xs)

foldt1 f [x]      = x
foldt1 f (x:y:xs) = foldt1 f (f x y : pairs f xs)
 
foldi1 f [x]      = x
foldi1 f (x:xs)   = f x (foldi1 f (pairs f xs))
```

### 例子

使用Haskell解釋器，摺疊進行的結構性變換可以用構造一個字串來展示：

```haskell
λ> foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"
 
λ> foldl (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"
 
λ> foldt (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)"
 
λ> foldi (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"
```

無限樹狀摺疊，可以用Haskell的通過埃拉托斯特尼篩法的遞歸素數生成來演示：

```haskell
primes = 2 : _Y ((3 :) . minus [5,7..] . foldi (\(x:xs) ys -> x : union xs ys) [] 
                       . map (\p-> [p*p, p*p+2*p..]))
_Y g = g (_Y g)     -- = g . g . g . g . ...
```

這裡的函數`union`以本地方式運算於有序列表之上來高效的產生它們的併集，而`minus` 做它們的集合差。

對於有限列表，歸併排序（和它的去除重複變體`nubsort`）可以使用樹狀摺疊輕易的定義為：

```haskell
mergesort xs = foldt merge [] [[x] | x <- xs]
nubsort   xs = foldt union [] [[x] | x <- xs]
```

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

函數`head`和`last`也可以通過摺疊定義為：

```haskell
head = foldr (\x r -> x) (error "head: Empty list")
last = foldl (\a x -> x) (error "last: Empty list")
```

### 求值次序考慮

在採用惰性或非嚴格求值策略的場合下，`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
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z xs = foldl (\k x y -> k (f x y)) id xs z

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z xs = foldr (\x k y -> k (f y x)) id xs z
```

另一個技術要點是，在使用惰性求值的左摺疊的情況下，新初始化參數在進行遞歸調用之前是不被求值的。在達到了列表末端並嘗試計算結果的巨大的表達式的時候，這可能導致堆棧溢出。為此，這種語言經常提供左摺疊的更嚴格變體，它在進行遞歸調用之前強制的求值初始化參數。在Haskell中它是Data.List庫里的`foldl'`函數（注意這個撇號讀作「prime」）。需要意識到一個事實，強制一個值用惰性數據構造子建造，其自身不會自動的強制它的構件。結合於尾遞歸，這種摺疊接近了循環的效率，在惰性求值的最終結果是不可能或不可取的時候，確保了恆定空間運算。

## 在各種語言中

語言｜左fold｜右fold｜無初始值左fold｜無初始值右fold｜Unfold｜注釋

APL｜`''func''⍨/⌽''initval'',''vector''`｜`''func''/''vector'',''initval''`｜`''func''⍨/⌽''vector''`｜`''func''/''vector''`

C# 3.0｜`''ienum''<wbr/>.Aggregate(''initval'', ''func'')`｜`''ienum''.Reverse()<wbr/>.Aggregate(''initval'', ''func'')`｜`''ienum''<wbr/>.Aggregate(''func'')`｜`''ienum''.Reverse()<wbr/>.Aggregate(''func'')`｜Aggregate是擴展方法 ienum是`IEnumerable<T>`在所有的.NET語言中都類似

C++｜`std::accumulate(<wbr/>''begin'', ''end'', ''initval'', ''func'')`｜`std::accumulate(<wbr/>''rbegin'', ''rend'', ''initval'', ''func'')`｜在頭文件 `<numeric>`中begin, end, rbegin, rend是迭代器func可以是一個函數指針或函數對象

C++17｜`(''initval'' ''op'' ... ''op'' ''pack'')`｜`(''pack'' ''op'' ... ''op'' ''initval'')`｜`(... ''op'' ''pack'')`｜`(''pack'' ''op'' ...)`｜Fold表達式（只用於變元函數模板）：op是二元算子（兩個op必須相同，比如`(std::cout << ... << args)`)， pack是未展開的參數包。

ColdFusion標記語言｜`obj.reduce(func,initial)`｜`obj.reduce(func)`｜這裡的`func`接受為實際參數的是前面運算的結果（或在第一次迭代上的`initial`值）；當前項；當前項的索引或鍵；和到`obj`的引用。

Clojure｜`(reduce ''func'' ''initval'' ''list'')`｜`(reduce ''func'' ''initval'' (reverse ''list'))`｜`(reduce ''func'' ''list'')`｜`(reduce ''func" (reverse ''list''))`｜參見clojure.core.reducers/fold

Common Lisp｜`(reduce ''func'' ''list'' :initial-value ''initval'')`｜`(reduce ''func'' ''list'' :from-end t :initial-value ''initval'')`｜`(reduce ''func'' ''list'')`｜`(reduce ''func'' ''list'' :from-end t)`

Curl｜`TreeNode.''default'' ''treeNode'' ...} ''.to-Iterator''}`｜`TreeNode.''default'' ''treeNode'' ...} ''.reverse}<wbr/>.to-Iterator''}`｜`{for {treeNode''<wbr/>.to-Iterator}'' ''do}''`｜`{for treeNode.reverse}''<wbr/>.to-Iterator}'' ''do}''`｜還有DefaultListModel和HashTable實現`to-Iterator`

D｜`reduce!''func''(''initval'', ''list'')`｜`reduce!''func''(''initval'', ''list''<wbr/>.reverse)`｜`reduce!''func''(''list'')`｜`reduce!''func''(<wbr/>''list''.reverse)`｜在模塊`std.algorithm`中

Elixir｜`List.foldl(list, acc, fun)`｜`List.foldr(list, acc, fun)`｜樣例用法見於documentation

Elm｜`List.foldl(''Fun'', ''Accumulator'', ''List'')`｜`List.foldr(''Fun'', ''Accumulator'', ''List'')`｜參見List API

Erlang｜`lists:foldl(''Fun'', ''Accumulator'', ''List'')`｜`lists:foldr(''Fun'', ''Accumulator'', ''List'')`

F#｜`Seq/List.fold ''func'' ''initval'' ''list''`｜`List.foldBack ''func'' ''list'' ''initval''`｜`Seq/List.reduce ''func'' ''list''`｜`List.reduceBack ''func'' ''list''`｜`Seq.unfold ''func'' ''initval''`

Gosu (程式語言)｜Iterable.fold(f(agg, e))Iterable.reduce(init, f(agg, e)) Iterable.partition(f(e)) ｜都是在java的Iterable接口上的擴展方法，陣列也支持。

Groovy｜`''list''<wbr/>.inject(''initval'', ''func'')`｜`''list''.reverse()<wbr/>.inject(''initval'', ''func'')`｜`''list''<wbr/>.inject(''func'')`｜`''list''.reverse()<wbr/>.inject(''func'')`

Haskell｜`foldl ''func'' ''initval'' ''list''`｜`foldr ''func'' ''initval'' ''list''`｜`foldl1 ''func'' ''list''`｜`foldr1 ''func'' ''list''`｜`unfoldr ''func'' ''initval''`｜對於foldl，摺疊函數接受參數的次序與foldr的次序相反。

Haxe｜`Lambda.fold(''iterable'', ''func'', ''initval'')`

J｜verb`~/|.` initval,array｜`''verb''/ ''array'',''initval''`｜verb`~/|.` array｜`''verb''/ ''array''`｜u/y應用二元u於y的項目之間。參見"J Dictionary: Insert"

Java 8+｜`''stream''.reduce<wbr/>(''initval'', ''func'')`｜`''stream''.reduce<wbr/>(''func'')`

JavaScript 1.8ECMAScript 5｜`''array''.reduce<wbr/>(''func'', ''initval'')`｜`''array''.reduceRight<wbr/>(''func'', ''initval'')`｜`''array''.reduce<wbr/>(''func'')`｜`''array''.reduceRight<wbr/>(''func'')`

Julia｜`foldl(''op'', ''itr''; [init])`｜`foldr(''op'', ''itr''; [init])`｜`foldl(''op'', ''itr'')`｜`foldr(''op'', ''itr'')`

Kotlin｜`''Iterable''.fold<wbr />(''initval'', ''func'')`｜`''Iterable''.foldRight<wbr />(''initval'', ''func'')`｜`''Iterable''.reduce''(func'')`｜`Iterable``.reduceRight''(func'')`｜其他搜集也支持`fold`和`reduce`。還有`Result.fold(onSuccess, onFailure)`，它歸約`Result<T>`（要麼成功要麼失敗）成`onSuccess`和`onFailure`的返回類型。

LFE (程式語言)｜`(lists:foldl ''func'' ''accum'' ''list'')`｜`(lists:foldr ''func'' ''accum'' ''list'')`

Logtalk｜`fold_left(Closure, Initial, List, Result)`｜`fold_right(Closure, Initial, List, Result)`｜meta標準庫對象提供元謂詞。縮寫foldl和foldr也可以使用。

Maple｜`foldl(''func'', ''initval'', ''sequence'')`｜`foldr(''func'', ''initval'', ''sequence'')`

Mathematica｜`Fold[''func'', ''initval'', ''list'']`｜`Fold[''func'', ''initval'', Reverse[''list'']]`｜`Fold[''func'', ''list'']`｜`Fold[''func'', Reverse[''list'']]`｜`NestWhileList[''func,'', ''initval'', ''predicate'']`｜不帶初始值的`Fold`在版本10.0和更高版本中支持。

MATLAB｜`fold(@''func'', ''list'', ''defaultVal'')`｜`fold(@''func'', flip(''list''), ''defaultVal'')`｜`fold(@''func'', ''list'')`｜`fold(@''func'', flip(''list''))`｜要求Symbolic Math Toolbox，從R2016b開始支持。

Maxima｜`lreduce(''func'', ''list'', ''initval'')`｜`rreduce(''func'', ''list'', ''initval'')`｜`lreduce(''func'', ''list'')`｜`rreduce(''func'', ''list'')`

Mythryl｜`fold_left ''func'' ''initval'' ''list''<br /> vector::fold_left ''func'' ''initval'' ''vector''`｜`fold_right ''func'' ''initval'' ''list''<br /> vector::fold_right ''func'' ''initval'' ''vector''`｜提供的函數接受在元組中實際參數。

OCaml｜`List.fold_left ''func'' ''initval'' ''list''<br /> Array.fold_left ''func'' ''initval'' ''array''`｜`List.fold_right ''func'' ''list'' ''initval''<br /> Array.fold_right ''func'' ''array'' ''initval''`｜`Base.Sequence.unfold ''~init'' ''~f''`

PARI/GP｜`fold( ''f'', ''A'' )`

Perl｜`reduce ''block'' ''initval'', ''list''`｜`reduce ''block'' ''list''`｜在`List::Util`模塊中

PHP｜`array_reduce(''array'', ''func'', ''initval'')`｜`array_reduce(<wbr/>array_reverse(''array''), ''func'', ''initval'')`｜`array_reduce(''array'', ''func'')`｜`array_reduce(<wbr/>array_reverse(''array''), ''func'')`｜在未提供initval的時候，使用了NULL，所以不是真正的foldl1。在PHP 5.3之前，initval只能是整數。func是一個callback。參見在線的array_reduce文檔。

Python 2.x｜`reduce(''func'', ''list'', ''initval'')`｜`reduce(lambda x,y: ''func''(y,x), reversed(''list''), ''initval'')`｜`reduce(''func'', ''list'')`｜`reduce(lambda x,y: ''func''(y,x), reversed(''list''))`

Python 3.x｜`functools.reduce(''func'', ''list'', ''initval'')`｜`functools.reduce(lambda x,y: ''func''(y,x), reversed(''list''), ''initval'')`｜`functools.reduce(''func'', ''list'')`｜`functools.reduce(lambda x,y: ''func''(y,x), reversed(''list''))`｜在模塊functools中。

R｜`Reduce(''func'', ''list'', ''initval'')`｜`Reduce(''func'', ''list'', ''initval'', right=TRUE)`｜`Reduce(''func'', ''list'')`｜`Reduce(''func'', ''list'', right=TRUE)`｜R通過給Reduce函數的right和init實際參數，支持右摺疊和有或沒有初始值的左或右摺疊。

Ruby｜`''enum''<wbr/>.inject(''initval'', ''&block'')<br /> ''enum''<wbr/>.reduce(''initval'', ''&block'')`｜`''enum''.reverse_each<wbr/>.inject(''initval'', ''&block'')<br /> ''enum''.reverse_each<wbr/>.reduce(''initval'', ''&block'')`｜`''enum''<wbr/>.inject(''&block'')<br /> ''enum''.reduce(''&block'')`｜`''enum''.reverse_each<wbr/>.inject(''&block'')<br /> ''enum''.reverse_each<wbr/>.reduce(''&block'')`｜在Ruby 1.8.7+中，還可以傳遞表示一個函數而非塊的一個符號。enum是Enumeration 請注意這些右摺疊的實現對於非交換律的&block是有誤的（還有初始值放在錯誤的一側）。

Rust｜`''iterator''.fold(''initval'', ''func'')`｜`''iterator''.rev().fold(''initval'', ''func'')`

Scala｜`''list''.foldLeft(''initval'')(''func'')``(''initval'' /: ''list'')(''func'')`｜`''list''.foldRight(''initval'')(''func'')``(''list'' :\ ''initval'')(''func'')`｜`''list''.reduceLeft(''func'')`｜`''list''.reduceRight(''func'')`｜Scala的符號式fold語法意圖重組常用來解釋摺疊運算的左或右傾斜樹，已經被重釋義為一個頂級多米諾骨牌的例證。來自通用Scala語法機制的冒號，憑藉顯見的中綴算子，被調用為一個方法在左操作數上，具有右操作數作為一個實際參數傳遞，或反之如果這個算子的最後字符是冒號，這裡是對稱應用的。Scala還有使用方法`list.fold(z)(op)`的樹狀摺疊特徵。

Scheme R6RS｜`(fold-left ''func'' ''initval'' ''list'')<br /> (vector-fold ''func'' ''initval'' ''vector'')`｜`(fold-right ''func'' ''initval'' ''list'')<br /> (vector-fold-right ''func'' ''initval'' ''vector'')`｜`(reduce-left ''func'' ''defaultval'' ''list'')`｜`(reduce-right ''func'' ''defaultval'' ''list'')`｜srfi/1 srfi/43

Smalltalk｜`''aCollection'' inject: ''aValue'' into: ''aBlock''`｜`''aCollection'' reduce: ''aBlock''`｜ANSI Smalltalk不定義#reduce: 但是很多實現定義了。

Standard ML｜`foldl ''func'' ''initval'' ''list''<br /> Array.foldl ''func'' ''initval'' ''array''`｜`foldr ''func'' ''initval'' ''list''<br /> Array.foldr ''func'' ''initval'' ''array''`｜提供的函數接受在元組中的實際參數。對於foldl，摺疊函數接受實際參數的次序同於foldr的次序。

Swift｜`''array''.reduce(''initval'', ''func'')<br /> reduce(''sequence'', ''initval'', ''func'')`｜`''array''.reverse()<wbr/>.reduce(''initval'', ''func'')`

XPath 3.1｜array:fold-left( $array as array(、), $zero as item、, $f as function(item、, item、) as item、) as item、fold-left( $seq as item、, $zero as item、, $f as function(item、, item) as item、) as item、｜array:fold-right( $array as array(、), $zero as item、, $f as`function(item()*, item()*) as item()*) as item()*` fold-right( $seq as item、, $zero as item、, $f as function(item, item、) as item、) as item、｜在XPath 3.1中由於歷史原因，`array`和`sequence`類型是不相容的 -- 因此需要分離給`array`和給`sequence`的`fold`函數。在簽名上的不同是由於`array`項目的值可以是`sequence`，但是XPath沒有`sequence`的`sequence`。

Xtend｜`''iterable''.fold(''initval'',[''func''])`｜`''iterable''.reduce[''func'']`

## 普遍性

摺疊是多態函數。對於有如下這樣定義的任何`g`：

```haskell
g [] = v
g (x:xs) = f x (g xs)
```

`g`都可以表達為：

```haskell
g = foldr f v
```

還有，不動點組合子可以通過摺疊實現，證明迭代可以被歸約成摺疊：

```haskell
y f = foldr (\_ -> f) undefined (repeat undefined)
```

## 外部連結

- "Unit 6: The Higher-order fold Functions"
- HaskellWiki: Fold