5.6 累積參數

在第 5.2 節中，我們曾提及該處定義的 reverse :: List a -> List a 需要 $O(n^2)$ 的時間。是否有比較快的作法呢？

5.6.1 串列反轉與連接

下列函數 revcat 似乎比 reverse 更通用一些：它拿兩個參數 xs 與 ys, 不僅將 xs 反轉，還把 ys 接到反轉後結果的右邊： (註6) revcat 為 reverse'' 與concat'' 的簡寫。

revcat :: List a -> List a -> List a
revcat xs ys = reverse xs ++ ys 

原有的 reverse 可以視為 revcat 的特例 --- reverse xs = revcat xs []. 這裡是否也會出現責任越大，能力越強的現象： 看似做了較多事情的 revcat 其實反倒有比較有效率的實作呢？ 我們試著演算看看！當 xs := [], 顯然 revcat [] ys = ys. 考慮 xs := x:xs 的情況：

      revcat (x:xs) ys
 ===    {- revcat 之定義 -}
      reverse (x:xs) ++ ys
 ===    {- reverse 之定義 -}
      (reverse xs ++ [x]) ++ ys
 ===    {- (++) 之結合律 -}
      reverse xs ++ ([x] ++ ys)
 ===    {- (++) 與 revcat 之定義 -}
      revcat xs (x : ys) 

因此我們有了：

revcat []      ys = ys
revcat (x:xs)  ys = revcat xs (x:ys) 

我們看看 revcat [1,2,3,4] [] 如何歸約：

   revcat (1:2:3:4:[]) []
=  revcat (2:3:4:[]) (1:[])
=  revcat (3:4:[]) (2:1:[])
=  revcat (4:[]) (3:2:1:[])
=  revcat [] (4:3:2:1:[])
=  [4,3,2,1] 

串列 [1,2,3,4] 中的元素一個個被搬到 revcat 的第二個參數中。這是一個常數時間內可完成的動作，而每個元素只會被搬動一次。因此當 xs 的長度是 n，reverse xs ys 可在 $O(n)$ 的時間內執行完畢！

我們剛看到的技巧和第 5.5 節中的組對互為對偶。 在第 5.5 節中，我們為了導出一個函數的較快版本，讓它多傳回一些資訊。 而在本節，我們則讓一個函數多吃些參數，多接受些資訊。 通常這些新介紹的參數用於「累積」計算到目前為止的結果，例如 在 revcat 中，參數 ys 存放被反轉到一半的串列。 因此這個技巧被稱作累積參數(accumulating parameters)。

很多情況下，累積參數的運用仰賴某些運算元的結合律。 觀察 revcat 的推導，關鍵的一步便是 (++) 的結合律。 它使我們能夠把 (reverse xs ++ [x]) ++ ys 轉換為 reverse xs ++ ([x] ++ ys)，將 [x] 往右搬，才能收回、累積到 revcat 的第二個參數 ys 中。

回顧起來，我們最初如何發明出 revcat xs ys = reverse xs ++ ys 這樣的定義呢？ 一個解釋便是：reverse 之所以慢，是因為 (++) 的括號都括錯了方向，往左邊括了。 因此我們在右邊補一個 (++ ys), 希望用 (++) 的結合律，將括號往右挪。

我們多看一個例子。以下函數 tags 傳回一棵 ITree 中所有的標籤：

tags :: ITree a -> List a
tags Null          = []
tags (Node x t u)  = tags t ++ [x] ++ tags u 

和習題 5.7 的情況類似，當 t 是一棵向左傾斜的樹，tags 會需要 $O(n^2)$ 的時間。 例如，考慮這棵樹 t （以下將 Node x Null Null 簡寫為 lv x）：

  t = Node 7  (Node 6  (Node 4  (Node 2 (lv 1) (lv 3))
                       (lv 5)))
              (lv 8) 

將 tags t 展開（並為說明方便，將一些 []++[x]++[] 化簡為 [x]），我們會得到：

 ((([1] ++ [2] ++ [3])  ++ [4]
                        ++ [5]) ++ [6]) ++ [7] ++ [8] 

這個式子的結構和 t 一樣，只是將 Node x... 都變為 .. ++ [x] ++ ... 我們可看到 (++[6]) 需要走過一個長度為 5 的串列，(++[7]) 需要走過一個長度為 6 的串列。

為了避免 (++) 的重複走訪，我們在 tags t 的左邊補一個 (++ys), 希望透過結合律改變括號的順序。我們定義：

tagsAcc :: ITree a -> List a -> List a
tagsAcc t ys = tags t ++ ys 

利用 (++) 的結合律，讀者應不難導出如下的歸納定義：

tagsAcc Null          ys = ys
tagsAcc (Node x t u)  ys = tagsAcc t (x : tagsAcc u ys) 

之後我們便可重新定義 tags t = tagsAcc t []. 至於 tagsAcc 的效率如何呢？ 如果將 tagsAcc t ys 展開，我們順利地得到：

 1 : (2 : (3 : (4 : (5 : (6 : (7 : (8 : ys))))))) 

      tagsAcc (Node x t u) ys
 ===  tags (Node x t u) ++ ys
 ===  (tags t ++ [x] ++ tags u) ++ ys
 ===    {- (++) 的結合律 -}
      tags t ++ (x : tags u ++ ys)
 ===  tagsAcc t (x : tagsAcc u ys) 

