列表

列表是元素的有序序列。在 OCaml 中，列表的所有元素必須是相同的類型。列表是內建於語言中的，並且具有特殊的語法。這是一個包含三個整數的列表

# [1; 2; 3];;
- : int list = [1; 2; 3]

請注意，元素之間以分號分隔，而不是逗號。空列表寫為 []。這個整數列表的類型是 int list。

列表如果不是空的，則具有頭部（第一個元素）和尾部（由其餘元素組成的列表）。在我們的例子中，頭部是整數 1，而尾部是列表 [2; 3]。空列表沒有頭部也沒有尾部。以下是一些更多的列表

# [];;
- : 'a list = []
# [1; 2; 3];;
- : int list = [1; 2; 3]
# [false; true; false];;
- : bool list = [false; true; false]
# [[1; 2]; [3; 4]; [5; 6]];;
- : int list list = [[1; 2]; [3; 4]; [5; 6]]

請注意，空列表的類型是 'a list（其元素類型未知）。另請注意最後一個列表的類型 - int list list 或整數列表的列表。

列表上有兩個內建運算子。 :: 或 cons 運算子，將一個元素添加到列表的前面。 @ 或 append 運算子將兩個列表合併

# 1 :: [2; 3];;
- : int list = [1; 2; 3]
# [1] @ [2; 3];;
- : int list = [1; 2; 3]

列表上的函數

我們可以透過模式匹配來編寫對列表進行操作的函數

# let rec total l =
    match l with
    | [] -> 0
    | h :: t -> h + total t;;
val total : int list -> int = <fun>
# total [1; 3; 5; 3; 1];;
- : int = 13

考慮一個尋找列表長度的函數

# let rec length l =
    match l with
    | [] -> 0
    | _ :: t -> 1 + length t;;
val length : 'a list -> int = <fun>

此函數不僅適用於整數列表，也適用於任何類型的列表。

# length [1; 2; 3];;
- : int = 3
# length ["cow"; "sheep"; "cat"];;
- : int = 3
# length [[]];;
- : int = 1

為什麼會這樣？因為在模式 _ :: t 中，不檢查列表的頭部，因此其類型無關緊要。這種函數稱為多型的。這是另一個多型函數，我們自己的 @ 運算子版本，用於附加

# let rec append a b =
  match a with
  | [] -> b
  | h :: t -> h :: append t b;;
val append : 'a list -> 'a list -> 'a list = <fun>

請注意，第二個列表的記憶體是共享的，但第一個列表實際上是被複製的。

列表上的高階函數

我們可能希望將一個函數應用於列表中的每個元素，從而產生一個新的列表。我們將編寫一個函數 map，該函數以另一個函數作為其參數 - 這種函數稱為「高階」函數

# let rec map f l =
    match l with
    | [] -> []
    | h :: t -> f h :: map f t;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

請注意，類型 f 的函數在整個類型中用括號括起來。此 map 函數，給定類型為 'a -> 'b 的函數和 'a 的列表，將建立一個 'b' 的列表。當然，有時 'a 和 'b 可能是相同的類型。以下是兩個顯示 map 函數用法的範例

# map (fun x -> x * 2) [1; 2; 3];;
- : int list = [2; 4; 6]
# map total [[1; 2]; [3; 4]; [5; 6]];;
- : int list = [3; 7; 11]

標準函式庫 List 模組

標準函式庫 List 模組包含各種有用的實用函數，包括我們在本教學中編寫的許多函數的預先編寫版本。具有標籤函數的模組版本可作為 StdLabels 的一部分使用。

在 List 模組文件中，標示了可能會引發例外狀況的函數。這些例外通常是由於列表為空（因此既沒有頭部也沒有尾部）或列表長度不匹配而導致的。

映射與迭代器

我們已經從頭開始編寫了 map 函數，並且毫不奇怪，List 模組中包含了一個。還有一個用於兩個列表的變體

# List.map2 ( + ) [1; 2; 3] [4; 5; 6];;
- : int list = [5; 7; 9]

此外，我們還有一個與 map 對應的命令式版本，稱為 iter。它接受一個類型為 'a -> unit 的命令式函數和一個 'a list，並依次將該函數應用於每個元素。一個合適的函數可能是 print_endline

# List.iter print_endline ["frank"; "james"; "mary"];;
frank
james
mary
- : unit = ()

還有一個 iter2 變體也適用於兩個列表

# List.iter2
    (fun a b -> print_endline (a ^ " " ^ b))
    ["frank"; "james"; "mary"]
    ["carter"; "lee"; "jones"];;
frank carter
james lee
mary jones
- : unit = ()

請注意，如果列表長度不相等，map2 和 iter2 將會失敗

# List.map2 ( + ) [1; 2; 3] [4; 5];;
Exception: Invalid_argument "List.map2".

