6.3 左摺、串列同構、與 Paramorphism
為了完整性，本節介紹與串列的摺相關的另外幾個組件函數。 初次閱讀時可跳過本節。
6.3.1 左摺
除了 foldr, Haskell 的標準函式庫有另一個函數 foldl, 名字中的字母 l 為「左」之意：
foldr 將串列中的元素往右括，foldl 則往左括，例如，
foldl rhd e [x0,x1,x2,x3] = (((e `rhd` x0) `rhd` x1) `rhd` x2) `rhd` x3
有了 foldl, 串列反轉可直接定義為 reverse = foldl (\xs x -> x:xs) [].
函數 foldl 可在輸入串列的長度上歸納定義如下：
foldl :: (b -> a -> b) -> b -> List a -> b
foldl rhd e [] = e
foldl rhd e (xs++[z]) = foldl rhd e xs `rhd` z
由於運算元 rhd 右邊的參數才是目前的元素，其型別為 b -> a -> b.
由此出發，我們不難導出下述將串列從左邊開始拆解的定義：
foldl rhd e [] = e
foldl rhd e (x:xs) = foldl rhd (e `rhd` x) xs
我們可注意到這是一個尾遞迴定義，
因此，如果將 sum, prod 等函數定義為 foldl (+) 0, foldl (*) 1 等等，執行時可不佔用堆疊的空間。
由於這個特性，對一些將 Haskell 用於著重效率的應用的人們來說，foldl 才是他們較常使用的「摺」。
為了效率因素更常被使用的可能是另一個嚴格(strict)版的函數 foldl', 該函數在遞迴呼叫前會先將 e `rhd` x 規約成正規式，避免尚待計算的算式被累積著。
關於 foldl 與 foldr 的關係，Bird [1998] 提及了三個定理。首先，
定理 6.14 第一對偶定理(The First Duality Theorem)
如果 oplus :: a -> a -> a 滿足遞移律，以 e :: a 為單位元素，則 foldr oplus e xs = foldl oplus e xs.
提醒一下：該定理及本節的其他定理中，xs 需為歸納定義、有限長度的串列。
遞移律意指 x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z --- 由於此項要求，oplus 的型別得是 a -> a -> a. 由於 (+), (*), (↓), (↑) 等運算元都有遞移律，sum, prod, maixmum, minimum 等函數都可用 foldl 定義。事實上，他們在標準 Haskell Report 中的定義便是如此。
定理6.14 其實是下述定理的特例。
函數 foldl 有個尾遞迴定義，其中參數 e 的角色就像是個累積參數。
第5.6.3 節中曾提及，尾遞迴函數時常和遞移律有關。
函數 foldl 是否也牽涉了某種遞移律呢？
定理 6.15 第二對偶定理(The Second Duality Theorem)
如果二元運算元 lhd :: a -> b -> b 及 rhd :: b -> a -> b 滿足 x `lhd` (y `rhd` z) = (x `lhd` y) `rhd` z 以及 x `lhd` e = e `rhd` x，
則 foldr lhd e xs = foldl rhd e xs.
定理 6.15 中的 x `lhd` (y `rhd` z) = (x `lhd` y) `rhd` z 可視為一種擴充到兩個運算元的遞移律。定理 6.14 則是 lhd = rhd 的特殊情況。
定理 6.15 的證明頗值得研究：
我們在 xs 上做歸納。基底狀況 xs := [] 中，等號兩邊都歸約為 e.
至於 xs := x : xs 的情況，我們把兩邊都化簡並使用歸納假設，推論如下：
foldr lhd e (x:xs)
=== {- foldr 之定義 -}
x `lhd` foldr lhd e xs
=== {- 歸納假設 -}
x `lhd` foldl rhd e xs
=== {- 論證如後述 -}
foldl rhd (x `lhd` e) xs
=== {- 假設： x `lhd` e = e `rhd` x -}
foldl rhd (e `rhd` x) xs
=== {- foldl 之定義 -}
foldl rhd e (x:xs)
在等式推論中段，我們希望 x `lhd` foldl rhd e xs = foldl rhd (e `rhd` x) xs.
這會需要另一個歸納證明。
但我們若直接證明此等式，到中途便會無法進行，且會發現我們需要稍做一下推廣，改證明一個較強的性質：
x `lhd` foldl rhd y xs = foldl rhd (x `lhd` y) xs (6.1 )
兩者的差別是後者不針對特定的值 e, 而是任何的 y.
這是一個「較強的性質反而比較好證明」的例子。
等式([RefUndefined])的證明如此進行：在 xs := [] 的情況中，等號兩側都規約為 x `lhd` y.
歸納情況 xs := z : xs 證明如下：
x `lhd` foldl rhd y (z:xs)
=== {- foldl 之定義 -}
x `lhd` foldl rhd (y `rhd` z) xs
=== {- 歸納假設 -}
foldl rhd (x `lhd` (y `rhd` z)) xs
=== {- 假設：x `lhd` (y `rhd` z) = (x `lhd` y) `rhd` z -}
foldl rhd ((x `lhd` y) `rhd` z) xs
=== {- foldl 之定義 -}
foldl rhd (x `lhd` y) (z:xs)
最後一個對偶定理則確認了我們的一個直覺理解：將一個串列反轉做 foldl, 便相當於 foldr:
定理 6.16 第三對偶定理(The Third Duality Theorem)
對所有 f :: a -> b -> b, e :: b, 以及 xs :: List a,
foldr f e xs = foldl (flip f) e (reverse xs).
其中 flip f x y = f y x.
6.3.2 串列同構
考慮函數 h :: List a -> b. 如果存在 e :: b, f :: a -> b, 和 odot :: b -> b -> b 使得 h 滿足下列等式：
h [] = e
h [x] = f x
h (xs ++ ys) = h xs ⊙ h ys
我們便說 h 是一個串列同構(list homomorphism), 記為 h = hom odot f e.
注意第三個等式蘊含 odot（至少在 h 的值域內）須滿足結合律：
h xs ⊙ (h ys ⊙ h zs) = h (xs++(ys++zs)) = h ((xs++ys)++zs) = (h xs ⊙ h ys) ⊙ h zs.
串列同構有平行計算的可能性：計算 hom odot f e xs 時，如果 xs 有不只一個元素，我們可將 xs 由中間任意截成兩段，分別給不同的處理器計算，再將結果用 odot 結合。
顯然，hom dot f e 可以寫成 foldr, 也能寫成 foldl:
hom odot f e === foldr (\x y -> f x ⊙ y) e
=== foldl (\y x -> y ⊙ f x) e
下述定理則告訴我們反過來也成立：如果 h 同時可寫成 foldr 及 foldl, 則 h 是一個串列同構：
定理 6.17 第三同構定理(The Third Homomorphism Theorem)
考慮 h :: List a -> b。如果存在 e :: b, lhd :: a -> b -> b, 及 rhd :: b -> a -> b 使得 h = foldr lhd e = foldl rhd e,
則存在 odot :: b -> b -> b 使得 h = hom odot f e （其中 f x = x `lhd` e = e `rhd` x）.
6.3.3 Paramorphism 與本原遞迴
如果我們把 foldr 的限制放寬，允許 xs 出現在遞迴呼叫之外，得到的模式稱為 paramorphism.
串列版的 paramorphism 可定義如下：
para :: (a -> List a -> b -> b) -> b -> List a -> b
para f e [] = e
para f e (x:xs) = f x xs (para f e xs)
para f e = fst . foldr (\x (y, xs) -> (f x xs y, x:xs)) (e, [])