编程语言导论/显著高阶函数
一些高阶函数是非常常见的编程习惯用法。三个最著名的例子是map，reduce和filter。本章中的第一个示例是 map 函数的实现。它接受两个参数，一个数据结构 *t* 和一个映射函数 *f*，并返回一个新的数据结构，其中每个元素都经过 *f* 转换。通常 map 在列表上工作。Map 不会向输入列表添加或删除元素；因此，输入和输出列表始终具有相同的尺寸。
Reduce 用于将数据结构转换为单个值，方法是连续应用二元运算符。在 SML 中，reduce 有两种形式：foldr 和 foldl。第一个函数 foldr 接受一个类型为 'a * 'b -> 'b 的二元函数、一个类型为 'b 的种子以及一个类型为 'a list 的列表，并返回一个称为 *归约* 的类型为 'b 的元素。函数 foldr 从列表的右侧开始向左侧应用二元运算符。下面给出一些示例
- foldr (op +) 0 [1,2,3,4];
val it = 10 : int
- foldr (op * ) 1 [1,2,3,4];
val it = 24 : int
- foldr (op ^) "" ["abc","def","ghi"];
val it = "abcdefghi" : string
- foldr (op ::) [5] [1,2,3,4];
val it = [1,2,3,4,5] : int list
- foldr (fn(a, b) => (a + b)/2.0) 0.0 [1.0, 2.0, 3.0, 4.0];
val it = 1.625 : real
函数 foldl 与 foldr 非常相似；但是，它从列表的左侧开始向右侧评估二元运算。下面给出了一些使用示例
- foldl (op +) 0 [1,2,3,4];
val it = 10 : int
- foldl (op * ) 1 [1,2,3,4];
val it = 24 : int
- foldl (op ^) "" ["abc", "def", "ghi"];
val it = "ghidefabc" : string
- foldl (op ::) [5] [1,2,3,4];
val it = [4,3,2,1,5] : int list
- foldl (fn(a, b) => (a + b)/2.0) 0.0 [1.0, 2.0, 3.0, 4.0];
val it = 3.0625 : real
有时，当给定相同的操作数时，foldl 和 foldr 会产生相同的结果。此结果取决于这些操作使用的二元运算符。如果运算符既是关联的又是可交换的，那么这些函数将对相同的输入产生相同的结果。否则，它们的结果可能不同。
这三个函数 map、foldr 和 foldl 是非常有用的并行骨架。例如，map 可以完全并行化，前提是处理器数量与输入列表的大小成正比，就像在PRAM 模型中一样。换句话说，在这个场景中，此函数将在 *O(f)*渐近 时间内执行，其中 *O(f)* 是应用映射函数的复杂度。如果处理器数量非常多，即与输入列表的大小成正比，那么 foldr 和 foldl 的复杂度都可以降低到输入列表大小的对数因子。这一观察结果促使了几个高性能框架的设计，例如map reduce 和radoop。
我们的最后一个高阶函数是 filter。此函数具有类型 ('a -> bool) -> 'a list -> 'a list。此函数接受两个参数：一个谓词，即一个对给定输入返回真或假的函数，以及一个列表。Filter 返回一个新列表，该列表仅包含导致谓词为真的那些元素。下面可以查看 SML 中的一些示例
- List.filter (fn s => hd (explode s) = #"p") ["grape", "pineaple", "pumpkin", "strawberry"];
val it = ["pineaple","pumpkin"] : string list
- List.filter (fn x => x > 2) [1,2,3,4,5];
val it = [3,4,5] : int list