tagsAcc Null          ys = ys
tagsAcc (Node x t u)  ys = tagsAcc t (x : tagsAcc u ys) 

      tipsAcc (Bin t u) ys
 ===  (tips t ++ tips u) ++ ys
 ===    {- (++) 之結合律 -}
      tips t ++ (tips u ++ ys)
 ===  tipsAcc t (tipsAcc u ys) 

tipsAcc (Tip x)    ys = x : ys
tipsAcc (Bin t u)  ys = tipsAcc t (tipsAcc u ys) 

5.6.2 由上到下的資訊流

前一節之中，我們用累積參數改變 (++) 結合的順序。 更廣泛說來，累積參數常有「增加一個由上到下的資訊流」的效果。

遞增串列   下述函數 ascending 判斷一個串列是否為遞增：

ascending :: List Int -> Bool
ascending []      = True
ascending (x:xs)  = all (x <=) xs ⋀ ascending xs 

當輸入串列長度為 n, 這個定義需做 $O(n^2)$ 次比較。 習題 5.14 曾考慮過一個定義類似的 ascending，並用組對的技巧得到一個時間複雜度為 $O(n)$ 的程式。本節則試試看改用累積參數！

這次我們使用如下的定義：

ascendBnd xs z = all (z<=) xs ⋀ ascending xs 

在嘗試推導 ascendBnd 之前，我們得先確定它是有用的 --- ascending 可以用 ascendBnd 定義出來。確實如此：ascending xs = ascendBnd xs minBound.

現在我們可以推導 ascendBnd 的歸納定義了。基底狀況如下：

      ascendBnd z []
 ===   {- ascendBnd 之定義 -}
      all (z<=) [] ⋀ ascending []
 ===   {- all 與 ascending 之定義 -}
      True

歸納狀況的推導則會需要下述性質：

  z <= x ⋀ all (z <=) xs ⋀ all (x <=) xs {-"~~"-} ==> {-"~~"-} z <= x ⋀ all (x <=) xs     (5.3 )

回顧起來，我們之所以那麼定義 ascendBnd, 正是希望利用 ([RefUndefined]) 將程式中的 all (z<=) xs 吸收掉。推導如下：

      ascendBnd z (x:xs)
 ===    {- ascendBnd 與 ascending 之定義 -}
      all (z<=) (x:xs) ⋀ all (x <=) xs ⋀ ascending xs
 ===    {- all 之定義 -}
      z <= x ⋀ all (z <=) xs ⋀ all (x <=) xs ⋀ ascending xs
 ===    {- 性質 \eqref{eq:lowerbound-strengthen} -}
      z <= x ⋀ all (x <=) xs ⋀ ascending xs
 ===    {- ascendBnd 之定義 -}
      z <= x ⋀ ascendBnd x xs 

總結之，我們導出了下述定義：

ascendBnd :: Int -> List Int -> Bool
ascendBnd z []      = True
ascendBnd z (x:xs)  = z <= x ⋀ ascendBnd x xs 

讀者可將之與最初的 ascending 比較。函數 ascending 的資訊流動只從串列尾到頭 --- ascending (x:xs) 的值需等待 ascending xs 的結果。但 ascendBnd 多了一個 \emph{由上到下}的資訊流動：如果 ascendBnd z xs 成立，參數 z 是 xs 所有元素的下界 (lower bound)，而該參數的值在每次遞迴呼叫時更新。

深度標記   給定 t :: ITree a（型別 ITree 定義於第 1.10 節）, 下述函數 depthsT t 由左至右傳回樹中所有的元素，並標記其深度 --- 根部節點的深度為 0, 左右子樹中的節點的深度則是其原本深度加一：

depths :: ITree a -> List (a × Nat)
depths Null          =  []
depths (Node x t u)  =  map (id *** (Suc)) (depths t) ++ [(x,0)] ++
                        map (id *** (Suc)) (depths u) 

由於反覆使用 map, 當輸入樹有 n 個節點時，depths 最壞情況下需使用 $O(n^2)$ 個 (Suc). 是否可能用累積參數讓它快一點呢？

和各種程式堆導與證明技巧一樣，使用累積參數的技巧時，最難的一步是如何設計那個通用版的函數。 我們的答案仍是\emph{讓符號為你工作}：許多時候我們可以藉由觀察算式、展開定義看出有哪些部分是可以取出、吸收、或累積的。在 ascending 的例子中，我們希望把 all (x<=) xs 吸收掉。 至於此處，如果試圖展開 depths, 我們會看到許多層 map (id *** (Suc)) 被堆積在算式中等待被畫減。 如果我們在最外面套一個 map (id *** (k +)):

depthsAcc t k = map (id *** (k +)) (depths t) 

也許有機會改變括號的順序，並將 map (id *** (Suc)) 吸收到 map (id *** (k +)) 之中。

同樣地，在推導 depthsAcc 之前，我們得先確認 depths 是 depthsAcc 的特例。 確實，depths t = depthsAcc t 0.

