map 函数

map 函数是函数式编程范式中最受欢迎的抽象之一。它最广为人知的作用是将列表中的元素映射为新元素。由于其强大实用性，map 已被引入大多数主流编程语言，如 JavaScript、Java 和 Python。

列表上的 map 函数

将 map 作用于列表的一种理解方式是：它代表了一种对列表进行通用计算的方法。
首先，我们编写一个 square_list 函数，用于将列表中所有元素平方，以观察其中的模式。

1(** [print_int_list] 将整数列表 [l] 打印到控制台。 *)
2let print_int_list l = print_string ("[" ^ (String.concat "; " (List.map string_of_int l)) ^ "]")
3
4(** [square_list] 返回一个新列表，其元素为输入列表 [l] 中各元素的平方。 *)
5let rec square_list l = match l with
6                        | [] -> []
7                        | hd :: tl -> (hd * hd) :: square_list tl
8
9(** 将 'square_list [1; 2; 3]' 的结果打印到控制台。 *)
10let _ = print_int_list (square_list [1; 2; 3])

接下来，我们编写另一个名为 cube_list 的函数，将列表元素变为它们的立方。

1(** [print_int_list] 将整数列表 [l] 打印到控制台。 *)
2let print_int_list l = print_string ("[" ^ (String.concat "; " (List.map string_of_int l)) ^ "]")
3
4(** [cube_list] 返回一个新列表，其元素为输入列表 [l] 中各元素的立方。 *)
5let rec cube_list l = match l with
6                      | [] -> []
7                      | hd :: tl -> (hd * hd * hd) :: cube_list tl
8
9(** 将 'cube_list [1; 2; 3]' 的结果打印到控制台。 *)
10let _ = print_int_list (cube_list [1; 2; 3])

square_list 和 cube_list 的实现非常相似。两者之间的区别仅在于最后一条语句：hd * hd 与 hd * hd * hd。除此之外，函数的整体结构完全一致。

正如我们在课程中多次看到的那样，这种共性几乎总是提升抽象层次的机会。我们可以将这一共同模式提取出来，形成一个高阶的 map 函数，它接收一个函数 f 和一个列表作为输入。该函数将 f 统一应用于列表的所有元素，并生成包含结果的新列表。这样，square_list 与 cube_list 就都成为 map 的具体应用实例。

1(** [print_int_list] 将整数列表 [l] 打印到控制台。 *)
2let print_int_list l = print_string ("[" ^ (String.concat "; " (List.map string_of_int l)) ^ "]")
3
4(** [map f l] 将函数 [f] 应用于列表 [l] 的每个元素。 *)
5let rec map f l = match l with
6                  | [] -> []
7                  | hd :: tl -> (f hd) :: map f tl
8
9(** [square_list] 是一个将列表元素平方的函数。 *)
10let square_list = map (fun x -> x * x)
11
12(** [cube_list] 是一个将列表元素变为立方的函数。 *)
13let cube_list = map (fun x -> x * x * x)
14
15(** 将 'square_list [1; 2; 3]' 和 'cube_list [1; 2; 3]' 的结果分别打印到控制台，中间换行。 *)
16let _ = print_int_list (square_list [1; 2; 3]);
17        print_newline ();
18        print_int_list (cube_list [1; 2; 3])

下图展示了这一抽象过程：

map 能够成为如此强大的抽象，是因为它让我们可以将数据序列的变换视为一个高层次的概念。使用 map 时，我们关注的是“做什么变换”，而不是“每一步如何执行”。

另一种理解 map f l 的方式是：将其看作将列表 l 中的每个元素 e 替换为 f e，如下图所示：

OCaml 的 List 模块提供了 map: ('a -> 'b) -> 'a list -> 'b list，这正是我们描述的行为。

1(** [print_int_list] 将整数列表 [l] 打印到控制台。 *)
2let print_int_list l = print_string ("[" ^ (String.concat "; " (List.map string_of_int l)) ^ "]")
3
4(** 将 'List.map (fun x -> x * x) [1; 2; 3]' 的结果打印到控制台。 *)
5let _ = print_int_list (List.map (fun x -> x * x) [1; 2; 3])

树上的 map 函数

map 的概念可以推广到分层数据结构，尤其是当这些结构包含相同类型的元素时。例如，我们定义一个二叉树的 map 函数，其代数数据类型如下：

