1 值、函數、與定義

1.8 串列

一個\emph{串列}(list) 抽象說來便是將零個或多個值放在一起變成一串。 串列是函數語言傳統上的重要資料結構： 早期的函數語言 LISP 便是 LISt Processing 的縮寫。 Haskell 中的串列多了一個限制：串列中的每個元素必須有同樣的型別。 本書中將「元素型別均為 a 的串列」的型別寫成 List a. Haskell 中的寫法是 [a]. 同樣地，在我的教學經驗中，將中括號同時使用在值與型別上造成不少誤解。例如學生可能認為 [1,2] 的型別是 [Int,Int] --- 其實應該是 [Int]. Hasekell 以中括號表示串列，其中的元素以逗號分隔。 例如，[1,2,3,4] 是一個型別為 List Int 的串列，其中有四個元素； [True, False, True] 是一個型別為 List Bool 的串列，有三個元素。 至於 [] 則是沒有元素的空串列（通常唸做 ``nil''），其最通用的型別為 List a， 其中 a 可以是任何型別。

串列的元素也可以是串列。例如 [[1,2,3],[],[4,5]] 的型別是 List (List Int), 含有三個元素，分別為 [1,2,3], [], 和 [4,5].

事實上，上述的寫法只是語法糖。我們可想像 Haskell 有這樣的型別定義：

data List a  =  []  |  a : List a

意謂一個元素型別為 a 的串列只有兩種可能構成方式： 可能是空串列 []，也可能是一個元素 (a) 接上另一個串列 (List a)。 後者的情況中，元素和串列之間用符號 (:) 銜接。

符號 (:) 唸作 ``cons'', 為「建構(construct)」的字首。 其型別為 a -> List a -> List a --- 它總是將一個型別為 a 的元素接到一個 List a 之上，造出另一個 List a. 上述的 [1,2,3,4] 其實是 1 : (2 : (3 : (4 : []))) 的簡寫：由空串列 [] 開始，將元素一個個接上去。 為了方便，Haskell 將 (:) 運算元視做右相依的， 因此我們可將括號省去，寫成 1 : 2 : 3 : 4 : []。

|(:)| 與 |(::)|

大部分有型別的函數語言（如 ML, Agda 等）之中， (:) 表示型別關係，(::) 則是串列的建構元。 Haskell 的前身之一是 David A. Turner 的語言 Miranda. 在其 Hindley-Milner 型別系統中，Miranda 使用者幾乎不需寫出程式的型別 --- 型別可由電腦自動推導。而串列是重要資料結構。 把兩個符號調換過來，使常用的符號較短一些，似乎是合理的設計。

Haskell 繼承了 Miranda 的語法。 然而，後來 Haskell 的型別發展得越來越複雜， 使用者偶爾需要寫出型別來幫助編譯器。 即使型別簡單，程式語言界也漸漸覺得將函數的型別寫出是好習慣。 而串列建構元的使用量並不見得比型別關係多。 但此時想改符號也為時已晚了。

無論如何，這樣的串列表示法是偏一邊的 --- 元素總是從左邊放入，最左邊的元素也最容易取出。 如果一個串列不是空的，其最左邊的元素稱作該串列的頭(head)， 剩下的元素稱作其尾(tail)。 例如，[1,2,3,4] 的頭是 1, 尾是 [2,3,4].

Haskell 中將字串當作字元形成的串列。標準函式庫中這麼定義著：

type String = List Char

意謂 String 就是 List Char。 在 Haskell 中，data 用於定義新型別，而 type 並不產生一個新的型別， 只是給現有的型別一個較方便或更顯出當下意圖的名字。 此外，Haskell 另提供一個語法糖，用雙引號表達字串。 因此，"fun" 是 ['f','u','n'] 的簡寫， 後者又是 'f':'u':'n':[] 的簡寫。

本節接下來將介紹許多與串列相關的內建函數。

1.8.1 串列解構

我們先從拆解串列的函數開始。函數 head 和 tail 分別取出一個串列的頭和尾：

head :: List a -> a
head (x:xs) = x 

tail :: List a -> List a
tail (x:xs) = xs

注意其型別：head 傳回一個元素，tail 則傳回一個串列。 例：head "fun" 和 tail "fun" 分別是字元 'f' 和字串 "un". 函數 head 和 tail 都可用樣式配對定義，但此處的樣式並不完整，尚缺 [] 的情況。 如果將空串列送給 head 或 tail，則會出現執行時錯誤。 因此，head 和 tail 都是部分函數(partial functions) --- 它們只將某些值（非空的串列）對應到輸出，某些值（空串列）則沒有。