然後我們可以開始推導 depthsAcc 了。基底狀況中，depthsAcc Null k = []. 考慮歸納狀況：

      depthsAcc (Node x t u) k
 ===    {- depthsAcc 與 depths 之定義 -}
      map (id *** (k +)) (  map (id *** (Suc)) (depths t) ++ [(x,0)] ++
                             map (id *** (Suc)) (depths u))
 ===    {- map 分配入 (++), map 之定義 -}
      map (id *** (k +)) (map (id *** (Suc)) (depths t)) ++ [(x,k)] ++
      map (id *** (k +)) (map (id *** (Suc)) (depths u))
 ===    {- map 融合， (***) 融合 \eqref{eq:prod-fusion} -}
      map (id *** ((k +) . (Suc))) (depths t) ++ [(x,k)] ++
      map (id *** ((k +) . (Suc))) (depths u)
 ===    {- 對所有 n, 我們有 k + (Suc n) = Suc (k + n) -}
      map (id *** ((Suc k) +)) (depths t) ++ [(x,k)] ++
      map (id *** ((Suc k) +)) (depths u)
 ===    {- depthsAcc 與 depths 之定義 -}
      depthsAcc t (Suc k) ++ [(x,k)] ++ depthsAcc u (Suc k) 

因此我們得到

depthsAcc :: ITree a -> Nat -> List (a × Nat)
depthsAcc Null          k =  []
depthsAcc (Node x t u)  k =  depthsAcc t (Suc k) ++ [(x,k)] ++
                             depthsAcc u (Suc k) 

同樣地，depthsAcc 的參數 k 是從上往下傳遞的資訊：它記錄著目前的深度，每往下一層就遞增一次。

depthsT :: ITree a -> ITree (a × Nat)
depthsT Null          = Null
depthsT (Node x t u)  = Node (x,0)  (mapI (id *** (Suc)) (depthsT t))
                                    (mapI (id *** (Suc)) (depthsT u)) 

depthsTAcc t k = mapI (id *** (k +)) (depthsT t) 

depthsAcc' t k ys = depthsAcc t k ++ ys 

5.6.3 尾遞迴

關於第 5.6.1 節的 revcat 有許多面向可談。 本節先用它帶出一個重要的觀念：尾遞迴。

從第 2 章起，我們常見的歸納定義形式如下：

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

sum []      = 0
sum (x:xs)  = x + sum xs 

右側的 sum 函數便是一個典型的例子。 我們通常必須對遞迴呼叫的結果做些加工。 例如此處 sum xs 的結果需要經過 (x+), 才成為 sum (x:xs) 的值。 實作上，電腦在執行 sum xs 的程式碼前必須記下「sum xs 回傳後，必須回來執行 (x+)」這件事。 這可能用堆疊或著其他方式達成。 無論如何，當 xs 長度為 n, 便有大約 n 個這種「尚待完成的計算」被暫存著。 當 xs 被走訪到了基底狀況，這些暫存的計算才一個個被收回。

但 revcat 的情況卻有點不同。 觀察其程式碼，會發現遞迴呼叫 revcat xs (x:ys) 的結果本身就是其左手邊 revcat (x:xs) ys 的值，不需其他的加工：

revcat []      ys = ys
revcat (x:xs)  ys = revcat xs (x:ys) 

因此，revcat 的實作中，遞迴呼叫完成後，電腦不需回到原呼叫之處再執行什麼東西：最後的結果 ys 可直接傳回到最上層、第一個呼叫 revcat 的地方！ (註7) 如果該語言的實作確實有做到這點，我們說它實作了尾呼叫消除(tail call elimination)或尾呼叫最佳化(tail call optimisation)。有些語言到了蠻晚的版本才支援這個最佳化。

當一個函數 f 呼叫函數 g 時，如果該呼叫本身就是函數 f 最後的結果，並沒有針對傳回值的額外計算，我們將它稱之為一個尾呼叫(tail call)。 此名稱的由來可能是因為該呼叫是一連串計算後「最尾端」的動作。 如果這是一個遞迴呼叫，則稱之為尾遞迴(tail recursion)。

尾遞迴與迴圈   函數語言中的尾遞迴程式和指令式語言中的迴圈有相當密切的關係。 回顧 revcat [1,2,3,4] [] 的歸約過程：

   revcat (1:2:3:4:[]) []
=  revcat (2:3:4:[]) (1:[])
=  revcat (3:4:[]) (2:1:[])
=  revcat (4:[]) (3:2:1:[])
=  revcat [] (4:3:2:1:[])
=  [4,3,2,1] 

其實看來就像是一個有兩個變數的迴圈，其中一個由 1:2:3:4:[] 逐漸縮短為 []，另一個由 [] 逐步增長為 4:3:2:1:[]. 函數 reverse 的定義 reverse xs = revcat xs [] 就是為這兩個變數設定初始值：如果要計算 xs 的反轉，兩變數應該分別初始化為 xs 與 []. 在 revcat 的定義中，revcat [] ys 表示該迴圈在第一個變數為 [] 時終止，此時程式傳回 ys；而revcat (x:xs) ys = revcat xs (x:ys) 則指定了在迴圈的每一步中兩個變數的值如何改變。 函數 reverse 與 revcat 的組合相當於是這樣的一個指令式語言迴圈（假設 xs 與 ys 為變數，XS 為欲反轉的串列）： (註8) xs, ys := e1, e2 將 e1 與 e2 兩個值同時給予 xs 與 ys; do B -> S od 表示一個迴圈，當 B 還成立時便反覆執行 S.

