6.1 串列的摺

「摺」有許多方式可理解。 我們可說 foldr 捕捉了最常見的一種歸納定義模式，並將它形式化地表達出來。 在第2 章中，許多函數定義都遵循這樣的模式：

h :: List a -> b
h []      = e
h (x:xs)  = ... x ... h xs ...

在 h [] 的情況傳回某個基底值；在 h (x:xs) 的情況中可使用 x 與 h xs 的值。 如果上述定義中 ... 之處沒有出現 xs, 則 h 的定義就能寫成一個 foldr.

我們也可將 foldr 視為組件(combinator)函數之一。 第1.8.3 節之中介紹了組件函數的觀念： 如同 map, take, drop, zip 等等的組件函數捕捉了常見的程式設計模式。 每個組件負責一項單一、通用、易重用的功能。 函數 foldr 也可視為一個組件，只是它比一些其他組件更抽象、更通用 --- 我們稍後將發現許多我們見過的組件函數都是 foldr 的特例。

還有一個理解 foldr 的方式：foldr 替換了串列中的建構元。 回顧：任何有限長度的串列都是由 [] 開始，有限次地套用 (:) 而來。 例如 [x0,x1,x2] 是 x0 : (x1 : (x2 : [])) 的簡寫。 考慮 foldr oplus e [x0,x1,x2]:

     foldr oplus e (x0 : (x1 : (x2 : [])))
===  x0 ⊕ foldr oplus e (x1 : (x2 : []))
===  x0 ⊕ (x1 ⊕ foldr oplus e (x2 : []))
===  x0 ⊕ (x1 ⊕ (x2 ⊕ foldr oplus e []))
===  x0 ⊕ (x1 ⊕ (x2 ⊕ e)) 

我們可看到 foldr 將串列走訪一次，將每個 (:) 替換成 oplus, 將 [] 替換成 e. 式子中的括號往右邊結合，這是 foldr 的名字中字母 r 的由來。 這種理解也便於解釋 foldr 的型別。 回想串列的兩個建構元，

• [] 的型別是 List a,

• (:) 的型別是 a -> List a -> List a.

函數 foldr oplus e 接收一個 List a，把其中的建構元分別替換為 e 與 oplus，藉此算出一個型別為 b 的值。因此，

• e 是輸入為 [] 時立刻傳回的值，其型別必須是 b.

• 至於 oplus 的型別，考慮 x0 ⊕ (x1 ⊕ (x2 ⊕ e)) 這個式子。 其中 x0 的型別為 a, x1 ⊕ (x2 ⊕ e) 是建構元已被替換過的串列，型別應該為 b. 而 oplus 拿到這兩個輸入後，得算出一個型別為 b 的值. 因此 oplus 的型別為 a -> b -> b.

注意：e 與 oplus 的型別分別是將 [] 與 (:) 的型別中的 List a 代換成 b 而來。 綜合言之， foldr 的型別是 (a -> b -> b) -> b -> List a -> b.

為方便說明，此後我們將 foldr oplus e 之中的 e 稱作基底值(base value)，將 oplus 稱作步驟函數(step function). 函數 foldr 的型別可以理解為：給一個型別為 a -> b -> b 的步驟函數，和一個型別為 b 的基底值，foldr 就能將一個 List a 轉換為 b.

串列的摺(foldr)只是一個常用的特例 ---「將資料結構中的建構元代換掉」的動作也可推廣到其他資料結構上。 我們在之後的章節中將看到一些其他資料結構上的摺。

下一節將舉更多使用 foldr 的例子。 在那之前我們再次提醒讀者：在 foldr oplus e (x:xs) 的狀況中，oplus 可以使用 x 與 foldr oplus e xs 的結果，但不能直接使用 xs.

6.1.1 更多串列上的摺

回顧起來，我們可發現第2 章介紹的許多函數都是 foldr.

串列連接 (++) :: List a -> List a -> List a 雖是個二元運算， 若將 (++ ys) :: List a -> List a 視為一個函數，它可寫成一個 foldr:

 (++ ys) = foldr (:) ys 

一個重要的特例是當 ys = [] 時。對任何 xs, xs ++ [] = xs. 因此 (++[]) 是串列上的 id:

id :: List a -> List a
id = foldr (:) [] 

確實，將一個串列中的 (:) 代換成 (:), [] 代換成 [], 我們還是得到原來的串列。 我們日後還會用到「串列上的 id 是一個 foldr」的性質。

計算所有前段的函數 inits :: List a -> List (List a) 可寫成 foldr:

inits = foldr (\x xss -> [] : map (x:) xss) [[]] 

計算所有後段的 tails :: List a -> List (List a) 也可以寫成 foldr，但需要用一個小性質。 回顧其定義：

tails []      = [[]]
tails (x:xs)  = (x:xs) : tails xs 

乍看之下這不符合 foldr 的模式：參數 xs 出現在 ... : tails xs 的左邊，但在 foldr 的模式中，xs 不能出現在遞迴呼叫之外。 幸好 tails 有一個剛好在此有用的小特性：tails xs 傳回的所有後段中，第一個就是 xs 本身：head (tails xs) = xs. 因此我們可將 tails 寫成：

tails = foldr (\x xss -> (x : head xss) : xss) [[]] 

由於 tails 永遠傳回非空串列，使用 head xss 是安全的。

splits = foldr spl [([],[])] 
  where  spl x ((xs,ys):zss) =
           ([],x:xs++ys) : map ((x:) *** id) ((xs,ys):zss) 

6.1.2 不是 foldr 的函數

並非所有輸入為串列的函數都是 foldr. 最明顯的例子是 tail: 我們無法由 x 和 tail xs 算出 tail (x:xs)。 例如，tail [1,2,3] = [2,3]，但 tail [2,3] = [3], 而 [2,3] 無法由 1 和 [3] 組出來。

另一個例子是 dropWhile p. 回顧其定義：

dropWhile p []      = []
dropWhile p (x:xs)  = if p x then dropWhile p xs else x:xs 

在歸納情況中，else 的分支需傳回 x:xs --- xs 出現在遞迴呼叫以外的地方。這樣的程式不是 foldr。 當然，這只表示 dropWhile p 的這個定義不符合 foldr 的模式. 是否有其他的方式能將 dropWhile p 寫成 foldr 呢？ 不論 dropWhile p 是怎麼定義的，考慮 dropWhile even [4,3,6,2] = [3,6,2], 但 dropWhile even [3,6,2] = [] --- 看來，dropWhile p 丟掉了太多資訊，使得我們無法保證能從 dropWhile p xs 重組出 dropWhile p (x:xs)。 因此，dropWhile p 和 tail 一樣，是先天上無法寫成 foldr 的。

fan :: a -> List a -> List (List a)
fan y []      = [[y]]
fan y (x:xs)  = (y:x:xs) : map (x:) (fan y xs) 

fan' y = foldr (\x xss -> (y:x: tail (head xss)) : map (x:) xss) [[y]]