Fold (高階函式)

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

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

作為結構性變換

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

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

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

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

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

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

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

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

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

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

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

這裡的點號(.)是指示函式複合（英語：Function composition (computer science)）的算子。

通過演示線上性列表上的摺疊函式的構造方式，就會得到啟發在其他代數資料類型和結構比如各種樹之上設計類似的摺疊函式。我們可以寫一個高階函式，遞迴的將資料類型的構造子替代為所提供的函式，並將任何這個類型的常數值替代為所提供的值。這種函式一般稱為catamorphism（英語：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是非嚴格求值的，這可能在效能上有重大影響。 線性摺疊是面向節點的，並以一致方式對列表的每個節點進行運算；而樹狀摺疊是面向整個列表的，並以一致方式跨越節點「群」進行運算。

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

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」所指的是自動提供初始元素，和它們所應用到的列表至少要有一個元素的事實。

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直譯器，摺疊進行的結構性變換可以用構造一個字串來展示：

λ> 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的通過埃拉托斯特尼篩法的遞迴素數生成來演示：

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）可以使用樹狀摺疊輕易的定義為：

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

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

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

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，這樣尾遞迴的建造出的一個表達式的表示同於右摺疊所建造的。

額外的中間列表結構可以通過形似傳遞續體風格（英語：continuation-passing style）的手段去除：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。它們也常被寫為^[1]：

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.Aggregate(initval, func)	ienum.Reverse().Aggregate(initval, func)	ienum.Aggregate(func)	ienum.Reverse().Aggregate(func)		Aggregate是擴充方法（英語：Extension method） ienum是IEnumerable<T> 在所有的.NET語言中都類似
C++	std::accumulate(begin, end, initval, func)	std::accumulate(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是未展開的參數包。
CFML（英語：ColdFusion Markup Language）	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[2]
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}.to-Iterator}	{for {treeNode.to-Iterator} do}	{for {{treeNode.reverse}.to-Iterator} do}		還有DefaultListModel和HashTable實現to-Iterator
D	reduce!func(initval, list)	reduce!func(initval, list.reverse)	reduce!func(list)	reduce!func(list.reverse)		在模組std.algorithm中
Elixir	List.foldl(list, acc, fun)	List.foldr(list, acc, fun)				樣例用法見於documentation[3]
Elm	List.foldl(Fun, Accumulator, List)	List.foldr(Fun, Accumulator, List)				參見List API[4]
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（英語：Gosu (programming language)）	Iterable.fold(f(agg, e))Iterable.reduce(init, f(agg, e)) Iterable.partition(f(e))					都是在java的Iterable介面上的擴充方法（英語：extension methods），陣列也支援。
Groovy	list.inject(initval, func)	list.reverse().inject(initval, func)	list.inject(func)	list.reverse().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"[5]
Java 8+	stream.reduce(initval, func)		stream.reduce(func)
JavaScript 1.8 ECMAScript 5	array.reduce(func, initval)	array.reduceRight(func, initval)	array.reduce(func)	array.reduceRight(func)
Julia	foldl(op, itr; [init])	foldr(op, itr; [init])	foldl(op, itr)	foldr(op, itr)
Kotlin	Iterable.fold(initval, func)	Iterable.foldRight(initval, func)	Iterable.reduce(func)	Iterable.reduceRight(func)		其他搜集也支援fold[6]和reduce[7]。還有Result.fold(onSuccess, onFailure)[8]，它歸約Result<T>（要麼成功要麼失敗）成onSuccess和onFailure的返回類型。
LFE（英語：LFE (programming language)）	(lists:foldl func accum list)	(lists:foldr func accum list)
Logtalk（英語：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 vector::fold_left func initval vector	fold_right func initval list vector::fold_right func initval vector				提供的函式接受在元組中實際參數。
OCaml	List.fold_left func initval list Array.fold_left func initval array	List.fold_right func list initval Array.fold_right func array initval			Base.Sequence.unfold ~init ~f [9]
Oz	{FoldL List Func InitVal}	{FoldR List Func InitVal}
PARI/GP（英語：PARI/GP）	fold( f, A )
Perl	reduce block initval, list		reduce block list			在List::Util模組中
PHP	array_reduce(array, func, initval)	array_reduce(array_reverse(array), func, initval)	array_reduce(array, func)	array_reduce(array_reverse(array), func)		在未提供initval的時候，使用了NULL，所以不是真正的foldl1。在PHP 5.3之前，initval只能是整數。func是一個callback[10]。參見線上的array_reduce文件[11]。
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中[12]。
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.inject(initval, &block) enum.reduce(initval, &block)	enum.reverse_each.inject(initval, &block) enum.reverse_each.reduce(initval, &block)	enum.inject(&block) enum.reduce(&block)	enum.reverse_each.inject(&block) enum.reverse_each.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語法意圖重組常用來解釋摺疊運算的左或右傾斜樹[13]，已經被重釋義為一個頂級多米諾骨牌的例證[14]。來自通用Scala語法機制的冒號，憑藉顯見的中綴算子，被呼叫為一個方法在左運算元上，具有右運算元作為一個實際參數傳遞，或反之如果這個算子的最後字元是冒號，這裡是對稱應用的。 Scala還有使用方法list.fold(z)(op)的樹狀摺疊特徵[15]。
Scheme R6RS	(fold-left func initval list) (vector-fold func initval vector)	(fold-right func initval list) (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 Array.foldl func initval array	foldr func initval list Array.foldr func initval array				提供的函式接受在元組中的實際參數。對於foldl，摺疊函式接受實際參數的次序同於foldr的次序。
Swift	array.reduce(initval, func) reduce(sequence, initval, func)	array.reverse().reduce(initval, func)
XPath 3.1	array:fold-left( $array as array(*), $zero as item()*, $f as function(item()*, item()*) as item()*) as item()*[16] fold-left( $seq as item()*, $zero as item()*, $f as function(item()*, item()) as item()*) as item()*[17]	array:fold-right( $array as array(*), $zero as item()*, $f asfunction(item()*, item()*) as item()*) as item()*[18] fold-right( $seq as item()*, $zero as item()*, $f as function(item(), item()*) as item()*) as item()*[19]				在XPath 3.1中由於歷史原因，array和sequence類型是不相容的 -- 因此需要分離給array和給sequence的fold函式。在簽章上的不同是由於array專案的值可以是sequence，但是XPath沒有sequence的sequence。
Xtend（英語：Xtend）	iterable.fold(initval,[func])		iterable.reduce[func]

普遍性

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

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

g都可以表達為^[20]：

g = foldr f v

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

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

參見

• 聚集函式（英語：Aggregate function）
• 迭代二元關係（英語：Iterated binary operation）
• Map (高階函式)
• Filter (高階函式)
• 字首和（英語：Prefix sum）
• 遞迴資料類型
• 遞迴算子（英語：Reduction Operator）
• 遞迴 (電腦科學)