xs, ys := XS, [];
do xs /= [] ->
   xs, ys := tail xs, head xs : ys
od ;
return ys

而該迴圈的恆式(loop invariant)是什麼呢？ 正是 reverse XS = reverse xs ++ ys --- 右手邊就是 revcat 的定義。

一般說來，一個尾遞迴函數可視為一個迴圈，其參數就是迴圈中的變數。 遞迴呼叫時參數改變，相當於更新這些變數的值，其基底狀況則相當於迴圈的終止條件。 當我們為了計算某個函數 f 而設計了另一個較通用、可寫成尾遞迴的函數 fAcc, fAcc 的定義(例如 reverse xs ++ ys)往往就是這個迴圈的恆式(loop invariant)。 在指令式程式推導的方法學中，設計一個迴圈最難之處便是決定其恆式。 如第 5.5.4 節所言，一般來說，並沒有一個固定的方法讓我們由 f 找出 fAcc。 但我們仍可讓符號推演幫我們一些忙，並歸納出一些常見的模式。

串列總和   累積參數的技巧常被用來推導尾遞迴程式（雖然累積參數的應用並不僅止於此）。 我們多看一個例子。如前所述，sum 函數每次被遞迴呼叫時會需要用堆疊或其他等價的方式記住每個 (x+)。是否能避免這麼做呢？ 我們定義：

sumAcc :: List Int -> Int -> Int
sumAcc xs y = y + sum xs 

如此定義 sumAcc 的直覺理由是：我們想用參數 y 存放累積的結果，希望利用 (+) 的結合律逐步把 sum xs 的結果搬入 y 中。 同樣地，一但找到了這個定義，之後的演算便相當日常、例行了。 我們先記下：sum xs = sumAcc xs 0. 接下來試圖導出 sumAcc 的歸納定義。 在基底情況中，我們會需要 y + 0 = y。 為了目睹結合律如何運作，我們看看 xs := x:xs 的狀況：

     sumAcc (x:xs) y
===  y + sum (x:xs)
===  y + (x + sum xs)
===    {- (+) 之結合律 -}
     (y+x) + sum xs
===  sumAcc xs (y+x) 

讀者可能發現我們之所以定義 sumAcc xs y 為 y + sum xs, 而不是 sum xs + y, 是為了在使用結合律的那一步之中讓 x 可以就近與 y 結合。 當然，(+) 也滿足交換律，因此兩個定義其實是一樣的。 當我們處理沒有交換律的運算元時，就得對這類細節更小心了。 總之，我們可導出以下的程式：

sumAcc []      y = y
sumAcc (x:xs)  y = sumAcc xs (y + x) 

這可翻譯成下述的兩種迴圈之一。 左手邊的程式將串列 XS 加總，使用的兩個變數 xs 與 y 對應到 sumAcc 的兩個參數。 在右邊的程式中，我們假設輸入資料 [x0, x1.. xN1] 依序被存放在一個陣列 X 中。陣列有 N 個元素，其索引範圍為 [0.. N-1]. 我們把陣列視為索引到內容的函數，因此 X i 存放著 xi.

xs, y := XS, 0;
do xs /= [] ->  y   := y + head xs ;
                xs  := tail xs
od ;
return y

i, y := 0, 0;
do i /= N ->  y  := y + X i ;
              i  := i + 1
od ;
return y

確實，這就是我們一般用指令式語言加總一個串列/陣列時的常見迴圈寫法： 由左到右走訪，用一個變數存放目前為止的和。 以往許多人可能都沒注意到：同樣是「將 xs 由左到右走一遍」，這個程式和 sum xs 是不同的演算法！ sum [1,2,3,4] 算出的是 1 + (2 + (3 + (4 + 0))), 而上述的、我們常用的那個迴圈算出的是 (((0 + 1) + 2) + 3) + 4. 多虧 (+) 的結合律，它們剛好是一樣的。

在迴圈中處理串列   在本節的結尾，我們更完整地討論一下歸納式的串列處理與迴圈的關係。初次閱讀的讀者可跳過本段。 假設某函數 f :: List A -> B 能寫成如下的形式：

 f []      = e
 f (x:xs)  = x ⊕ f xs 

其中 e :: B, oplus :: A -> B -> B, 此處不假設 oplus 滿足結合律。我們能用一個尾遞迴函數（或著說用一個迴圈）計算 f 嗎？直覺上，我們可用一個迴圈將串列從右往左走一遍，並用變數紀錄目前為止算出的值。確實，如果我們要求如下的規格：

loop xs (f ys) &= f (xs ++ ys)     (5.4 )

（所以 f xs = loop xs (f []) = loop xs e） 並分析 xs := [] 和 xs := xs++[x] 的情況如下：

    loop [] (f ys)
