列表高阶函数详解

### 列表高阶函数详解 #### 1. 累积变量 在递归过程中，有时需要在不同阶段传递中间信息。以查找整数列表中的最大值为例，我们需要记录到目前为止的最大值。 - 若列表为空，最大值就是到目前为止记录的最大值。 - 若列表头部元素大于当前记录的最大值，更新最大值为头部元素，继续在列表尾部查找。 - 若头部元素不大于当前最大值，保持最大值不变，继续在尾部查找。 以下是实现代码： ``` – (* find biggest in integer list given biggest so far *) fun max1 (bsf:int) [ ] = bsf | max1 bsf (h::t) = if h>bsf then max1 h t else max1 bsf t; > val max1 = fn : int -> int list -> int ``` 假设列表至少有一个元素，可将第一个元素作为初始最大值： ``` – exception Max; > exception Max – (* find biggest in integer list *) fun max (h::t) = max1 h t | max [ ] = raise Max; > val max = fn : int list -> int ``` 若对空列表调用 `max` 函数，会抛出异常，因为空列表没有最大值。例如： ``` – max [1, 3, 2, 4, 7, 5, 6]; > 7 : int ``` 执行过程如下： ``` max [1, 3, 2, 4, 7, 5, 6] ==> max1 [3, 2, 4, 7, 5, 6] ==> max1 3 [2, 4, 7, 5, 6] ==> max1 3 [4, 7, 5, 6] ==> max1 4 [7, 5, 6] ==> max1 7 [5, 6] ==> max1 7 [6] ==> max1 7 [ ] ==> 7 ``` 这里的 `bsf` 是累积变量，它累积了到目前为止的最大值信息。 #### 2. 局部声明封装 编程中的一个重要原则是封装。解决问题时，应只让关键信息被广泛访问。对于整体解决方案中但不独立使用的部分，应仅让使用它的部分访问。在多人合作构建大型系统时，这一点尤为重要，每个人只需了解其他组件的整体行为，而无需关心具体实现细节。 在当前问题中，最终函数常调用一个或多个辅助函数，这些辅助函数可分组，使其仅在调用函数内部可访问。例如，`max` 函数中仅在内部使用 `max1` 函数，可通过局部声明限制 `max1` 的访问范围。 局部声明的形式为： ``` local dedaration1 in declaration2 end ``` 这表示 `dedaration1` 仅在 `dedaration2` 内部可见。示例如下： ``` – local fun max1 (bsf:int) [ ] = bsf | max1 bsf (h::t) = if h>bsf then max1 h t else max1 bsf t in fun max (h::t) = max1 b t | max [ ] = raise Max end; > val max = fn : int list -> int ``` 此时只有 `max` 函数能访问 `max1` 函数。注意，局部声明结尾的 `end` 不能遗漏。 #### 3. 升序序列 考虑构建一个升序排列的平方数列表，即 `[sq 1, sq 2, …sq n]`。若要生成 `m` 到 `n` 之间的平方数列表： - 若 `m` 大于 `n`，返回空列表。 - 否则，将 `m` 的平方添加到 `m + 1` 到 `n` 的平方数列表中。 代码如下： ``` – (* list squares from m to n *) fun sqlist1 m n = if m>n then [ ] else sq m::sqlist1 (m+1) n; > val sqlist1 = fn : int -> int -> int list ``` 从 1 开始生成列表： ``` – (* list squares from 1 to n *) val sqlist=sqlist1 1; > val sqlist = fn : int -> int list ``` 这里使用条件表达式控制值的生成，模式匹配可检测特定值，但无法检测满足任意条件的值。也可将 `sqlist1` 的声明隐藏在 `sqlist` 内部： ``` – local fun sqlist1 m n = if m>n then [ ] else sq m::sqlist1 (m+1) n in val sqlist = sqlist1 1 end; > val sqlist = fn : int -> int list ``` 例如： ``` – sqlist 4; > [1, 4, 9, 16] : int list ``` 执行过程如下： ``` sqlist 4 ==> sqlist1 1 4 ==> sq 1::sqlist1 2 4 ==> sq 1::sq 2::sqlist1 3 4 ==> sq 1::sq 2::sq 3::sqlist1 4 4 ==> sq 1::sq 2::sq 3::sq 4::sqlist1 54 ==> sq 1::sq 2::sq 3::sq4::[ ] ==> [1, 4, 9, 16] ``` 这里的 `m` 累积了下一个要生成范围的起始点。 #### 4. 列表反转 反转列表时，需记录到目前为止反转后的列表。 - 若列表为空，返回记录的反转列表。 - 若列表不为空，将头部元素添加到记录的反转列表前面，继续反转尾部列表。 代码如下： ``` – (* reverse second list onto first list *) fun rev1 rlsf [ ] = rlsf | rev1 rlsf (h::t) = rev1 (h::rlsf) t; > val rev1 = fn : ′a list -> ′a list -> ′a list ``` 将初始反转列表设为空列表： ``` – (* reverse list *) val rev = rev1 [ ] ; > val rev = fn : ′a list -> ′a list ``` 同样可将 `rev1` 隐藏在 `reverse` 内部： ``` – local fun rev1 rlsf [ ] = rlsf | rev1 rlsf (h::t) = rev1 (h::rlsf) t in val rev = rev1 [ ] end; > val rev = fn : ′a list -> ′a list ``` 例如： ``` – rev ["a", "b", "c", "d"]; > ["d", "c", "b", "a"] : string list ``` 执行过程如下： ``` rev ["a", "b", "c", "d"] ==> rev1 [ ] ["a", "b", "c", "d"] ==> rev1 "a"::[ ] ["b", "c", "d"] ==> rev1 "b"::"a"::[ ] ["c", "d"] ==> rev1 "c"::"b"::"a"::[ ] ["d"] ==> rev1"d"::"c"::"b"::"a"::[ ] [ ] ==> "d"::"c"::"b"::"a":: [ ] ==> ["d", "c", "b", "a"] ``` 这里的 `rlsf` 累积了正在构建的反转列表，`rev` 是 SML 预定义函数。 #### 5. 列表映射 与处理数字类似，常见的列表处理函数可通过高阶函数进行泛化。以整数列表元素平方和字符串列表元素添加 “s” 为例。 整数列表元素平方： ``` – (* square each in integer list *) fun sqs [ ] = [ ] | sqs (h::t) = sq h::sqs t; > val sqs = fn : int list -> int list ``` 字符串列表元素添加 “s”： ``` – (* end string with "s" *) fun plural s = s^"s"; > val plural = fn : string -> string – (* end each in string list with "s" *) fun plurals [ ] = [ ] | plurals (h::t) = plural h::plurals t; > val plurals = fn : string list -> string list ``` `sqs` 和 `plurals` 结构相似，只是对头部元素的操作不同。可将操作替换为任意函数进行泛化： ``` – (* apply function to each in list *) fun map _[ ] =[ ] | map f (h::t) = f h::map f t; > val map = fn : (′a -> ′b) -> ′a list -> ′b list ``` `map` 函数将函数 `f` 应用于列表的每个元素，生成新列表。例如： ``` – val sqs=map sq; > val sqs=fn:int list -> int list – sqs [4, 5, 6]; > [16, 25, 36] : int list ``` ``` – val plurals = map plural; > val plurals = fn : string list -> string list – plurals ["dog", "emu", "frog"]; > ["dogs", "emus", "frogs"] : string list ``` 还可将二进制数字转换为字符串： ``` – (* convert binary digit to string *) fun conv 0 = "zero" | conv 1 = "one" | conv _ = "not binary"; > val conv = fn : int -> string – (* convert binary digit list to string list *) val convs = map conv; > val convs = fn : int list -> string list – convs [1, 0,1] ; > ["one", "zero", "one"] : string list ``` `map` 是 SML 预定义函数。 #### 6. 列表过滤 `map` 函数将函数应用于列表的所有元素，而列表过滤是提取列表中满足特定属性的元素。 判断单词是否为冠词或代词： ``` – (* is word an article or pronoun? *) fun isap "a"=true | isap "an"=true | isap "the"=true | isap "his"=true | isap "her"=true | isap "their"=true | isap "our"=true | isap "my"=true | isap _=false; > val isap = fn : string -> bool ``` 提取列表中的冠词和代词： ``` – (* find all articles or pronouns in list *) fun getaps [ ] = [ ] | getaps (h::t) = if isap h then h::getaps t else getaps t; > val getaps = fn : string list -> string list ``` 判断数字是否为偶数： ``` – (* is integer even? *) fun even x = x mod 2=0; ```