函數 null 判斷一個串列是否為空串列。它也可用樣式配對定義如下：

null :: List a -> Bool
null []      = True
null (x:xs)  = False

本書依循 Bird [1998] 中的變數命名習慣， 將型別為串列的變數以 s 做結尾，例如 xs, ys 等等。 至於「元素為串列的串列」則命名為 xss, yss 等等。 但這只是為方便理解而設計的習慣。Haskell 本身並無此規定。

除了 head 與 tail，也有另一組函數 last 與 init 分別取出一個串列最右邊的元素，以及剩下的串列：

last  :: List a -> a 
init  :: List a -> List a

例：last "fun" 與 init "fun" 分別為字元 'n' 與字串 "fu". 但 last 與 init 的定義比起 head 與 tail 來得複雜： 記得我們的串列表示法是偏向一邊的，從左邊存取元素容易，從右邊存取元素則較麻煩。 我們會在 \todo{where} 之中談到 last 與 init 的定義。

1.8.2 串列生成

第1.8.1 節中的函數均將串列拆開。 本節之中我們來看一些生成串列的方法。 如果元素的型別是有順序的（例如Int, Char等型別），Haskell 提供了一個 方便我們依序生成串列的語法。以例子說明：

例 1.15

以下為 Haskell 的列舉語法的一些例子：

  • [0..10] 可展開為 [0,1,2,3,4,5,6,7,8,9,10].

  • 可用頭兩個元素來指定間隔量。例如 [0,3..10] = [0,3,6,9]. 注意該串列的元素不超過右界 10.

  • 在 [10..0] 之中，10 一開始就超過了右界 0, 因此得到 []. 如果想要產生由 10 倒數到 0 的串列，可這樣指定間隔：[10,9..0].

  • 字元也是有順序的，因此 ['a'..'z'] 可展開為含所有英文小寫字母的串列。

  • 至於沒有右界的 [0..] 則會展開為含 [0,1,2,3...] 的無限長串列。

函數 iterate :: (a -> a) -> a -> List a 用於產生無限長的串列： iterate f x 可展開為 [x, f x, f (f x), f (f (f x))... ].

例 1.16

一些 iterate 的例子：

  • iterate (1+) 0 展開為 [0,1,2,3...]. 其實 [n..] 可視為 iterate (1+) n 的簡寫。

  • 在例[RefUndefined]中我們會看到 [m..n] 也可用 iterate 與其他函數做出。

  • iterate not False 可得到無窮串列 [False, True, False...].

數學中描述集合時常使用一種稱作集合建構式(set comprehension)的語法。例如， {x * x | x ∈ S, odd x} 表示收集所有 x*x 形成的集合，其中 x 由集合 S 中取出，並且必須為奇數。Haskell 將類似的語法用在串列上。 同樣以例子說明：

例 1.17

串列建構式(list comprehension)的例子：

  • [x | x <- [0..9]] 表示「從[0..9]之中取出 x, 並收集 x」，可展開為 [0,1,2,3,4,5,6,7,8,9].

  • [x*x | x <- [0..10]] 的 x 來源和之前相同，但收集的是 x*x，得到 [0,1,4,9,25,36,49,64,81].

  • [(x,y) | x <- [0..2], y <- "abc"] 展開得到 [(0,'a'), (0,'b'), (0,'c'), (1,'a'), (1,'b'), (1,'c'), (2,'a'), (2,'b'), (2,'c')]. 注意序對出現的順序：先固定 x，將 y 跑過一遍，再換成下一個 x.

  • [x*x | x <- [0..10], odd x] 從[0..10]之中取出 x，但只挑出滿足 odd x 的那些，得到 [1,9,25,49,81].

例 1.18

以下算式的值分別為何？

  1. [(a,b) | a <- [1..3], b <- [1..2]].

  2. [(a,b) | b <- [1..2], a <- [1..3]].

  3. [(i, j) | i <- [1..4], j <- [(i + 1)..4]]. 這是一個有了 i <- .. 之後，i 即可在右方被使用的例子。

  4. [(i, j) | i <- [1..4], even i, j <- [(i + 1)..4], odd j].

  5. ['a' |i <- [0..10]]. 這個例子顯示 i 並不一定非得出現在被收集項目中。

答案

分別展開如下：

  1. [(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)].

  2. [(1,1),(2,1),(3,1),(1,2),(2,2),(3,2)].

  3. [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)].

  4. [(2,3)].

  5. "aaaaaaaaaaa".