===   {- loop 之規格 -}
    f ([] ++ ys)
===   {- (++) 之定義 -}
    f ys 

    loop (xs++[x]) (f ys)
===   {- loop 之規格 -}
    f (xs ++ [x] ++ ys)
===   {- (++) 之結合律，loop 之規格 -}
    loop xs (f (x:ys))
=== loop xs (x ⊕ f ys) 

可知如下定義的 loop 能滿足 ([RefUndefined])：

loop []           z = z
loop (xs ++ [x])  z = loop xs (x ⊕ z) 

但從串列尾端取出元素較不方便。如果我們改用下式作為規格：

loop xs (f ys) &= f (reverse xs ++ ys)     (5.5 )

可推導出

 loop []      z = z
 loop (x:xs)  z = loop xs (x ⊕ z) 

但此時要用 loop 計算出 f xs，得先將 xs 反轉：f xs = loop (reverse xs) e. 這具體印證了我們的觀察：在串列上歸納定義出的函數，處理元素的順序和通常寫法的迴圈是相反的。

假設有 N 個元素的串列 xs = [x0, x1 ... xN1] 被反過來存放在陣列 X 之中， 意即 X 0 = xN1, X 1 = xN2, ... X (n-1) = x0. 前述的兩種 loop 函數都可在不同的詮釋下理解為如下的指令式程式。

i, z := 0, e;
do i /= N ->  z  := X i ⊕ z ;
              i  := i + 1
od ;
return z 

5.6.4 更多尾遞迴範例

我們多看些使用結合律推導出尾遞迴程式，並增進效率的例子。

快速乘冪   說到結合律的應用，似乎不得不提作為經典例子的乘冪。我們在第 5.3.2 節中曾用二進位表示法導出一個用 $O(\log n)$ 個乘法計算 $b^n$ 的程式。 此處我們使用結合律推導出尾遞迴的版本。 回顧函數 exp 在第 2.2 節中的定義，乘冪便是連續的乘法。 我們定義以下的函數 expAcc，把 exp b n 乘上一個累積參數 x，希望將一些中間結果搬移到 x 中：

expAcc :: Nat -> Nat -> Nat -> Nat
expAcc b n x = x * exp b n 

如果 expAcc 有快速的定義，我們可以令 exp b n = expAcc b n 1. 然後我們針對 n 為零、n 為非零的偶數，以及 n 為奇數三種情況作分析。 當 n := 0, expAcc b 0 x = x. 當 n 為偶數時，可以被改寫成 2*n. 以下的推導中我們將 exp b n 寫成 $b^n$, 並假設它已有乘冪該有的各種性質：

      expAcc b (2 * n) x
 ===  x * exp b (2 * n)
 ===   {- 因 exp b (m * n) = exp (exp b m) n -}
      x * exp (exp b 2) n
 ===   {- expAcc 之定義，exp b 2 = b * b -}
      expAcc (b * b) n x 

當 n 是奇數，我們將它改寫成 1+n:

      expAcc b (1 + n) x
 ===  x * exp b (1+n)
 ===    {- $\Varid{exp}$ 之定義 -}
      x * (b * exp b n)
 ===    {- (*) 之結合律 -}
      (x * b) * exp b n
 ===    {- expAcc 之定義 -}
      expAcc b n (x * b) 

將語法改寫成 Haskell 能接受的形式（例如將 2 * n 與 n 改寫成 n 與 n `div` 2）之後，我們得到這樣的程式：

expAcc b 0 x  = x
expAcc b n x  | even  n = expAcc (b * b) (n `div` 2) x
              | odd   n = expAcc b (n-1) (x*b) 

確實，這是一般在指令式語言中快速計算乘冪的方式。 一個操作性的理解法是：expAcc b n x 開始執行後，第一個參數中總是存放著 b 的「2 的某個次方」的乘冪（$b$, $b^2$, $b^4$...）。只在 n 是奇數時，當時的 b 才會被乘入累積參數 x 之中。

b, n, x := B, N, 1;
do n /= 0 ->  if  even  n -> b, n := b * b, n `div` 2
              |   odd   n -> n, x := n - 1, x * b
              fi
od;
return x

fact :: Nat -> Nat
fact Zero     = 1
fact (Suc n)  = (Suc n) *: fact n 

     factAcc (Suc n) y
===  y *: fact (Suc n)
===  y *: ((Suc n) *: fact n)
===    {- (*:) 之結合律 -}
     (y *: (Suc n)) *: fact n
===  factAcc n (y *: (Suc n)) 

factAcc Zero     y = y
factAcc (Suc n)  y =
   factAcc n (y *: (Suc n)) 

n, y := N, 0;
do n /= 0 -> n, y := n-1, y * n od;
return y 

mulAcc m n k = k + m * n 

      mulAcc (2*m) n k
 ===  k + (2*m) * n
 ===   {- (*) 之交換律與結合律 -}
      k + m * (2 * n)
 ===  mulAcc m (2*n) k 

      mulAcc (1+m) n k
 ===  k + (1+m) * n
 ===    {- (*) 分配進入 (+) -}
      k + n + m * n
 ===    {- (+) 之結合律，mulAcc 之定義 -}
      mulAcc m n (k + n) 