1type 'a bin_tree = Leaf | Node of 'a bin_tree * 'a * 'a bin_tree

二叉树要么是一个没有字段的 Leaf，要么是一个包含左子树、数据和右子树的 Node。
下图展示了一个二叉树的例子：

图中所示的二叉树在 OCaml 中表示为：

1Node (Node (Leaf, 2, Leaf), 1, Node (Node (Leaf, 4, Leaf), 3, Leaf))

我们可以定义一个 map_tree 函数，它接收一个函数 f 和一棵二叉树 t，并统一将 f 应用于树中每个节点的数据。

1let rec map_tree f t = match t with 
2                       | Leaf -> Leaf
3                       | Node (l, v, r) -> Node (map_tree f l, f v, map_tree f r)

与列表上的 map 类似，我们可以将 map_tree f t 理解为将每个节点的数据 e 替换为 f e。

我们使用 map_tree 将树中所有元素平方，传入平方函数 (fun x -> x * x)。同样，也可以用立方函数 fun x -> x * x * x 将所有节点元素变为立方。

1(** [bin_tree] 数据类型定义二叉树。 *)
2type 'a bin_tree =
3 | Leaf
4 | Node of 'a bin_tree * 'a * 'a bin_tree
5
6(** [print_bin_tree t] 将二叉树打印到控制台。 *)
7let print_bin_tree t = 
8   let rec bin_tree_to_string t = match t with
9                                  | Leaf -> "Leaf"
10                                  | Node (l, x, r) -> "Node (" ^ (bin_tree_to_string l) ^ ", " ^ (string_of_int x) ^ ", " ^ (bin_tree_to_string r) ^ ")"
11   in print_string (bin_tree_to_string t)
12
13(** [map_tree f t] 将函数 [f] 应用于树 [t] 的每个节点。 *)
14let rec map_tree f t = match t with
15                       | Leaf -> Leaf
16                       | Node (l, x, r) -> Node (map_tree f l, f x, map_tree f r)
17
18(** 将 'map_tree (fun x -> x * x) (Node (Node (Leaf, 2, Leaf), 1, Node (Node (Leaf, 4, Leaf), 3, Leaf)))' 和 'map_tree (fun x -> x * x * x) (Node (Node (Leaf, 2, Leaf), 1, Node (Node (Leaf, 4, Leaf), 3, Leaf)))' 的结果分别打印到控制台，中间换行。 *)
19let _ = print_bin_tree (map_tree (fun x -> x * x) (Node (Node (Leaf, 2, Leaf), 1, Node (Node (Leaf, 4, Leaf), 3, Leaf))));
20        print_newline ();
21        print_bin_tree (map_tree (fun x -> x * x * x) (Node (Node (Leaf, 2, Leaf), 1, Node (Node (Leaf, 4, Leaf), 3, Leaf))));

容器上的 map 函数

列表和二叉树都是容器——包含元素的数据结构。事实上，我们通常可以为某种容器类型定义有意义的 map 函数。例如，OCaml 的 option 类型就是一个容器类型。

1type 'a option = None | Some of 'a

option 容器要么为空（None），要么包含一个值 x（Some x）。

我们可以为 option 类型定义一个 map 函数。

1(** [print_option o] 将 option [o] 打印到控制台。 *)
2let print_option o = 
3   let option_to_string o = match o with 
4                            | None -> "None"
5                            | Some x -> "Some " ^ (string_of_int x)
6   in print_string (option_to_string o)
7                                      
8(** [map_option o] 将函数 [f] 应用于 option [o] 中包含的值。 *)
9let map_option f o = match o with
10                     | None -> None
11                     | Some x -> Some (f x)
12
13(** 将 'map_option (fun x -> x * x) None' 与 'map_option (fun x -> x * x) (Some 3)' 的结果分别打印到控制台，中间换行。 *)
14let _ = print_option (map_option (fun x -> x * x) None);
15        print_newline ();
16        print_option (map_option (fun x -> x * x) (Some 3));

OCaml 的 Option 模块提供了 map 函数，其行为与上述 map_option 完全一致。在代码沙箱中将 map_option 替换为 Option.map 即可看到效果。

我们可以将 map_option f o 理解为：将 Some 内部的数据 x 替换为 f x，而对 None 不做任何操作，如下图所示：

能够对 option 进行 map 操作在错误处理中非常有用。例如，我们可以用它来实现以下 longest_string: string list -> string option 函数，该函数用于查找列表中最长的字符串。

