初探 list 操作

撰寫程式的目的，經常是為了處理一組資料，整理資料最基本的資料結構是 list，因此這邊先來認識 Haskell 的 list 基本操作。

list 操作

要建立一個 list，可以使用 []，例如，[1, 2, 3, 4, 5]、['a', 'b', 'c']，只要元素型態相同，就可以放在同一個。例如：

ghci> [1, 2, 3, 4, 5]
[1,2,3,4,5]
ghci> ['a', 'b', 'c']
"abc"
ghci> :t ['a', 'b', 'c']      
['a', 'b', 'c'] :: [Char]
ghci> :t "abc"          
"abc" :: String

['a', 'b', 'c'] 建立後，在 ghci 顯示 "abc"？這是字串？是的！"abc" 是 ['a', 'b', 'c'] 的語法蜜糖，型態 String 只是 [Char] 的別名。

以下的 list 的建立會失敗，因為元素不是同一型態：

ghci> [1, 'a']

<interactive>:14:2: error:
    ‧ No instance for (Num Char) arising from the literal ‘1’
    ‧ In the expression: 1
      In the expression: [1, 'a']
      In an equation for ‘it’: it = [1, 'a']
ghci>

list 可以使用 ++ 串接，使用 : 在 list 的首元素前，再前置一個元素，使用 == 可以比較 list 內容是否相同：

ghci> let lt1 = [1, 2, 3]
ghci> let lt2 = [4, 5, 6]
ghci> let lt3 = [1, 2, 3]
ghci> lt1 ++ lt2
[1,2,3,4,5,6]
ghci> 0 : lt1
[0,1,2,3]
ghci> -1 : 0 : lt1
[-1,0,1,2,3]
ghci> lt1 == lt2
False
ghci> lt1 == lt3
True
ghci> "abc" == ['a', 'b', 'c']
True

可以一直用 : 不斷地在 list 前置元素，之後會也看到，[1, 2, 3] 其實就是 1:2:3:[] 的語法蜜糖，[] 是個空 list，真正在構造時，其實是透過 : 函式遞迴地在 [] 前置元素。

類似地，[1, 2, 3] ++ [4, 5, 6] 時，其實是遞迴地在 [4, 5, 6] 前置元素，也就是 1:2:3:[4, 5, 6] 這樣的過程，因此，如果 ++ 左邊是個很長的 list 時，就會有效能上的問題，日後你更熟悉 Haskell 之後，可以思考調整演算過程，想辦法改用 : 來取得效能改進。

方才談到，"abc" 只是 ['a', 'b', 'c'] 的語法蜜糖，因此比較 "abc" == ['a', 'b', 'c'] 結果是 True，而 ++ 等函式，都可以套用在字串上。

list 若要能比較，元素必須具備可比較的行為，就相等性比較的 ==、/= 函式而言，元素至少要具備 Eq 的行為，若想以 >、<、>=、<= 等函式來比較順序的話，元素要具備 Ord 的行為：

ghci> :t (==)
(==) :: Eq a => a -> a -> Bool
ghci> :t (/=)
(/=) :: Eq a => a -> a -> Bool
ghci> :t (>)  
(>) :: Ord a => a -> a -> Bool
ghci> :t (>=)
(>=) :: Ord a => a -> a -> Bool
ghci>

存取元素

list 是有順序、具索引的資料結構，若想指定索引取得元素，要使用 !! 函式，索引是從 0 開始。例如，[10, 20, 30] !! 1 結果就是 20。

如果要取得 list 第一個元素，雖然可以使用 !! 指定索引 0，不過建議使用 head 函式比較具可讀性，如果要取得尾 list，也就是扣掉第一個元素之後的子 list，可以使用 tail：

ghci> let lt = [10, 20, 30, 40, 50]
ghci> lt !! 0 
10
ghci> head lt
10
ghci> tail lt
[20,30,40,50]
ghci>

[] 代表空 list，怎麼判斷 list 是否為空，可以使用 list == []，不過建議使用 null 函式會比較具可讀性。例如：

ghci> let lt = [10, 20, 30, 40, 50]
ghci> if (null lt) then 0 else 1
1
ghci>

來寫個 leng 吧！

如果想計算 list 的長度呢？若你只有使用過命令式的語言的經驗，可能會馬上被卡住，純函數式的 Haskell，變數是指數學上的變數，也就是不會有 x = x + 1 這種事，若不能有 x = x + 1 的行為，那麼怎麼計數呢？例如，計算一個 list 的長度？就命令式而言，例如 Python，一般會這麼寫：

def leng(lt):
    count = 0
    for _ in lt:
        count = count + 1
    return count

lt = [1, 3, 2, 5, 8]
length = leng(lt)

那我就要問你了，上面這個 leng，以白話來描述，你做了什麼呢？你走訪 lt，有元素時遞增 1，直到沒有元素為止，對吧！也就是說，你知道資料的結構可以從頭至尾走訪，而且你知道該重複什麼流程。

如果不能有 x = x + 1 的行為，那麼就無法使用迴圈來完成以上的任務；然而，走訪 lt，有元素時遞增 1，直到沒有元素為止，這個動作不依賴迴圈，還是能做到的：

leng :: [a] -> Int
leng lt =
    if null lt
        then 0
        else 1 + (leng $ tail lt)

main = do
    putStrLn $ show $ leng []         -- 顯示 0
    putStrLn $ show $ leng [1, 2]     -- 顯示 2
    putStrLn $ show $ leng [3, 4, 5]  -- 顯示 3

基本上，leng 幾乎就是在宣告你的需求，也就是方才粗體字部份的描述，這就是函數式程式設計常被稱為宣告式（Declarative）設計的原因。

你看到了遞迴！「遞迴只應天上有，凡人應當用迴圈」？

很多人覺得遞迴不好寫，其實那是習慣的問題，其一是思考的習慣，就命令式語言來說，許多人習慣用迴圈思考重複流程的問題，不習慣用遞迴思考重複流程的問題，這就像是有兩種工具都能解決事情，你總是習慣用其中一種來解決罷了。

另一個習慣就比較不好了，很多人習慣在迴圈中塞一堆東西，比方說，計數的同時，順便對元素進行運算，然後根據某個條件收集在另一個 list 之類，因而讓迴圈本體變得複雜，如果要將複雜的迴圈本體變成遞迴，就會困難重重。

在〈Immutable〉中，我以命令式語言為例，說明了如何採取不可變動特性，以控制應用程式的狀態，也談到了複雜迴圈如何拆解，並進一步改為遞迴的過程。

然而，若一開始就不能進行 x = x + 1 之類的動作，為了遞迴思考時的方便，你會被迫一次處理一件事，如果一次只處理一件事，那麼遞迴在設計時，就不是困難之事，因為就只是分而治之（Divide and conquer）。

以方才的 leng 來說，每次只要傳進來的 list 不為空，那麼要做的任務就是，取得尾 list 的長度加上 1，就可以得到答案了，至於尾 list 長度？那是 length' $ tail lt 的事，不關我的事！

因為 list 經常需要重複性的處理，作為初學 Haskell 的第一個資料結構，是個很好的開始，你可以從中發掘出許多有趣的模式與元素，這就在後續的文件中再來談了…