串列建構式在寫程式時相當好用，但它也僅是個語法糖 --- 所有的串列建構式都可轉換為後面的章節將介紹的 map, concat, filter 等函數的組合。

1.8.3 串列上的種種組件函數

我們將在本節介紹大量與串列有關的函數。 它們常被稱做組件(combinators)函數。 每一個組件都負責一項單一、但具通用性而容易重用的功能。 它們常用來彼此結合以組出更大的程式。

介紹這些函數有兩個原因。首先，它們可用來組出許多有趣的程式。 我們將一邊逐一介紹這些函數，一邊以例子示範， 同時也逐漸帶出本章鼓勵的一種特殊編程風格。 另一個原因是在日後的章節中我們也都將以這些函數作為例子， 討論並證明關於它們的性質。

第一次閱讀的讀者可能訝異：這麼多函數，怎麼記得住？ 事實上，這些組件大都僅是把常見的編程模式具體地以形式方式表達出來。 辨識出這些模式後，不僅會發現它們其實很熟悉，對於我們日後了解其他程式也有助益。

長度   函數 length :: List a -> Int 計算串列的長度。 空串列 [] 的長度為 0. 例：length "function" = 8.

索引   函數 (!!) 的型別為 List a -> Int -> a. 給定串列 xs 和整數 i, 如果 0 <= i < length xs, xs !! i 為 xs 中的第 i 個元素，但由 0 起算。 例 "function" !! 0 = 'f', "function" !! 3 = 'c'. 如果 i > length xs, 則會成為執行期錯誤。 注意：如果 length xs = n，其中的元素編號分別為 0, 1 .. n-1.

在指令式語言中，索引是處理陣列常用的基本操作。 處理陣列的常見模式是用一個變數i指向目前正被處理的元素，將a[i]的值讀出或覆寫， 然後更新i的值。 但由接下來的許多範例中，讀者會發現本章盡量避免這種做法。 也因此 (!!) 在本章中使用的機會不多。

連接   函數 (++) :: List a -> List a -> List a 將兩個串列相接。 例：[1,2,3] ++ [4,5] = [1,2,3,4,5].

函數 (++) 和 (:) 似乎都是把串列接上東西。兩者有什麼不同呢？ 答案是：(:) :: a -> List a -> List a 永遠把一個元素接到串列的左邊， 而 (++) 把兩個串列接在一起，兩個串列都有可能含有零個或多個元素。 例：[] ++ [4,5] = [4,5]. 事實上，(:) 是比 (++) 更基礎的操作。 在第2.4.1 節中，我們會看到 (++) 是用 (:) 定義而成的。

另一個關於連接的函數是 concat :: List (List a) -> List a：它以一個元素都是串列的串列作為輸入，將其中的串列接在一起。例：concat [[1,2,3],[],[4],[5,6]] = [1,2,3,4,5,6]. 它和 (++) 的不同之處在哪呢？顯然，(++) 總把兩個串列接在一起， 而 concat 的參數中可含有零個或多個串列。 在第2.4.1 節中，我們會看到 concat 是用 (++) 定義而成的。

取與丟   take 的型別為 Int -> List a -> List a. take n xs 取 xs 的前 n 個元素。若 xs 的長度不到 n, take n xs 能拿幾個就拿幾個. 例：take 3 "function" = "fun", take 5 "ox" = "ox".

相對地，drop n xs 丟掉 xs 的前 n 個元素。若 xs 的長度不到 n, drop n xs 能丟幾個就拿幾個. 例：drop 3 "function" = "ction", take 5 "ox" = "". 函數 drop 的型別也是 Int -> List a -> List a.

函數 take 和 drop 顯然有些關聯，但它們的關聯該怎麼具體地寫下來呢？ 一個可能是：對所有的 n 和 xs,

乍看之下似乎言之成理。但這個性質真的成立嗎？ 我們將在第2 章中討論到。

映射   map :: (a -> b) -> List a -> List b 是串列上 一個很重要的高階函數：map f xs 將 f 作用在 xs 的每一個元素上。 例：

回憶我們之前關於高階函數的討論，另一個理解方式是： map 是一個處理函數的操作。給一個「將 a 變成 b」的函數 f :: a -> b， map 將這個函數提升到串列的層次， 得到一個「將 List a 變成 List b」的函數 map f :: List a -> List b.

例 1.19