1let rec longest_string l =
2          match l with
3          | [] -> None
4          | hd :: tl -> let s = longest_string tl in
5                           match s with
6                           | None -> Some hd
7                           | Some x -> if String.length hd > String.length x then Some hd else Some x

该函数返回 option 类型，因为空列表不存在最长字符串。

如果我们想写一个 max_length 函数，返回列表中最长字符串的长度，可以将 longest_string 与 Option.map 组合使用。

这在 OCaml 中可以表示为：

1(** [print_option o] 将 option [o] 打印到控制台。 *)
2let print_option o = 
3   let option_to_string o = match o with 
4                            | None -> "None"
5                            | Some x -> "Some " ^ (string_of_int x)
6   in print_string (option_to_string o)
7
8(** [longest_string l] 返回 [Some x]，其中 [x] 是列表 [l] 中最长的字符串；
9或当列表为空时返回 [None]。 *)
10let rec longest_string l =
11          match l with
12          | [] -> None
13          | hd :: tl -> let s = longest_string tl in
14                           match s with
15                           | None -> Some hd
16                           | Some x -> if String.length hd > String.length x then Some hd else Some x
17
18(** [max_length l] 返回 [Some n]，其中 [n] 是列表 [l] 中最长字符串的长度；
19或当列表为空时返回 [None]。 *)
20let max_length l = Option.map String.length (longest_string l)
21                                      
22(** 将 'max_length []' 与 'max_length ["a"; "abc"; "ab"]' 的结果分别打印到控制台，中间换行。 *)
23let _ = print_option (max_length []);
24        print_newline ();
25        print_option (max_length ["a"; "abc"; "ab"]);

得益于 Option.map 的设计，我们可以同时处理两种情况：如果存在最长字符串，则将其映射为长度；否则返回空结果。

接下来，我们看看 map 如何对列表、树和 option 进行数据转换。

上图清楚地表明：map 对容器中的每个元素应用函数，但不会改变容器的结构。这是 map 抽象必须满足的关键特性之一。当我们为其他容器类型定义 map 时，必须牢记这一点。

域或上下文上的 map 函数

map 是一种高度通用且可复用的概念，不仅适用于列表、树、option 等常规容器，还可以推广到不同域或上下文之间的映射。这一点从 map 的类型签名中尤为明显。

不同容器上的 `map` 类型签名

这三个类型签名共享一个深层的共同模式。因此，我们可以进一步抽象，将 map 一般化为： ('a -> 'b) -> 'a context -> 'b context，其中 context 是某种类型。

下图展示了这一推广过程：

context 可以是容器类型（如列表），也可以是抽象概念，比如异步计算。假设我们定义一个 future 类型，封装一个将在未来某个时刻返回值的异步计算。此时，我们可以定义 map_future 函数，通过将函数应用于前一个 future 的值，将一个 future 映射为另一个 future。

1map_future: ('a -> 'b) -> 'a future -> 'b future

这正是 Scala 编程语言中 Future 模块中 map 函数的核心思想。特别地，Future.map 允许我们对异步计算的结果进行映射，而无需关心计算的具体执行方式。

回顾我们提到的：map 作用于容器时不会改变容器结构。类似地，map 作用于域或上下文时，也应只对值应用函数，而不改变上下文本身。例如，Future.map 可以映射 Future 实例所持有的值，但不应改变该 Future 所代表的异步计算过程。

map 作为提升函数

另一种深刻理解 map 的方式是将其视为提升函数。为了说明这一点，假设我们定义了一个 square 函数，它接收一个整数并返回其平方。要将 square 概念扩展到诸如列表、树、可选值甚至异步计算等上下文中，我们可以使用 map 将 square 提升到该领域。

例如，若将 List.map: ('a -> 'b) -> 'a list -> 'b list 部分应用到函数 square: int -> int，我们将得到一个 int list -> int list 函数，它知道如何对列表元素进行平方运算。
一般而言，map 可以被视为将 'a -> 'b 函数提升为 'a context -> 'b context 函数的能力。它能够将一个上下文映射到另一个上下文。

下图可视化了 map 作为提升函数的视角：

本课的核心要点是：map 是一种高度通用的计算方法。它使我们能够将结构的数据变换视为一个概念单元。我们无需关心每个元素的映射是如何具体实现的。