mulAcc 0 n k  = k
mulAcc m n k  | even n  = mulAcc (m `div` 2) (2*n) k
              | odd n   = mulAcc (m - 1) n (k + n) 

dtoN :: List Nat -> Nat
dtoN []      = 0
dtoN (d:ds)  = d * exp 10 (length ds) + dtoN ds 

dtoNT :: List Nat -> (Nat × Nat)
dtoNT ds = (dtoN ds, exp 10 (length ds)) 

dtoNT []      = (0,1)
dtoNT (d:ds)  = (d * t + n, 10 * t) 
  where (n,t) = dtoNT ds 

dtoNAcc ds n = n * exp 10 (length ds) + dtoN ds 

      dtoNAcc (d : ds) n
 ===  n * exp 10 (length (d:ds)) + dtoN (d:ds)
 ===  n * exp 10 (length (d:ds)) + d * exp 10 (length ds) + dtoN ds
 ===    {- length 與乘冪之定義 -}
      n * 10 * exp 10 (length ds) + d * exp 10 (length ds) + dtoN ds
 ===    {- 算數運算 -}
      (n * 10 + d) * exp 10 (length ds) + dtoN ds
 ===    {- dtoNAcc 之定義 -}
      dtoNAcc ds (n * 10 + d) 

dtoNAcc []      n = n
dtoNAcc (d:ds)  n = dtoNAcc ds (n * 10 + d) 

多個累積參數   我們以一個稍微複雜的例子結束本節。給定以下函數： (註9) masc 為 ``mostly ascending'' 的縮寫。這個函數大致上遞增，但偶爾會掉下來一點點。

masc :: Nat -> Nat
masc 0            = 1
masc (2 * n)      = 2 * masc n
masc (1 + 2 * n)  = n + masc n 

我們想用累積參數的技巧，推導出一個以尾遞迴計算 masc n 的演算法。 最難的一步總是尋找一個合適的通用化。 我們試著展開 masc, 看看是否能找到什麼規律。 以 masc 43 為例：

   masc 43
=  21 + masc 21
=  21 + 10 + masc 10
=  31 + masc 10
=  31 + 2 * masc 5
=  31 + 2 * (2 + masc 2)
=  35 + 2 * masc 2
=  35 + 4 * masc 1
=  35 + 4 * 1
=  39 

我們發現式子總能展開成為 a + b * masc n 的形式。 因此我們定義

mascAcc :: Nat -> Nat -> Nat -> Nat
mascAcc n a b = a + b * masc n 

但在開始推導 mascAcc 前，我們得先確定 masc 能由 mascAcc 算得出來。 幸好，我們可以讓 masc n = mascAcc n 0 1.

現在我們試著尋找 mascAcc 的尾遞迴定義。 當 n := 0, mascAcc 0 a b = a + b. 當 n 為非零的偶數，可以將它代換為 2 * n。我們推導：

      mascAcc (2*n) a b
 ===  a + b * masc (2 * n)
 ===   {- masc 之定義 -}
      a + b * 2 * masc n
 ===  mascAcc n a (2 * b) 

而當 n 為奇數，可以寫成 1 + 2 * n 的形式：

      mascAcc (1+2*n) a b
 ===  a + b * masc (1 + 2 * n)
 ===    {- masc 之定義 -}
      a + b * (n + masc n)
 ===    {- (*) 分配入 (+), (+) 之結合律 -}
      (a + b * n) + b * masc n
 ===  mascAcc n (a + b * n) b 

因此我們有了如下的尾遞迴定義：

mascAcc 0 a b  = a + b
mascAcc n a b  | even  n = mascAcc (n `div` 2) a (2 * b)
               | odd   n = mascAcc (n `div` 2) (a + b * (n `div` 2)) b 

在推導 mascAcc 的過程中使用了各種四則運算的性質，但總之目標是將式子整理回 a + b * masc n 的形式，以便收回成為 mascAcc。

fusc :: Nat -> Nat
fusc 0            = 0
fusc 1            = 1
fusc (2 * n)      = fusc n
fusc (1 + 2 * n)  = fusc n + fusc (1 + n)

 fuscAcc n a b = a * fusc n + b * fusc (1 + n) 

      fuscAcc (2 * n) a b
 ===  a * fusc (2 * n) + b * fusc (1 + 2 * n)
 ===    {- fusc 之定義 -}
      a * fusc n + b * (fusc n + fusc (1 + n))
 ===    {- 四則運算 -}
      (a + b) * fusc n + b * fusc (1 + n)
 ===  fuscAcc n (a + b) b 

      fuscAcc (1 + 2 * n) a b
 ===  a * fusc (1 + 2 * n) + b * fusc (2 + 2 * n)
 ===  a * fusc (1 + 2 * n) + b * fusc (2 * (1 + n))
 ===    {- fusc 之定義 -}
      a * (fusc n + fusc (1 + n)) + b * fusc (1 + n)
 ===    {- 四則運算 -}
      a * fusc n + (a + b) * fusc (1 + n)
 ===  fuscAcc n a (a + b) 

