折疊算法是list的典型算法。通過折疊算法可以實作衆多函數組合（function composition）。是以折疊算法也是泛函程式設計裡的基本元件（function combinator）。了解折疊算法的原理對了解泛函組合有着至關緊要的幫助。折疊算法又可分右折疊和左折疊。我們先從右折疊（foldright）開始:
從以上兩圖示可以得出對list(a,b,c)的右折疊算法：op(a,op(b,op(c,z))) 可以看出括号是從右開始的。計算方式如圖二：op(a,sub), sub是重複子樹，可以肯定要用遞歸算法。這裡z代表了一個起始值。我們現在可以推算出foldright的函數款式（function signature）了:
注意foldright不是一個尾遞歸算法（tail recursive）。我們試着對一個list(1,2,3)進行操作，先來個加法：
我們可以用”等量替換“方法簡約：
注意以上的起始值1和nil:list[int]。z的類型可以不是a，是以op的結果也有可能不是a類型，但在以上的加法和乘法的例子裡z都是int類型的。但在list重構例子裡z是list[int]類型，是以op的結果也是list[int]類型的，這點要特别注意。
再來看看左折疊算法：
從以上圖示分析，左折疊算法就是所有list元素對z的操作op。從圖二可見，op對z,a操作後op的結果再作為z與b再進行op操作，如此循環。看來又是一個遞歸算法，而z就是一個用op累積的值了：op(op(op(z,a),b),c)。左折疊算法的括号是從左邊開始的。來看看foldleft的實作：
注意z (zero) 變成了 acc (accumulator），op: (b,a) = b, 和foldright的op函數入參順序是颠倒的。foldleft是個尾遞歸方法。
以上加法和乘法的累積值acc都是a類型，但注意list重構的acc是list[int]類型的，這個時候op入參的位置就很重要了。再注意一下，foldleft重構的list的元素排列是反向的cons(13,cons(12,cons(11,nil))。我們還是可以用“等量替換”方法進行簡約：
除foldright,foldleft之外，折疊算法還包括了：reduceright,reduceleft,scanright,scanleft。
reduceleft是以第一個，reduceright是以最後一個list元素作為起始值的折疊算法，沒有單獨的起始值：
scanleft, scanright 分别把每次op的結果插入新産生的list作為傳回結果。
先實作scanleft:
試試簡約：
再實作scanright:
實在沒能想出用遞歸算法實作scanright的方法，隻能用while loop來解決了。注意雖然使用了臨時變量,但這些變量都是本地封閉的，是以scanright還是純函數。scanright元素周遊（traverse）順序是反向的，是以用reverse函數把list(1,2,3)先變成list(3,2,1)。
注意scanright和scanleft的結果不同。這是因為算法不同：元素周遊（traverse）順序不同。
下面開始示範一下折疊算法作為基本元件（combinator）來實作一些函數功能：
上次實作了函數++，即append。我們同樣可以用foldleft和foldright來實作：
由于append的功能是将兩個list拼接起來，必須保證最終結果list元素的順序。是以在appendbyfoldleft裡使用了reverse。再注意foldleft和foldright在op參數位置是相反的。
之前遞歸算法實作的函數有些是可以用折疊算法實作的：
還有些比較間接的：
這個函數可以用來實作flatmap：
如果了解以上函數實作方式有困難時可以先從類型比對上下手，或者試着用“等量替換”方法簡約跟蹤一下。