如果一個串列 xs 可分解為 ys ++ zs, 我們說 ys 是 xs 的一個前段(prefix), zs 則是 xs 的一個後段(suffix). 例如，串列 [1,2,3] 的前段包括 [], [1], [1,2], 與[1,2,3] （注意：[]是一個前段，[1,2,3] 本身也是）, 後段則包括 [1,2,3], [2,3], [3], 與 []。

試定義函數 inits :: List a -> List (List a), 計算輸入串列的所有前段。 請注意該函數的名字是 inits, 和之前介紹過的 init 不同。這是 Haskell 函式庫中使用的命名。 {\bf 提示}：目前我們可以用 map, take 和其他函數組出 inits. 在第2.6 節中將會介紹另一個做法。

答案

一種使用 map 和 take 的可能作法如下：

inits :: List a -> List (List a)
inits xs = map (\n -> take n xs) [0 .. length xs]

或著也可用串列建構式寫成 [take n xs | n <- [0.. length xs]]. 讀者可能已發現：[f x | x <- xs] 就是 map f xs.

練習 1.12

定義函數 tails :: List a -> List (List a), 計算輸入串列的所有後段。

答案
tails :: List a -> List (List a)
tails xs = map (\n -> drop n xs) [0 .. length xs]

過濾   一個型別為 a -> Bool 的函數稱作一個「述語」(predicate). 給定述語 p, filter p xs 將 xs 之中滿足 p 的元素挑出。 函數 filter 的型別為 (a -> Bool) -> List a -> List a。 例：filter even [2,5,1,7,6] = [2,6].

例 1.20

該怎麼得知一個字串中大寫字母的個數？ 將大寫字母過濾出來，計算所得串列的長度即可。如下所示：

numUpper :: String -> Int
numUpper = length . filter isUpper
例 1.21

下列算式求出$0^2$ 到 $50^2$ 的平方數（能寫成 $n^2$ 的數字）中， 結尾為 $25$ 的數字。

  filter ((==25) . (`mod` 100)) (map square [0..50])

歸約後得到 [25,225,625,1225,2025]. 其中 (==25) . (`mod` 100) 部分使用了第頁 中提到的語法。如果覺得不習慣，也可用 $\lambda$ 算式寫成：

  filter (\ n -> n `mod` 100 == 25) (map square [0..50])
例 1.22

接續上例。另一個可能寫法是先過濾出「平方之後結尾為 25」的數字， 再算這些數字的平方：

  map square (filter ((==25) . (`mod` 100) . square) [0..50])

這個算式也歸約出一樣的結果：[25,225,625,1225,2025]。

稍微推廣一些，這個例子暗示我們 filter p . map f 和 map f . filter (p . f) 似乎是等價的。 但確實如此嗎？我們也將在第2 章中討論。

例 1.23

接續上例。如果我們不僅希望找到結尾為 $25$ 的平方數，也希望知道它們是什麼數字的平方， 一種寫法如下：

  filter ((==25) . (`mod` 100) . snd) (map (fork id square) [0..50])

我們用 map (fork id square) 將每個數字與他們的平方放在一個序對中， 得到[(0,0), (1,1), (2,4), (3,9)...]. 而 filter 的述語多了一個 snd, 表示我們只要那些「第二個元素符合條件」的序對。 上式化簡後可得到 [(5,25), (15,225), (25,625), (35,1225), (45,2025)]. 運算元 fork 的定義詳見第頁。

述語 (==25) . (`mod` 100) . snd 可以展開為 (\(i,n) -> n `mod` 100 == 25).

取、丟、與過濾   函數 takeWhile, dropWhile 和 filter 有一樣的型別。

takeWhile  :: (a -> Bool) -> List a -> List a 
dropWhile  :: (a -> Bool) -> List a -> List a

它們之間的差異也許用例子解釋得最清楚：

filter     even [6,2,4,1,7,8,2] = [6,2,4,8,2] 
takeWhile  even [6,2,4,1,7,8,2] = [6,2,4] 
dropWhile  even [6,2,4,1,7,8,2] = [1,7,8,2]

filter p 挑出所有滿足 p 的元素； takeWhile p 由左往右逐一取出元素，直到遇上第一個不滿足 p 的元素，並將剩下的串列丟棄； dropWhile p 則與 takeWhile p 相對，將元素丟棄，直到遇上第一個不滿足 p 的元素。 直覺上，後兩者似乎也應該滿足 takeWhile p xs ++ dropWhile p xs = xs, 但這仍尚待驗證。

例 1.24