fuscAcc 0 a b  = b
fuscAcc n a b  | even  n = fuscAcc (n `div` 2) (a + b) b
               | odd   n = fuscAcc (n `div` 2) a (a + b) 

mapAcc f []      ys = ys
mapAcc f (x:xs)  ys = mapAcc f xs (ys++[f x]) 

mapAcc f []      ys = reverse ys
mapAcc f (x:xs)  ys = mapAcc f xs (f x : ys) 

mapAcc :: (a -> b) -> List a -> List b -> List b
mapAcc f xs ys = reverse ys ++ map f xs 

      mapAcc f xs ys
 ===  reverse ys ++ map f (x:xs)
 ===  reverse ys ++ (f x : map f xs)
 ===  (reverse ys ++ [f x]) ++ map f xs
 ===  reverse (f x : ys) ++ map f xs
 ===  mapAcc f xs (f x : ys) 

5.6.5 尾遞迴的效率考量

如前一節所述，歸納定義的 sum 需用堆疊（或其他功能相當的機制）記下每個遞迴呼叫的結果該怎麼加工。 這會佔用與輸入串列長度成正比的額外空間，相當不理想 --- 直覺上，「將一個串列加總」應該是只需定量的額外空間即可完成的計算。 尾遞迴的 sumAcc 則只需用一個變數存放目前為止的總和，當串列走訪到底，可直接將這個總和傳到最上層，似乎合理多了。 因此，在以效率為考量的函數語言程式庫中，諸如加總、算最小值等等的函數幾乎都是以尾遞迴方式寫成的。 大部分函數語言使用及早求值 --- 在呼叫一個函數之前，總是把其參數先算成範式（見第1.1 節，第頁）。 對這些語言來說，在上述場合使用尾遞迴函數確實只使用了定額的額外空間，效果相當好。

但對使用惰性求值的 Haskell 來說，情況又更複雜一些 --- 若以分析工具實測，我們會發現純以本章的方式寫出的 sumAcc 仍用了和串列長度成正比的記憶體空間！ 這是怎麼回事呢？ 如前所述，sumAcc [1,2,3,4...] 0 的值是 ((((0 + 1) + 2) + 3) + 4) + .... 串列越長，這個式子越長。 根據惰性求值的原則，Haskell 不拖到被強迫求值的最後一刻是不會將算式歸約的。 因此在走訪串列的過程中，0+1 不會歸約成 1, (0 + 1) + 2 不會歸約成 3... 這個大算式就這麼存放在記憶體中。 直到整個串列被走訪完，sumAcc 的呼叫者要檢查其傳回值了（可能是要將它印出來，或著做樣式配對），這個大算式才又一步步被化簡成一個單一數值。

為改善這類情況下的效率，Haskell 提供了一些方法讓我們早點把一些數值強迫算成範式。 例如在資料型別上標注某些欄位為「嚴格(strict)」的、使用內建函數 seq 將數值歸約、或甚至使用更低階、屬於特定編譯器的「無盒型別(unboxed type)」等等。 對實務導向的 Haskell 編程員來說這些都是實用的技巧，只是已超出本書的範疇。

如果函數傳回的不是數值，而是結構化的資料，而程式語言支援惰性求值，情形又有所不同。 如習題 5.30 中所見，我們可用尾遞迴的方式做 map f:

mapAcc f []      ys = reverse ys
mapAcc f (x:xs)  ys = mapAcc f xs (f x : ys) 

乍看之下，這個程式的問題似乎是需要多做一次 reverse。 但這可能並不很嚴重：reverse 也可用 revcat 實作，在線性時間內完成。 該定義和原歸納定義的 map f 的最大差別是：mapAcc f 需等到輸入串列整個被走訪完畢後才會開始傳回第一個結果。而回顧 map f 的歸納定義：

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

歸納狀況中，f x : ... 可在走訪到 x 時便先產生。考慮這樣的程式： length . filter p . map f。根據惰性求值，f x : ... 會立刻被 filter 與 length 接收，然後才開始計算 map f xs. 因此 map f 回傳的中間串列其實並不會被完整地產生。 在大部分情況下，歸納定義的 map f 是比尾遞迴的 mapAcc f 更有效率的函數。 在許多情形中，早點產生部分的結果、早點讓它被使用掉，會是在空間與時間上都更有效率的做法。

5.6.6 函數作為串列

既然說到串列反轉，本節延伸介紹一個相關且相當有用的技巧。 回顧 revcat 的尾遞迴定義，若將最後一個參數省去，其定義可改寫成：

revcat :: List a -> (List a -> List a)
revcat []      = id
revcat (x:xs)  = revcat xs . (x:) 

revcat 是一個傳回 List a -> List a 的函數。 在基底狀況，revcat [] 傳回 id. 歸納狀況中，revcat xs 傳回的函數和 (x:) 組合在一起。 這和 reverse 其實很像：在基底狀況，reverse [] 傳回空串列 [], 歸納狀況中，reverse (x:xs) 傳回 reverse xs ++ (x:[])。 好像把空串列代換成 id, 把 (++) 變成 (.), 我們就得到 revcat 了。