列表掃描

實用的函式 mem 會掃描列表的內容，以檢查給定的元素是否為列表的成員。

# List.mem "frank" ["james"; "frank"; "mary"];;
- : bool = true
# List.mem [] [[1; 2]; [3]; []; [5]];;
- : bool = true

還有更精密的掃描函式：假設我們想檢查列表中的所有元素是否為偶數，或者是否有任何元素為偶數。我們可以編寫函式來遍歷列表中的每個元素，並保持布林檢查，或者使用 mem 和我們已知的其他函式。

# let all =
    not (List.mem false (List.map (fun x -> x mod 2 = 0) [2; 4; 6; 8]));;
val all : bool = true
# let any =
    List.mem true (List.map (fun x -> x mod 2 = 0) [1; 2; 3]);;
val any : bool = true

不過，這樣做相當笨拙。標準函式庫提供了兩個有用的函式 for_all 和 exists 來解決這個常見的問題。

# List.for_all (fun x -> x mod 2 = 0) [2; 4; 6; 8];;
- : bool = true
# List.exists (fun x -> x mod 2 = 0) [1; 2; 3];;
- : bool = true

因此，您可以看到標準函式庫是如何演變成現在的狀態：常用的程式碼片段會被轉換成有用的通用函式。

列表搜尋

函式 find 會返回列表中第一個符合給定謂詞（predicate，一個測試函式，當給定一個元素時，會返回 true 或 false）的元素。如果找不到這樣的元素，它會引發例外。

# List.find (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5];;
- : int = 2
# List.find (fun x -> x mod 2 = 0) [1; 3; 5];;
Exception: Not_found.

函式 filter 同樣會接收一個謂詞，並針對列表中的每個元素進行測試，但這次會返回所有測試結果為 true 的元素的列表。

# List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5];;
- : int list = [2; 4]

如果我們也想知道哪些元素的測試結果為 false，我們可以使用 partition，它會返回一個列表對：第一個列表包含謂詞測試結果為 true 的元素，第二個列表包含謂詞測試結果為 false 的元素。

# List.partition (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5];;
- : int list * int list = ([2; 4], [1; 3; 5])

請注意，filter 和 partition 的文件說明告訴我們，輸入的順序會保留在輸出中。如果文件中沒有說明，則不能假設這一點。

關聯列表

關聯列表是一種簡單（且簡陋）的方式來實作字典資料結構：也就是說，一組帶有相關值的鍵。對於大型字典，為了效率，我們會使用標準函式庫的 Map 或 Hashtbl 模組。但是，來自 List 模組的這些函式對於通常很小的列表很有用，並且具有其他優點：由於它們只是成對的列表，因此可以輕鬆地建立和修改。它們也很容易在 toplevel 中印出。

# List.assoc 4 [(3, "three"); (1, "one"); (4, "four")];;
- : string = "four"
# List.mem_assoc 4 [(3, "three"); (1, "one"); (4, "four")];;
- : bool = true

當使用關聯列表以及用於其他目的時，有時能夠從一對列表建立成對的列表，反之亦然會很有用。List 模組提供了函式 split 和 combine 來實現此目的。

# List.split [(3, "three"); (1, "one"); (4, "four")];;
- : int list * string list = ([3; 1; 4], ["three"; "one"; "four"])
# List.combine [3; 1; 4] ["three"; "one"; "four"];;
- : (int * string) list = [(3, "three"); (1, "one"); (4, "four")]

列表排序

函式 List.sort，給定一個類型為 'a -> 'a -> int 的比較函式（相等則為零，第一個較小則為負數，第二個較小則為正數）和一個類型為 'a list 的輸入列表，會根據比較函式返回排序後的列表。通常，我們使用內建的比較函式 compare，它可以比較任何兩個相同類型的值（除了無法比較的函式）。

# List.sort compare [1; 4; 6; 4; 1];;
- : int list = [1; 1; 4; 4; 6]
# List.sort compare ["Reynolds"; "Smith"; "Barnes"];;
- : string list = ["Barnes"; "Reynolds"; "Smith"]
# List.sort (Fun.flip compare) [1; 4; 6; 4; 1];;
- : int list = [6; 4; 4; 1; 1]
# List.sort compare [(1, 3); (1, 2); (2, 3); (2, 2)];;
- : (int * int) list = [(1, 2); (1, 3); (2, 2); (2, 3)]
# List.sort
    (fun a b -> compare (fst a) (fst b))
    [(1, 3); (1, 2); (2, 3); (2, 2)];;
- : (int * int) list = [(1, 3); (1, 2); (2, 3); (2, 2)]

函式 Fun.flip 會反轉二元函式的參數順序。

摺疊

