列表

列表是有序的元素序列。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]

此外，我们有一个名为 iter 的 map 的命令式模拟。它采用类型为 '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 返回列表中第一个匹配给定谓词的元素（谓词是一个测试函数，在给定一个元素时返回真或假）。如果找不到这样的元素，则会引发异常。

# 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 再次接受一个谓词并针对列表中的每个元素进行测试，但这次返回所有测试结果为真的元素的列表。

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

如果我们还想了解哪些元素测试结果为假，我们可以使用 partition，它返回一对列表：第一个是谓词为真的元素列表，第二个是谓词为假的元素列表。

# 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 模块中的这些函数对于通常很小的列表很有用，并且具有其他优点：由于它们只是对的列表，因此可以轻松地构建和修改它们。它们也很容易在顶层打印。

# 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>

在此示例中，初始累加器是第二个列表，第一个列表的每个元素依次连接到它。您可以看到 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>

在标准库文档中，未标记尾递归的函数。