這令我們聯想：有沒有可能把 List a -> List a 視為串列的另一種表示法， 其中 id 就是空串列，而串列連接就是 (.) 呢？ 定義：

type DList a = List a -> List a 

一個型別為 DList a 的函數 f 表示一個「尾段尚未確定」的串列 --- 餵給它一個尾巴 ys, f ys 便會傳回一個真正的串列。 若 xs 是一個型別為 List a 的串列， (xs ++) 便是如此的一個 DList a. 要將一個 DList a 轉成 List a, 則只需將 [] 傳進去即可。 下列兩個函數幫我們在這兩種表示法之間作轉換：

toDList :: List a -> DList a
toDList xs = (xs ++) 

toList :: DList a -> List a
toList xs = xs [] 

空串列被轉換成 ([]++), 化簡一下之後確實得到了 id. 「含一個單一元素 x」的 DList 可寫成 (x:) --- 給任何串列，(x:) 把 x 接到其最左邊。

兩個 DList a 如何連接在一起呢？使用函數組合 (.)。 確實，(xs++) . (ys ++) 是一個接收任一個尾段 ws, 傳回 xs ++ (ys ++ ws) 的函數。 DList 版本的 cons'' 建構元則可定義成 % 我們可定義 |DList| 版本的空串列與cons'' 建構元如下：

nil :: DList a
nil = id 

cons :: a -> DList a -> DList a
cons x xs = (x:) . xs 

List 上的 (++) 若往左結合，效率會較不好。 例如 (xs ++ ys) ++ zs 會需要把 xs 走訪兩次。 DList 的情況呢？ 考慮 ((xs ++) . (ys ++)) . (zs ++)，其中左邊的兩個 DList 被括在一起。 我們演算看看給了一個尾端 ws 後的情況：

     ((xs ++) . (ys ++)) . (zs ++) $ ws
===    {- (.) 之定義 -}
     (xs ++) . (ys ++) $ zs ++ ws
===    {- (.) 之定義 -}
     (xs ++) $ ys ++ (zs ++ ws)
===  xs ++ (ys ++ (zs ++ ws)) 

由於 (.) 的定義，即使 (xs ++) . (ys ++) 先被組合在一起，我們仍得到括號往右括的 xs ++ (ys ++ (zs ++ ws))！

我們多研究一個例子。 在習題 5.7 中，給定一個 ETree a, 我們想傳回其所有的標記。 如果寫成 tips (Bin t u) = tips t ++ tips u，當樹往左邊傾斜時，程式會需要 $O(n^2)$ 的時間。 但如果我們改用 DList:

tipsD :: ETree a -> DList a
tipsD (Tip x)    = (x:)
tipsD (Bin t u)  = tipsD t . tipsD u 

上述函數會邊走訪輸入的樹，邊產生一個結構與輸入樹相同的 DList。 例如，考慮如下的樹：

t = Bin  (Bin  (Bin (Tip 5) (Tip 4))
               (Bin (Tip 3) (Tip 2)))
         (Tip 1)

tipsD t 將會是 (((5:). (4:)) . ((3:) . (2:))) . (1:) -- 結構和 t 相同，只是將 t 的每個 Tip x 代換成 (x:), 每個 Bin 代換成 (.). 但當我們傳一個空串列進去，這個由 (x:) 和 (.) 形成的「樹」將被走訪一遍，並在線性時間內得到 5:4:3:2:1:[]。 事實上，如果我們為 tipsD 補一個參數並展開，我們將得到和習題 5.21 中一樣的結果。 有了 tipsD, 我們可將原有的 tips 改定義為 tips = toList . tipsD, 或著 tips t = tipsD t [].

Hughes [1986]

ddD :: ETree a -> (DList a, Nat)
ddD t = let (xs, n) = dd t in ((\zs -> xs++zs), n) 

      ddD (Bin t u)
 ===    {- ddD 之定義 -}
      let (xs, n) = dd (Bin t u) in ((xs++), n)
 ===    {- dd 之定義 -}
      let  (xs, m) = dd t
           (ys, n) = dd u
      in (  ((if m < n then xs else if m == n then xs ++ ys else ys)++),
            1 + (m ↑ n))
 ===    {- 函數應用分配入 if -}
      let  (xs, m) = dd t
           (ys, n) = dd u
      in (  if m < n then (xs++) else if m == n then (xs ++ ys ++) else (ys++),
            1 + (m ↑ n))
 ===    {- 抽出 (xs++) 與 (ys++) -}
      let  (f, m) = (let (xs, m) = dd t in ((xs++), m))
           (g, n) = (let (ys, n) = dd u in ((ys++), n))
      in (  if m < n then f else if m == n then f . g else g,
            1 + (m ↑ n))
 ===    {- ddD 之定義 -}
      let  (f, m) = ddD t
           (g, n) = ddD u
      in (  if m < n then f else if m == n then f . g else g,
            1 + (m ↑ n)) 

ddD (Tip x)    = ((x:), 0)
ddD (Bin t u)  | m <  n  = (f, 1 + n)
               | m == n  = (f . g, 1 + n)
               | m >  n  = (g, 1 + m) 
  where ((f,m),(g,n)) = (ddD t, ddD u)