3.3.2 介紹函數式清單

3.3.2 介紹函數式清單

    現在，使用遞歸的一般原則更舒适，那我們就詳細地看看函數式清單。剛才我們提到過，清單既可以是空的，也可以由一個元素與另一個清單組成。這意味着，我們需要一個特殊的值來表示空的清單，還有一種建構清單的方法，通過取一個現有清單，并在它的前面加上一個元素。第一個選項（空清單）有時稱為 nil，第二個選項産生 cons cell（是構造的清單單元格縮寫，constructed list cell）。你可以在圖 3.1 中看到示例列建表，由一個空清單和 cons cell 構成。

圖 3.1 一個函數式包含清單 6、 2、 7 和 3。矩形表示 cons cell，它包含一個值和對清單其餘部分的引用。最後的cons cell 引用一個特殊值，表示一個空清單。

    正如你在圖 3.1 中所看到的，每個 cons cell 存儲這個清單單個值（稱為頭），和對清單其餘部分（稱為尾）的引用，它既可以是另一個 cons cell，也可以是一個空清單（nil）。讓我們現在看看 F# 提供的建立清單的幾種方法：

> let ls1 = []
val ls1 : 'a list = []
> let ls2 = 6::2::7::3::[]
val ls2 : int list = [6; 2; 7; 3]
> let ls3 = [6; 2; 7; 3]
val ls3 : int list = [6; 2; 7; 3]
> let ls4 = [1 .. 5]
val ls4 : int list = [1; 2; 3; 4; 5]
> let ls5 = 0::ls4
val ls5 : int list = [0; 1; 2; 3; 4; 5]
           

    首先，建立了一個空清單，在 F# 中寫作 []。如果你看看結果，可以看到 F# 建立一個不包含元素的值。清單的類型是有點不清楚，因為，現在還不知道清單中包含的值的類型，F# 推斷該清單的類型是"某些東西"，這稱為泛型值，我們将在第 5 章讨論它。

    第二個示例更加有趣。你可以看到如何根據内容建立清單：我們取一個空清單，并使用一種建立 cons cell 的文法 ::，不像（一般的）運算符，例如 +，:: 結構是右關聯的，這意味着，它從右至左組合值。如果你按這個方向讀這個表達式，可以看到我們用 3 和一個空清單，建構了一個清單單元；然後，用 7 和這個結果，建構另一個單元，等等。輸入這個表達式以後，F# Interactive 報告，建立了一個 int list 類型的清單。這表示 ls2 值的類型是一個包含整數清單。這又是通過泛型類型完成的，可能從 C# 中得知（将詳細讨論如何在 F# 中使用它們，在稍後的時間）。

    在接下來的兩個示例中，我們使用了一塊 F# 提供的建立清單的文法糖。第一個使用方括号，清單元素以分号分隔；第二個使用點-點來建立包含一個數字序列的清單。

    最後一個例子顯示了如何使用 cons cells 建立一個清單，通過在另一個清單的開頭追加值。可以看到 ls5 包含 0 開頭，後面的所有元素都來自 ls4 清單中。

    有關函數式清單的一個重要事實就是它的們不可變。這意味着，我們可以建構一個清單（如在前面的示例中一樣），但不能取得現有的清單并修改；不能添加或删除元素。需要添加新元素或删除現有元素的函數，總是傳回一個新的清單，而不修改原始清單，因為，修改清單其實是不可能的。我們将在第 5、 6 和 10 章中看到更多有關這些函數的示例，但現在，讓我們看看如何處理現有的清單中的元素。

    在函數語言使用清單，處理清單的典型代碼包含兩個分支：

    ■ 當給定的清單是空的，執行的操作

    ■ 當參數值是 cons cell，執行的操作

    後一個分支通常執行一個計算，使用頭，并用這個清單的尾進行遞歸處理。在這一章的後面，我們将會看到所有這些通用模式，但首先，讓我們研究一下如何編寫代碼，使用模式比對在這兩個分支之間進行選擇。

用模式比對分解清單

    在 3.2.4 節中，我們在讨論有關元組的比對模式時，看到兩和不同的方法。一種方法是直接在 let 綁定中寫模式，即可以是把表達式的結果賦給一個值或，也可以是在函數參數的聲明中；另一種方法是使用 match 關鍵字。兩者的重要差別在于，使用 match，我們可以指定多個模式，有多個分支。對于清單，我們需要使用第二個方法，因為，在寫清單處理代碼時，每次需要指定兩個不同的分支，（一個用于空清單，另一個用于建立使用 cons cell）。

    下面的代碼示範了對清單的模式比對，列印一條消息，第一個元素的值，或者該清單為空時，則“Empty list”：

match list with
| [] -> printfn "Empty list"
| head::tail -> printfn "Starting with %d" head
           

    可以看到，在第二行的模式比對空清單，在第三行的模式，提取頭（第一個元素的值）和尾(頭後面的清單)。編寫這兩種模式的文法與較早時用于建立清單的文法完全相同。一個空清單用 [] 來比對，cons cell 使用:: 模式分解。第二種情況更有趣，因為，它把一個值賦給兩個新的符号，head 和 tail。将包含一個數字，通過分解第一個 cons cell 獲得的清單中的其餘部分。空清單不含任何值，是以，第一個模式不綁定值到任何符号，它隻會通知我們原始清單是空的。

    如果參考圖 3.1，就會發現，第一個模式對應于 nil 的橢圓，不包含任何值。第二個模式比對 cons cell 矩形，帶出兩個部分的内容。

    正如在元組的示例中，模式清單是完整的，這意味着，它必須選擇任意給定的清單中的一個分支。如果我們嘗試使用不完整的模式，看看會發生什麼。

Listing 3.13 An incomplete pattern matching on lists (F# Interactive)

> let squareFirst list =
match list with
| head::_ -> head * head
;;
Warning FS0025: Incomplete pattern matches on this
expression. The value '[]' will not be matched.
val sqareFirst : int list –> int
           

> squareFirst [4; 5; 6];;
val it : int = 16
           

> squareFirst []
Exception of type 'Microsoft.FSharp.Core.
MatchFailureException' was thrown.
(...)
           

    我們首先聲明一個函數 squareFirst，包含一個模式比對，隻比對 cons cell，并傳回清單中的第一個元素的平方。然而，當清單為空時，此模式不會處理這種情況。我們可以看到，F# 編譯器是很聰明的，當我們寫的模式比對可能會失敗時，能檢測到這種情況，甚至給我們這個比對将會失敗的示例。不要忽略此警告，除非你絕對肯定這種情況永遠不會發生。喟然，這個函數對于空清單來說，沒有任何合理的意義，但是，最好還是添加一個針對剩餘情況的處理程式（這種模式可以使用下劃線字，表示比對任意值），既可以觸發有額外資訊的異常，也可什麼都不做。當然，如果這個函數的傳回類型是除 unit 以外的其他任何類型，都必須給出一個合适的值傳回，即使你什麼也不做。 如果函數真的不應該用空清單調用，那麼，抛出異常通常是一個更好的主意。

    盡管有一個警告，F# Interactive 還是願意咬牙處理這個函數的，是以，我們可以嘗試調用它。首先，嘗試一和可以工作的情況，我們會看到，它行為與預期相同。如果用空清單作為參數值調用函數，match 構造不包含任何比對的模式，是以，它将觸發異常。這是一個通常的 .NET 異常，在 F# 中可以使用 try 結構造抓取。

    你應該想到，我們會從函數式清單中期望得到什麼，是以，在下一節中，我們會把注意力轉到 C# ，并使用它來詳細解釋清單。我們還會寫出第一個清單處理代碼。