List 模組中有兩個名稱有趣的函式，fold_left 和 fold_right。它們的作用是使用給定的函式將列表的元素組合在一起，累積一個結果並返回。返回的結果取決於給定的函式、列表的元素和提供的累積器的初始值。因此，您可以想像這些是非常通用的函式。讓我們首先探索 fold_left。

在此範例中，我們提供加法函式和 0 的初始累積器值。

# List.fold_left ( + ) 0 [1; 2; 3];;
- : int = 6

結果是列表中元素的總和。現在，讓我們使用 OCaml 的內建 max 函式，它會返回兩個給定整數中較大的值，而不是我們的加法函式。我們使用 min_int，即最小的可能整數，作為我們的初始累積器。

# List.fold_left max min_int [2; 4; 6; 0; 1];;
- : int = 6

找到列表中最大的數字。讓我們看看 fold_left 函式的類型。

# List.fold_left;;
- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

函式的類型為 'a -> 'b -> 'a，其中 'a 是累積器，'b 是列表的每個元素的類型。下一個參數是初始累積器，其類型必須為 'a，最後是類型為 'b list 的輸入列表。結果是累積器的最終值，因此它的類型必須為 'a。當然，在我們的兩個範例中，'a 和 'b 是相同的。但情況並非總是如此。

考慮以下使用 fold_right 定義的 append（fold_left 從左側考慮元素，fold_right 從右側考慮元素）：

# let append x y =
    List.fold_right (fun e a -> e :: a) x y;;
val append : 'a list -> 'a list -> 'a list = <fun>

在此範例中，初始累積器是第二個列表，而第一個列表的每個元素依次被 consed 到它。您可以看到 fold right 參數的順序略有不同。

# List.fold_right;;
- : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

函式首先出現，然後是元素列表，然後是初始累積器值。我們可以使用 fold_right 來定義我們常用的 map 函式。

# let map f l =
    List.fold_right (fun e a -> f e :: a) l [];;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

但是需要小心。如果我們嘗試使用 List.concat，它會將列表的列表透過將列表連接在一起來轉換成一個列表，我們會產生以下結果：

# let concat l = List.fold_left ( @ ) [] l;;
val concat : 'a list list -> 'a list = <fun>

不幸的是，此處的求值順序是將越來越大的項目作為第一個參數傳遞給 @ 運算子，因此該函式的執行時間比 List.concat 更差。您可以在標準容器的比較中閱讀有關列表和其他常見 OCaml 資料結構的時間和空間效率的更多資訊。

以下是一些以 fold_left 或 fold_right 表示的熟悉函式的更多重新定義。您能找出它們是如何運作的嗎？

# let length' l =
    List.fold_left (fun a _ -> a + 1) 0 l;;
val length' : 'a list -> int = <fun>
# let rev' l =
    List.fold_left (fun a e -> e :: a) [] l;;
val rev' : 'a list -> 'a list = <fun>
# let split' l =
    List.fold_right
      (fun (x, y) (xs, ys) -> (x :: xs, y :: ys))
      l
      ([], []);;
val split' : ('a * 'b) list -> 'a list * 'b list = <fun>

列表和尾遞迴

先前定義的 length 函式 建立了一個大小與其輸入列表成比例的中間運算式。

   length [1; 2; 3]
=> 1 + length [2; 3]
=> 1 + (1 + length [3])
=> 1 + (1 + (1 + length []))
=> 1 + (1 + (1 + 0))
=> 1 + (1 + 1)
=> 1 + 2
=> 3

注意 上面不是 OCaml 語法，而是一個草圖，旨在解釋如何評估 length [1; 2; 3]。符號 => 表示一個評估步驟。

對於長列表，這可能會導致堆疊溢位（對電腦來說太大而無法處理）。解決方案是使用累加參數編寫我們的函式，如下所示：

# let rec length acc l =
    match l with
    | [] -> acc
    | _ :: t -> length (acc + 1) t;;
val length : int -> 'a list -> int = <fun>
# let l = length 0 [1; 2; 3];;
val l : int = 3

這個函式現在在堆疊上使用固定的空間量。

   length 0 [1; 2; 3]
=> length 1 [2; 3]
=> length 2 [3]
=> length 3 []
=> 3

我們稱這樣的函式為尾遞迴。我們可以編寫一個包裝函式，以便自動提供初始累積器值。

# let rec length_inner acc l =
    match l with
    | [] -> acc
    | _ :: t -> length_inner (acc + 1) t;;
val length_inner : int -> 'a list -> int = <fun>
# let length l = length_inner 0 l;;
val length : 'a list -> int = <fun>

或者，我們可以在一個函式中完成所有操作。

# let length l =
    let rec length_inner acc l =
      match l with
      | [] -> acc
      | _ :: t -> length_inner (acc + 1) t
    in
      length_inner 0 l;;
val length : 'a list -> int = <fun>

在標準函式庫文件中，未標記尾遞迴的函式。