給定整數 m 與 n, [m..n] 可視為 takeWhile (<= n) (iterate (1+) m) 的簡寫。

例 1.25

讀者也許覺得 takeWhile 或 dropWhile 似乎和迴圈有密切關係。 確實，利用 iterate 與 dropWhile，我們可定義出類似 while 迴圈的操作：

until :: (a -> Bool) -> (a -> a) -> a -> a
until p f = head . dropWhile (not . p) . iterate f

until p f x 由 x 算出 f x, 由 f x 算出 f (f x) ... 直到 p (f (f .. x)) 成立為止。例： until ((> 50) . square) (1+) 0 得到 8, 因為 $8^2 = 64$, 是第一個平方大於 $50$ 的非負整數。 由於惰性求值，iterate f 在意義上雖然是個無窮串列， 但只會被執行到 dropWhile (not . p) 擷取的長度為止。

下述函數則實作了用輾轉相減法求最大公因數的古典演算法。函數 minus 不斷 將大數減去小數，直到兩數相等為止：

gcd :: (Int × Int) -> Int
gcd = fst . until (uncurry (==)) minus 
  where minus (x,y)  | x > y = (y, x-y)
                     | x < y = (y-x, x)

關於 uncurry 詳見第頁。

練習 1.13

試定義一個函數 squaresUpTo :: Int -> List Int, 使得 squaresUpTo n 傳回 所有不大於 n 的平方數。例：squaresUpTo 10 = [1,4,9], squaresUpTo (-1) = [].

答案
squaresUpTo :: Int -> List Int
squaresUpTo n = takeWhile (<= n) (map square [0..])

拉鍊   函數 zip :: List a -> List b -> List (a × b) 的作用可由下述例子示範：

zip [1,2,3]  "abc"  = [(1,'a'), (2,'b'), (3,'c')] 
zip [1,2]    "abc"  = [(1,'a'), (2,'b')] 
zip [1,2,3]  "ab"   = [(1,'a'), (2,'b')] 
zip [1..]    "abc"  = [(1,'a'), (2,'b'), (3,'c')] 
zip [1..]    [2..]  = [(1,2), (2,3), (3,4) ..]

zip xs ys 將串列 xs 與 ys 相對應的元素放在序對中。 如果兩個串列長度不同，zip 將其中一個用完後即停止。 zip 也能處理無限長的串列。 由於這個動作看來像是把xs與ys當作拉鍊的兩側「拉起來」，因此用拉拉鍊的狀聲詞 ``zip'' 命名。

相對地，也有一個函數 unzip :: List (a × b) -> (List a × List b)， 將「拉鍊」拉開。例：unzip [(1,'a'), (2,'b'), (3,'c')] 可得到 ([1,2,3],"abc").

許多情況下，我們不想要把兩兩對應的元素放到序對中，而是分別餵給一個二元運算子。 這時可用另一個相關函數 zipWith, 例： zipWith (+) [1,2,3] [4,5,6] = [5,7,9] 函數 zipWith 可以這樣定義：

zipWith :: (a -> b -> c) -> List a -> List b -> List c
zipWith f = map (uncurry f) . zip
練習 1.14

用 zipWith 定義 zip.

答案

\Answer zip = zipWith (,), 或 zip = zipWith (\x y -> (x,y)).

例 1.26

試定義函數 positions :: Char -> String -> List Int, 使得 positions z xs 傳回 z 在 xs 中出現的所有位置。 例：positions 'o' "hoola hooligans" = [1,2,7,8].

答案

一種可能寫法如下：

positions z = map fst . filter ((==z) . snd) . zip [0..]

我們用 zip [0..] 為輸入串列標上位置，用 filter ((==z) . snd) 取出第二個元素等於 z 的序對，最後用 map fst 取出所有位置。 注意函數合成與 currying 的使用。

例 1.27

接續上例。如果我們僅想要 z 出現的第一個位置呢？我們可以定義：

pos :: Char -> String -> Int
pos z = head . positions z

這是一個部分函數，pos z xs 傳回 positions z xs 的第一個結果。 如果 z 沒有出現，positions z xs 傳回 [], pos z xs 會得到執行期錯誤。如果 z 出現在 xs 中，由於惰性求值，pos 得到第一個位置後 positions 便會停下，不會把串列整個產生。

如果我們希望 pos 在 z 沒有出現時傳回 -1, 可以這麼做：

pos :: Char -> String -> Int
pos z xs = case positions z xs of
            []      -> -1
            (i:is)  -> i