SML列表：基础、操作与模式匹配

### SML 列表：基础、操作与模式匹配 在编程中，列表是一种非常重要的数据结构，它可以用来存储一组有序的元素。本文将深入介绍 SML（Standard ML）中列表的相关知识，包括基本列表值、模式匹配、相等类型以及常用的列表操作。 #### 1. 基本列表值 SML 提供了列表类型来表示集合。列表是一个可变长度的元素序列，其中所有元素的类型相同。列表可以看作是由包含两个字段的单元组成，即头部（head）和尾部（tail）。如果头部是任意类型的值，那么尾部必须是一个元素类型与头部值相同的列表。列表总是以空列表（也称为空表）结尾，空列表可以写成 `nil` 或 `[ ]`。 列表通过中缀构造运算符 `::`（有时称为 “cons”）来构建。例如： ```sml 1 :: [ ] ``` 这是一个整数列表，头部为 1，尾部为空列表。同样地： ```sml 2 :: (1 :: [ ]) ``` 这是一个整数列表，头部为 2，尾部为 `1 :: [ ]`。 列表表示法有两种简化方式： - 如果列表的尾部是一个列表，则不需要加括号。例如： ```sml 3 :: (2 :: (1 :: [ ])) ``` 可以简化为： ```sml 3 :: 2 :: 1 :: [ ] ``` - 以空列表结尾的列表可以用方括号表示，元素之间用逗号分隔，省略末尾的空列表。例如： ```sml 1 :: 2 :: 3 :: [ ] ``` 等同于： ```sml [1, 2, 3] ``` 列表可以由任何类型的元素组成，包括元组、函数和列表。例如： ```sml [("Donald", "Duck"), ("Mickey", "Mouse"), ("Pluto", "Pup")] ``` 这是一个字符串元组列表。 列表类型是多态类型，假设 `′a` 是任意类型，那么该类型元素的列表类型为 `′a list`。`::` 的类型为： ```sml – (op ::); > fn : (′a * ′a list) -> ′a list ``` 这意味着 `::` 接受一个任意类型 `′a` 的参数和一个该类型的列表参数，并返回一个该类型的列表。 #### 2. 列表的模式匹配 列表的形式定义为： - `[ ]` 是一个列表。 - 如果 `expression1` 是 `′a` 类型，`expression2` 是 `′a list` 类型，那么 `expression1 :: expression2` 是一个 `′a list` 类型的列表。 对于列表的递归函数，我们可以使用 `[ ]` 作为基本情况，使用列表模式作为递归情况。例如，计算列表长度的函数： ```sml – (* length of list *) fun length [ ] = 0 | length (h :: t) = 1 + length t; > val length = fn : ′a list -> int ``` 这是一个多态函数，可以计算任何类型列表的长度。由于除了模式匹配外，没有对列表元素执行任何操作，所以列表的类型无关紧要。 在递归情况中，如果 `h` 未被使用，可以用通配符模式 `_` 替换： ```sml – fun length [ ] = 0 | length (_ :: t) = 1 + length t; > val length = fn : ′a list -> int ``` #### 3. 相等类型 考虑计算值 `v` 在列表中出现的次数。空列表中 `v` 出现 0 次。如果列表的头部是 `v`，则在尾部中 `v` 的计数上加 1；否则，继续在尾部中计数： ```sml – (* count value in list *) fun count v [ ] = 0 | count v (h :: t) = if v = h then 1 + count v t else count v t; > val count = fn : "a -> "a list -> int ``` 这里的类型涉及变量 `′ ′a` 而不是通常的 `′a`。因为对 `v` 和 `h` 执行的操作是使用 `=` 进行相等比较，所以 `v` 和 `h` 必须是相同类型，且该类型必须是定义了相等性的类型，即相等类型。这是对多态类型的一种轻微限制，因此变量在字母标识符前用两个撇号表示。 #### 4. 常用列表操作 ##### 4.1 添加到列表末尾 将一个值添加到列表末尾的函数： ```sml – (* put value on the end of list *) fun add v [ ] = [v] | add v (h :: t) = h :: a ```