第 4 章：列表与模式（Lists and Patterns）
原文：Anil Madhavapeddy and Yaron Minsky, Real World OCaml: Functional Programming for the Masses, Second Edition, Chapter 4。维护者已确认本书为开源书籍，可翻译并发布用于学习研究。
本章会聚焦 OCaml 编程中的两个常见元素：列表和模式匹配。这两者都已经在第 2 章“导览（A Guided Tour）”中讨论过，但这里会更深入一些，把两个主题放在一起讲，并用其中一个来帮助说明另一个。
4.1 列表基础（List Basics）
OCaml 列表是由相同类型元素组成的不可变、有限序列。正如已经看到的，OCaml 列表可以使用方括号和分号记法生成：
# open Base;;
# [1;2;3];;
- : int list = [1; 2; 3]
也可以用等价的 :: 记法生成：
# 1 :: (2 :: (3 :: []));;
- : int list = [1; 2; 3]
# 1 :: 2 :: 3 :: [];;
- : int list = [1; 2; 3]
可以看到，:: 运算符是右结合的，这意味着我们可以不用括号来构建列表。空列表 [] 用来终止列表。注意，空列表是多态的，意味着它可以与任意类型的元素一起使用，如下所示：
# let empty = [];;
val empty : 'a list = []
# 3 :: empty;;
- : int list = [3]
# "three" :: empty;;
- : string list = ["three"]
:: 运算符把元素附加到列表前端的方式，反映了这样一个事实：OCaml 的列表实际上是单链表。粗略地说，1 :: 2 :: 3 :: [] 会被布局成一串 cons 单元；每个单元保存当前元素的数据引用，以及指向列表剩余部分的引用，最后一个元素再指向空列表。
每个 :: 本质上都会向这个结构添加一个新块。这样的块包含两件东西：对该列表元素中数据的引用，以及对列表剩余部分的引用。这就是为什么 :: 可以在不修改列表的情况下扩展列表：扩展会分配一个新的列表元素，但不会改变任何已有元素，如下所示：
# let l = 1 :: 2 :: 3 :: [];;
val l : int list = [1; 2; 3]
# let m = 0 :: l;;
val m : int list = [0; 1; 2; 3]
# l;;
- : int list = [1; 2; 3]
4.2 使用模式从列表中抽取数据（Using Patterns to Extract Data from a List）
我们可以使用 match 表达式从列表中读取数据。下面是一个简单递归函数示例，它会计算列表所有元素的和：
# let rec sum l =
match l with
| [] -> 0
| hd :: tl -> hd + sum tl;;
val sum : int list -> int = <fun>
# sum [1;2;3];;
- : int = 6
# sum [];;
- : int = 0
这段代码遵循了用 hd 表示列表第一个元素（head，头部）、用 tl 表示列表剩余部分（tail，尾部）的约定。
sum 中的 match 表达式实际上做了两件事。第一，它作为情况分析工具，把各种可能性拆成一个由模式索引的情况列表。第二，它允许你为被匹配数据结构中的子结构命名。在这个例子中，变量 hd 和 tl 由 match 表达式第二个情况中的模式绑定。以这种方式绑定的变量，可以在该模式箭头右侧的表达式中使用。
match 表达式可以绑定新变量，这一点有时会造成困惑。为了看看这种困惑如何出现，假设我们想写一个函数，从列表中滤掉所有等于某个特定值的元素。你可能会想把代码写成下面这样，但这么做时，编译器会立刻警告你有地方不对：
# let rec drop_value l to_drop =
match l with
| [] -> []
| to_drop :: tl -> drop_value tl to_drop
| hd :: tl -> hd :: drop_value tl to_drop;;
Line 5, characters 7-15:
Warning 11 [redundant-case]: this match case is unused.
val drop_value : 'a list -> 'a -> 'a list = <fun>
此外，这个函数显然做错了事情：它会滤掉列表中的所有元素，而不只是那些等于给定值的元素，如下所示：
# drop_value [1;2;3] 2;;
- : int list = []
那么，发生了什么？
关键观察是，第二个情况中出现的 to_drop 并不意味着检查第一个元素是否等于传给 drop_value 的参数 to_drop。相反，它只是让一个新的变量 to_drop 被绑定到列表第一个元素里恰好出现的值上，从而遮蔽了之前的 to_drop 定义。第三个情况没有被使用，因为它本质上与第二个情况中的模式相同。
更好的写法不是使用模式匹配来判断第一个元素是否等于 to_drop，而是使用普通的 if 表达式：
# let rec drop_value l to_drop =
match l with
| [] -> []
| hd :: tl ->
let new_tl = drop_value tl to_drop in
if hd = to_drop then new_tl else hd :: new_tl;;
val drop_value : int list -> int -> int list = <fun>
# drop_value [1;2;3] 2;;
- : int list = [1; 3]
如果我们想丢弃某个特定字面量值，而不是丢弃传入的值，就可以使用类似原始 drop_value 实现的写法：
# let rec drop_zero l =
match l with
| [] -> []
| 0 :: tl -> drop_zero tl
| hd :: tl -> hd :: drop_zero tl;;
val drop_zero : int list -> int list = <fun>
# drop_zero [1;2;0;3];;
- : int list = [1; 2; 3]
4.3 模式匹配的限制（也是福分）（Limitations and Blessings of Pattern Matching）
前面的例子凸显了关于模式的一个重要事实：模式不能用来表达任意条件。模式可以刻画数据结构的布局，甚至可以包含字面量，如 drop_zero 示例所示，但也就到此为止了。模式可以检查一个列表是否有两个元素，但不能检查前两个元素是否彼此相等。
你可以把模式看作一种专门的子语言，它能表达一组有限但仍然相当丰富的条件。模式语言受限这一事实最终是一件好事，因为这使得编译器可以为模式构建更好的支持。尤其是，match 表达式的效率，以及编译器检测匹配错误的能力，都依赖于模式受约束的本质。
4.3.1 性能（Performance）
天真地想，你可能会认为必须按顺序检查 match 中的每个情况，才能弄清楚哪一个会触发。如果 match 的情况由任意代码守卫，那确实会如此。但 OCaml 通常能够生成机器码，基于一组高效选择的运行时检查，直接跳转到匹配的情况。
举个例子，考虑下面两个相当愚蠢的函数，它们都把整数加一。第一个使用 match 表达式实现，第二个使用一串 if 表达式实现：
# let plus_one_match x =
match x with
| 0 -> 1
| 1 -> 2
| 2 -> 3
| 3 -> 4
| 4 -> 5
| 5 -> 6
| _ -> x + 1;;
val plus_one_match : int -> int = <fun>
# let plus_one_if x =
if x = 0 then 1
else if x = 1 then 2
else if x = 2 then 3
else if x = 3 then 4
else if x = 4 then 5
else if x = 5 then 6
else x + 1;;
val plus_one_if : int -> int = <fun>
注意上面 match 中使用了 _。这是一个通配符模式，可以匹配任何值，但不会把变量名绑定到该值上。
如果对这些函数做基准测试，会看到 plus_one_if 明显比 plus_one_match 慢，而且随着情况数量增加，这个优势会变得更大。这里我们使用 core_bench 库对这些函数做基准测试；可以在命令行运行 opam install core_bench 安装它。
# #require "core_bench";;
# open Core_bench;;
# [ Bench.Test.create ~name:"plus_one_match" (fun () ->
plus_one_match 10)
; Bench.Test.create ~name:"plus_one_if" (fun () ->
plus_one_if 10) ]
|> Bench.bench;;
Estimated testing time 20s (2 benchmarks x 10s). Change using -quota SECS.
Name Time/Run
plus_one_match 34.86ns
plus_one_if 54.89ns
- : unit = ()
下面是另一个不那么人为的例子。我们可以不使用 match，而是使用 if 表达式改写本章前面描述的 sum 函数。然后使用 List 模块中的 is_empty、hd_exn 和 tl_exn 函数拆解列表，从而完全不使用模式匹配来实现整个函数：
# let rec sum_if l =
if List.is_empty l then 0
else List.hd_exn l + sum_if (List.tl_exn l);;
val sum_if : int list -> int = <fun>
同样，可以对它们做基准测试来观察差异：
# let numbers = List.range 0 1000 in
[ Bench.Test.create ~name:"sum_if" (fun () -> sum_if numbers)
; Bench.Test.create ~name:"sum" (fun () -> sum numbers) ]
|> Bench.bench;;
Estimated testing time 20s (2 benchmarks x 10s). Change using -quota SECS.
Name Time/Run
sum_if 62.00us
sum 17.99us
- : unit = ()
在这个例子中，基于 match 的实现比基于 if 的实现快很多倍。差异来自于：我们实际上需要多次做同样的工作，因为每个被调用的函数都必须重新检查列表第一个元素，以判断它是否为空单元。而使用 match 表达式时，对每个列表元素来说，这项工作只发生一次。
这是一个更一般的现象：模式匹配非常高效，并且通常比你自己手写的代码更快。
4.3.2 检测错误（Detecting Errors）
match 表达式检测错误的能力，要说的话比它的性能还重要。我们已经看到过一个 OCaml 发现模式匹配问题的例子：在损坏的 drop_value 实现中，OCaml 警告我们最后一个情况是冗余的。对于用通用语言编写的谓词，并不存在能判断它是否冗余的算法；但在模式语境中，这个问题可以可靠解决。
OCaml 还会检查 match 表达式是否穷尽。考虑如果通过删除某个情况的处理器来修改 drop_zero，会发生什么。可以看到，编译器会产生警告，说明我们漏掉了一个情况，并给出一个未匹配模式的示例：
# let rec drop_zero l =
match l with
| [] -> []
| 0 :: tl -> drop_zero tl;;
Lines 2-4, characters 5-31:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
1::_
val drop_zero : int list -> 'a list = <fun>
即使对这样简单的例子，穷尽性检查也很有用。但正如第 7 章“变体（Variants）”会看到的，当例子更复杂，尤其是涉及用户定义类型时，它们会变得更有价值。除了捕获直接错误之外，它们还会扮演一种重构工具，指引你找到需要调整代码以应对类型变化的位置。
4.4 有效使用 List 模块（Using the List Module Effectively）
到目前为止，我们已经使用模式匹配和递归函数编写了相当多的列表处理代码。在现实生活中，通常更好的做法是使用 List 模块；它充满了可复用函数，抽象出了使用列表计算时常见的模式。
我们来看一个具体例子。我们会编写函数 render_table，给定一个列标题列表和一个行列表，它会以格式良好的文本表格打印出来。完成后，得到的函数应该像下面这样工作：
# Stdio.print_endline
(render_table
["language";"architect";"first release"]
[ ["Lisp" ;"John McCarthy" ;"1958"] ;
["C" ;"Dennis Ritchie";"1969"] ;
["ML" ;"Robin Milner" ;"1973"] ;
["OCaml";"Xavier Leroy" ;"1996"] ;
]);;
| language | architect | first release |
|----------+----------------+---------------|
| Lisp | John McCarthy | 1958 |
| C | Dennis Ritchie | 1969 |
| ML | Robin Milner | 1973 |
| OCaml | Xavier Leroy | 1996 |
- : unit = ()
第一步是编写一个函数，计算每列数据的最大宽度。可以通过把标题和每一行转换成整数长度列表，然后对这些长度列表逐元素取最大值来完成。直接编写所有这些代码会有点费事，但利用 List 模块中的三个函数 map、map2_exn 和 fold，我们可以相当简洁地做到。
List.map 最容易解释。它接收一个列表，以及一个用于转换该列表元素的函数，并返回一个包含转换后元素的新列表。因此，可以这样写：
# List.map ~f:String.length ["Hello"; "World!"];;
- : int list = [5; 6]
List.map2_exn 类似于 List.map，但它接收两个列表以及一个组合二者元素的函数。因此，我们可以写：
# List.map2_exn ~f:Int.max [1;2;3] [3;2;1];;
- : int list = [3; 2; 3]
名字中的 _exn 是因为当列表长度不匹配时，该函数会抛出异常：
# List.map2_exn ~f:Int.max [1;2;3] [3;2;1;0];;
Exception: (Invalid_argument "length mismatch in map2_exn: 3 <> 4")
List.fold 是三者中最复杂的，它接收三个参数：要处理的列表、初始累加器值，以及用于更新累加器的函数。List.fold 会从左到右遍历列表，每一步更新累加器，并在完成后返回累加器的最终值。可以通过查看 fold 的类型签名看到其中的一些内容：
# List.fold;;
- : 'a list -> init:'accum -> f:('accum -> 'a -> 'accum) -> 'accum = <fun>
我们可以用 List.fold 做像列表求和这样简单的事情：
# List.fold ~init:0 ~f:(+) [1;2;3;4];;
- : int = 10
这个例子特别简单，因为累加器和列表元素具有相同类型。但 fold 并不限于这种情况。例如，我们可以用 fold 反转一个列表，此时累加器本身也是一个列表：
# List.fold ~init:[] ~f:(fun acc hd -> hd :: acc) [1;2;3;4];;
- : int list = [4; 3; 2; 1]
现在把这三个函数组合起来，计算最大列宽：
# let max_widths header rows =
let lengths l = List.map ~f:String.length l in
List.fold rows
~init:(lengths header)
~f:(fun acc row ->
List.map2_exn ~f:Int.max acc (lengths row));;
val max_widths : string list -> string list list -> int list = <fun>
通过 List.map，我们定义了函数 lengths，它把字符串列表转换成整数长度列表。随后使用 List.fold 遍历各行，并用 map2_exn 对累加器和表格每一行中字符串长度取最大值；累加器则初始化为标题行的长度。
现在已经知道如何计算列宽，可以编写生成分隔标题和表格剩余部分的那一行的代码。我们会把 String.make 映射到列长度上，生成适当长度的短横线字符串；然后用 String.concat 把这些短横线序列连接起来，并使用 ^ 这个两两字符串连接函数在外侧加上分隔符。String.concat 会用一个可选分隔符字符串连接字符串列表。
# let render_separator widths =
let pieces = List.map widths
~f:(fun w -> String.make w '-')
in
"|-" ^ String.concat ~sep:"-+-" pieces ^ "-|";;
val render_separator : int list -> string = <fun>
# render_separator [3;6;2];;
- : string = "|-----+--------+----|"
注意，我们让短横线比给定宽度多两个字符，从而为表中每个条目周围留出一些空白。
String.concat 与 ^ 的性能（Performance of String.concat and ^）
在前面的代码中，我们用两种方式连接字符串：String.concat 作用于字符串列表；^ 是一个二元运算符。你应该避免用 ^ 连接大量字符串，因为它每次运行都会分配一个新字符串。因此，下面的代码：
# let s = "." ^ "."
^ "."
^ "."
^ "."
^ "."
^ ".";;
val s : string = "......."
会分配长度为 2、3、4、5、6 和 7 的字符串；而下面这段代码：
# let s = String.concat [".";".";".";".";".";".";"."];;
val s : string = "......."
会分配一个大小为 7 的字符串，以及一个长度为 7 的列表。在这么小的规模下，差异并不大；但在组装大字符串时，这会成为严重的性能问题。
现在需要编写渲染数据行的代码。先写一个名为 pad 的函数，用于把字符串填充到指定长度：
# let pad s length =
s ^ String.make (length - String.length s) ' ';;
val pad : string -> int -> string = <fun>
# pad "hello" 10;;
- : string = "hello "
可以通过把填充后的字符串合并在一起，渲染一行数据。同样，我们会使用 List.map2_exn 把行中的数据列表和宽度列表组合起来：
# let render_row row widths =
let padded = List.map2_exn row widths ~f:pad in
"| " ^ String.concat ~sep:" | " padded ^ " |";;
val render_row : string list -> int list -> string = <fun>
# render_row ["Hello";"World"] [10;15];;
- : string = "| Hello | World |"
最后，可以把这一切组合起来，构建一开始想要的 render_table 函数：
# let render_table header rows =
let widths = max_widths header rows in
String.concat ~sep:"\n"
(render_row header widths
:: render_separator widths
:: List.map rows ~f:(fun row -> render_row row widths)
);;
val render_table : string list -> string list list -> string = <fun>
4.4.1 更多有用的列表函数（More Useful List Functions）
前面的例子只涉及 List 中的三个函数。这里不会覆盖整个接口（完整接口请查看在线文档），但还有几个函数足够有用，值得在这里提一下。
使用 List.reduce 组合列表元素（Combining List Elements with List.reduce）
前面描述过的 List.fold 是一个非常通用且强大的函数。不过有时你想要更简单、更容易使用的东西。List.reduce 就是这样的函数。它本质上是 List.fold 的一个专门版本，不需要显式起始值，并且它的累加器必须消费并产生与所应用列表元素相同类型的值。
下面是类型签名：
# List.reduce;;
- : 'a list -> f:('a -> 'a -> 'a) -> 'a option = <fun>
reduce 返回可选结果；当输入列表为空时返回 None。
现在可以看看 reduce 的运行：
# List.reduce ~f:(+) [1;2;3;4;5];;
- : int option = Some 15
# List.reduce ~f:(+) [];;
- : int option = None
使用 List.filter 和 List.filter_map 过滤（Filtering with List.filter and List.filter_map）
处理列表时，你常常希望只关注列表中值的某个子集。List.filter 函数是实现这一点的一种方式：
# List.filter ~f:(fun x -> x % 2 = 0) [1;2;3;4;5];;
- : int list = [2; 4]
有时，你希望在同一次计算中既转换又过滤。这时需要 List.filter_map。传给 List.filter_map 的函数会返回一个可选值，而 List.filter_map 会丢弃所有返回 None 的元素。
下面是一个例子。以下函数会从文件列表计算扩展名列表，并把结果通过 List.dedup_and_sort 管道化处理，返回去重并排序后的列表。注意，这个例子使用了 String 模块中的 String.rsplit2，根据给定字符最右侧的一次出现来拆分字符串：
# let extensions filenames =
List.filter_map filenames ~f:(fun fname ->
match String.rsplit2 ~on:'.' fname with
| None
| Some ("",_) -> None
| Some (_,ext) ->
Some ext)
|> List.dedup_and_sort ~compare:String.compare;;
val extensions : string list -> string list = <fun>
# extensions ["foo.c"; "foo.ml"; "bar.ml"; "bar.mli"];;
- : string list = ["c"; "ml"; "mli"]
前面的代码也是或模式（or-pattern）的例子，它允许你在更大的模式中包含多个子模式。在这里，None | Some ("",_) 就是一个或模式。稍后会看到，或模式可以嵌套在更大模式中的任意位置。
使用 List.partition_tf 分区（Partitioning with List.partition_tf）
另一个与过滤密切相关的有用操作是分区。函数 List.partition_tf 接收一个列表，以及一个用于在列表元素上计算布尔条件的函数，并返回两个列表。名字中的 tf 是一个助记，用来提醒使用者：true 元素进入第一个列表，false 元素进入第二个列表。下面是一个例子：
# let is_ocaml_source s =
match String.rsplit2 s ~on:'.' with
| Some (_,("ml"|"mli")) -> true
| _ -> false;;
val is_ocaml_source : string -> bool = <fun>
# let (ml_files,other_files) =
List.partition_tf ["foo.c"; "foo.ml"; "bar.ml"; "bar.mli"]
~f:is_ocaml_source;;
val ml_files : string list = ["foo.ml"; "bar.ml"; "bar.mli"]
val other_files : string list = ["foo.c"]
组合列表（Combining lists）
列表上的另一个非常常见操作是连接。List 模块实际上提供了几种不同方式来做这件事。首先是 List.append，用于连接一对列表。
# List.append [1;2;3] [4;5;6];;
- : int list = [1; 2; 3; 4; 5; 6]
还有 @，它是等价于 List.append 的运算符版本。
# [1;2;3] @ [4;5;6];;
- : int list = [1; 2; 3; 4; 5; 6]
另外还有 List.concat，用于连接列表的列表：
# List.concat [[1;2];[3;4;5];[6];[]];;
- : int list = [1; 2; 3; 4; 5; 6]
下面是把 List.concat 与 List.map 一起使用，递归列出目录树的例子。
# module Sys = Core.Sys
module Filename = Core.Filename;;
module Sys = Core.Sys
module Filename = Core.Filename
# let rec ls_rec s =
if Sys.is_file_exn ~follow_symlinks:true s
then [s]
else
Sys.ls_dir s
|> List.map ~f:(fun sub -> ls_rec (Filename.concat s sub))
|> List.concat;;
val ls_rec : string -> string list = <fun>
注意，这个例子使用了 Core 中的 Sys 和 Filename 模块的一些函数，用于访问文件系统和处理文件名。
前面 List.map 与 List.concat 的组合非常常见，因此存在一个函数 List.concat_map，把二者组合成一个更高效的操作：
# let rec ls_rec s =
if Sys.is_file_exn ~follow_symlinks:true s
then [s]
else
Sys.ls_dir s
|> List.concat_map ~f:(fun sub -> ls_rec (Filename.concat s sub));;
val ls_rec : string -> string list = <fun>
4.5 尾递归（Tail Recursion）
计算 OCaml 列表长度的唯一方式，是从头到尾遍历列表。因此，计算列表长度所需时间与列表大小成线性关系。下面是一个简单实现：
# let rec length = function
| [] -> 0
| _ :: tl -> 1 + length tl;;
val length : 'a list -> int = <fun>
# length [1;2;3];;
- : int = 3
这看起来足够简单，但你会发现这个实现在非常大的列表上会遇到问题，如下面代码所示：
# let make_list n = List.init n ~f:(fun x -> x);;
val make_list : int -> int list = <fun>
# length (make_list 10);;
- : int = 10
# length (make_list 10_000_000);;
Stack overflow during evaluation (looping recursion?).
前面的例子使用 List.init 创建列表。List.init 接收一个整数 n 和一个函数 f，并创建长度为 n 的列表，其中每个元素的数据都通过在该元素索引上调用 f 生成。
为了理解上面例子中的错误来自哪里，需要多了解一点函数调用是如何工作的。通常，函数调用需要一些空间来跟踪与该调用相关的信息，例如传给函数的参数，或函数调用完成后需要从哪里继续执行代码。为了允许嵌套函数调用，这些信息通常会组织在一个栈中：每次嵌套函数调用都会分配新的栈帧，函数调用完成时再释放它。
这正是我们调用 length 时的问题：它试图分配一千万个栈帧，从而耗尽了可用栈空间。幸运的是，有办法绕过这个问题。考虑下面这个替代实现：
# let rec length_plus_n l n =
match l with
| [] -> n
| _ :: tl -> length_plus_n tl (n + 1);;
val length_plus_n : 'a list -> int -> int = <fun>
# let length l = length_plus_n l 0;;
val length : 'a list -> int = <fun>
# length [1;2;3;4];;
- : int = 4
这个实现依赖辅助函数 length_plus_n，它会计算给定列表的长度再加上给定的 n。实践中，n 作为累加器，答案在其中一步步构建出来。因此，我们可以一路完成加法，而不是像第一个 length 实现那样，在嵌套函数调用序列展开返回时再做加法。
这种做法的优势在于，length_plus_n 中的递归调用是尾调用。稍后我们会更精确地解释尾调用是什么意思；它重要的原因在于，借助所谓的尾调用优化（tail-call optimization），尾调用不需要分配新的栈帧。如果某个递归函数的所有递归调用都是尾调用，就称它是尾递归的。length_plus_n 确实是尾递归的，因此 length 可以接收很长的列表作为输入，而不会爆栈：
# length (make_list 10_000_000);;
- : int = 10000000
那么，什么时候一个调用是尾调用呢？想象一个函数（调用者）调用另一个函数（被调用者）的情况。如果调用者除了返回被调用者返回的值之外，不再对这个值做任何事情，那么这个调用就被认为是尾调用。尾调用优化是合理的，因为当调用者发出尾调用时，调用者的栈帧再也不需要被使用，所以不需要保留它。因此，编译器可以不为被调用者分配新的栈帧，而是复用调用者的栈帧。
尾递归的重要性并不只限于列表。处理二叉树这样的数据结构时，普通的非尾递归调用通常是合理的，因为树的深度与数据规模呈对数关系。但当嵌套调用序列的深度与数据规模同阶时，尾递归通常是正确做法。
4.6 更简洁、更快速的模式（Terser and Faster Patterns）
现在我们更了解列表和模式的工作方式了，可以回头看看如何改进第 2.3.2 节“递归列表函数（Recursive List Functions）”中的一个例子：函数 remove_sequential_duplicates。下面是之前描述的实现：
# let rec remove_sequential_duplicates list =
match list with
| [] -> []
| [x] -> [x]
| first :: second :: tl ->
if first = second then
remove_sequential_duplicates (second :: tl)
else
first :: remove_sequential_duplicates (second :: tl);;
val remove_sequential_duplicates : int list -> int list = <fun>
我们会考虑几种让这段代码更简洁、更高效的方式。
先考虑效率。上面代码的一个问题是，在某些情况下，它会在箭头右侧重新创建一个已经存在于箭头左侧的值。因此，模式 [hd] -> [hd] 实际上会分配一个新的列表元素；但真正应该做的只是返回被匹配的那个列表。这里可以使用 as 模式减少分配。as 模式允许我们为某个模式或子模式匹配到的东西声明一个名字。顺便，我们还会使用 function 关键字，消除显式 match 的需要：
# let rec remove_sequential_duplicates = function
| [] as l -> l
| [_] as l -> l
| first :: (second :: _ as tl) ->
if first = second then
remove_sequential_duplicates tl
else
first :: remove_sequential_duplicates tl;;
val remove_sequential_duplicates : int list -> int list = <fun>
还可以使用或模式把前两个情况合并成一个，从而进一步压缩：
# let rec remove_sequential_duplicates list =
match list with
| [] | [_] as l -> l
| first :: (second :: _ as tl) ->
if first = second then
remove_sequential_duplicates tl
else
first :: remove_sequential_duplicates tl;;
val remove_sequential_duplicates : int list -> int list = <fun>
现在可以使用 when 子句，让代码稍微更简洁。when 子句允许我们以任意 OCaml 表达式的形式，为模式添加额外前置条件。在这个例子中，可以用它包含对前两个元素是否相等的检查：
# let rec remove_sequential_duplicates list =
match list with
| [] | [_] as l -> l
| first :: (second :: _ as tl) when first = second ->
remove_sequential_duplicates tl
| first :: tl -> first :: remove_sequential_duplicates tl;;
val remove_sequential_duplicates : int list -> int list = <fun>
多态比较（Polymorphic Compare）
你可能已经注意到，remove_sequential_duplicates 被专门化到了整数列表。这是因为 Base 默认的相等性运算符专门用于整数；如果尝试把它应用到不同类型的值上，就能看到这一点：
# open Base;;
# "foo" = "bar";;
Line 1, characters 1-6:
Error: This expression has type string but an expression was expected
of type
int
OCaml 还有一组多态相等和比较运算符，可以通过打开 Base.Poly 模块让它们可用。
# open Base.Poly;;
# "foo" = "bar";;
- : bool = false
# 3 = 4;;
- : bool = false
# [1;2;3] = [1;2;3];;
- : bool = true
事实上，如果查看相等运算符的类型，会看到它是多态的。
# (=);;
- : 'a -> 'a -> bool = <fun>
如果在打开 Base.Poly 的情况下改写 remove_sequential_duplicates，就会看到它得到一个多态类型，现在可以用于不同类型的输入。
# let rec remove_sequential_duplicates list =
match list with
| [] | [_] as l -> l
| first :: (second :: _ as tl) when first = second ->
remove_sequential_duplicates tl
| first :: tl -> first :: remove_sequential_duplicates tl;;
val remove_sequential_duplicates : 'a list -> 'a list = <fun>
# remove_sequential_duplicates [1;2;2;3;4;3;3];;
- : int list = [1; 2; 3; 4; 3]
# remove_sequential_duplicates ["one";"two";"two";"two";"three"];;
- : string list = ["one"; "two"; "three"]
OCaml 附带一整族多态比较运算符，包括标准中缀比较器 <、>= 等，以及函数 compare。compare 会返回 -1、0 或 1，分别表示第一个操作数小于、等于或大于第二个操作数。
你也许会好奇：如果 OCaml 没有内置这些函数，是否能自己构建它们？事实证明，你不能自己构建这些函数。OCaml 的多态比较函数以内建形式存在于运行时的较低层。它们之所以具有多态性，是因为它们几乎忽略被比较值的类型信息，只关注这些值在内存中的结构布局。（你可以在第 24 章“值的内存表示（Memory Representation of Values）”中进一步学习这种结构。）
多态比较确实有一些限制。例如，如果它遇到函数值，会在运行时失败。
# (fun x -> x + 1) = (fun x -> x + 1);;
Exception: (Invalid_argument "compare: functional value")
类似地，它也会在来自 OCaml 堆之外的值上失败，例如来自 C 绑定的值。但对大多数其他种类的值来说，它会以合理方式工作。对于简单原子类型，多态比较具有你会期待的语义：对浮点数和整数来说，多态比较对应于预期的数值比较函数；对字符串来说，它是字典序比较。
尽管如此，有经验的 OCaml 开发者通常会避免多态比较。考虑到它明显有用，这可能令人意外，但背后有充分理由。虽然它很方便，但在某些情况下，多态比较对类型无感这一性质意味着它会做出不适合你正在处理的特定值类型的事情。这可能在代码中导致令人惊讶且难以解决的 bug。正因为如此，Base 默认隐藏多态比较，从而不鼓励使用它。
第 15 章“映射与哈希表（Maps and Hash Tables）”会更详细地讨论多态比较的缺点。
注意，when 子句也有一些缺点。前面提到过，与模式匹配相关的静态检查依赖这样一个事实：模式能够表达的内容是受限制的。一旦我们加入为模式添加任意条件的能力，就会失去一些东西。具体来说，编译器判断某个匹配是否穷尽，或者某个情况是否冗余的能力，会受到影响。
考虑下面这个函数。它接收一个可选值列表，并返回其中 Some 值的数量。由于这个实现使用了 when 子句，编译器无法看出代码是穷尽的：
# let rec count_some list =
match list with
| [] -> 0
| x :: tl when Option.is_none x -> count_some tl
| x :: tl when Option.is_some x -> 1 + count_some tl;;
Lines 2-5, characters 5-57:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
_::_
(However, some guarded clause may match this value.)
val count_some : 'a option list -> int = <fun>
尽管有警告，这个函数确实可以正常工作：
# count_some [Some 3; None; Some 4];;
- : int = 2
如果再添加一个没有 when 子句的冗余情况，编译器就会停止抱怨穷尽性，并且也不会针对冗余产生警告。
# let rec count_some list =
match list with
| [] -> 0
| x :: tl when Option.is_none x -> count_some tl
| x :: tl when Option.is_some x -> 1 + count_some tl
| x :: tl -> -1 (* unreachable *);;
val count_some : 'a option list -> int = <fun>
更好的做法也许是简单地删除第二个 when 子句：
# let rec count_some list =
match list with
| [] -> 0
| x :: tl when Option.is_none x -> count_some tl
| _ :: tl -> 1 + count_some tl;;
val count_some : 'a option list -> int = <fun>
不过，这比直接的模式匹配方案稍微不那么清晰；在直接方案中，每个模式本身的含义更清楚：
# let rec count_some list =
match list with
| [] -> 0
| None :: tl -> count_some tl
| Some _ :: tl -> 1 + count_some tl;;
val count_some : 'a option list -> int = <fun>
所有这些的要点是：尽管 when 子句可能很有用，但只要模式本身足够，就应该优先使用模式。
顺带一提，上面 count_some 的实现比必要的更长；更糟的是，它不是尾递归的。现实中，你可能只会使用 List.count 函数：
# let count_some l = List.count ~f:Option.is_some l;;
val count_some : 'a option list -> int = <fun>