5.2 關於執行效率

有點意外地，本書直到現在才較正式地談執行效率。 在本書中，我們假設數字四則運算、邏輯運算元等等都可在常數時間內完成。 資料結構方面，使用資料建構元或對其做樣式配對都只需要常數時間。 例如，將 x 與 y 做成 (x,y) 是常數時間內可完成的動作；一個型別是序對的值如果已經是弱首範式，將其配對成 (x,y) 以取出其中的 x 和 y 也只需要常數時間。 如果有資料結構定義 data T = A | B, 給一個已經是弱首範式的 x :: T, 只需常數時間便可判斷它究竟是 A 還是 B.

回顧 List 的定義：

data List a = [] | a : List a 

我們可看出這是一個偏一邊的表示法。 對於串列的左邊的操作都可以在常數時間內完成。 因此，我們可在常數時間內判斷一個串列 xs 究竟是 [] 還是可分解成頭和尾； 產生 [] 只需要常數時間；在 xs 的左邊添加一個元素，傳回 x:xs，也是常數時間內可完成的動作。 但如果我們要拿出某串列最右邊的元素，或著在串列的右邊加東西呢？回顧 (++) 的定義：

(++) :: List a -> List a -> List a
[]      ++ ys  = ys
(x:xs)  ++ ys  = x : (xs ++ ys) 

若我們試著看看 [1,2,3] ++ [4,5] 是怎麼被算出來的

   (1 : 2 : 3 : []) ++ (4 : 5 : [])
=  1 : ((2 : 3 : []) ++ (4 : 5 : []))
=  1 : 2 : ((3 : []) ++ (4 : 5 : []))
=  1 : 2 : 3 : ([] ++ (4 : 5 : []))
=  1 : 2 : 3 : 4 : 5 : [] 

可發現 (++) 需把第一個參數從頭到尾走過一遍。 因此，若第一個參數的長度是 n，(++) 是一個時間複雜度為 $O(n)$ 的函數。 函數 last 的情況也類似。

諸如 sum, length, maximum 之類的函數將串列從頭到尾走過一次。 當輸入串列長度為 n, 它們均需時 $O(n)$。如果函數 f 需時 $O(t)$，map f 需時 $O(t\times n)$. 函數 filter p, takeWhile p 等等在最壞情況下需將串列走完，因此它們也是需要線性時間的函數。 函數 zip 需要的時間與兩個串列中較短者成正比。

在習題 2.5 中，我們曾請讀者定義一個函數 reverse :: List a -> List a，將輸入的串列反轉，例如 reverse [1,2,3,4,5] = [5,4,3,2,1]. 一個可能的答案如下：

reverse []      = []
reverse (x:xs)  = reverse xs ++ [x] 

這個程式的效率如何呢？我們看看 reverse [1,2,3,4] 如何被歸約：

   reverse [1,2,3,4]
=  reverse [2,3,4] ++ [1]
=  (reverse [3,4] ++ [2]) ++ [1]
=  ((reverse [4] ++ [3]) ++ [2]) ++ [1]
=  (((reverse [] ++ [4]) ++ [3]) ++ [2]) ++ [1]
=  ((([] ++ [4]) ++ [3]) ++ [2]) ++ [1] 

為了把 [1] 接在左邊，(++ [1]) 需要走過一個長度為 3 的串列。 而在那之前，(++ [2]) 需要走過一個長度為 2 的串列。 推廣說來，要反轉一個長度為 n 的串列，(++) 會被使用 $O(n)$ 次。每個 (++) 左邊的串列長度也是 $O(n)$，因此 reverse 是一個需時 $O(n^2)$ 的演算法！ 「反轉串列」這個看來很基本的操作竟需要 $O(n^2)$ 的時間，似乎令人難以接受。 是否有更快的做法呢？我們將在第 5.6 節討論到。

data ETree a  = Tip a | Bin (ETree a) (ETree a) 

tips :: ETree a -> List a
tips (Tip x)    = [x]
tips (Bin t u)  = tips t ++ tips u 

t = Bin (Tip 1) (Bin (Tip 2) .. (Bin (Tip (n-1)) (Tip n))) 

u =  Bin (Bin (... (Bin (Bin (Tip 1) (Tip 2)) (Tip 3)))...
       (Tip (n-1))) (Tip n)