处理数据处理应用中的集合

软件行业中存在一种根深蒂固的误解，认为函数式编程是由大学研究人员为“数学问题”而发明的。人们普遍认为函数式编程在现实世界的应用中（如外卖、网约车和电子商务）并不重要。然而，越来越多的软件工程师发现，函数式编程是一种优雅的范式，能够有效解决企业应用中的许多数据处理问题。

本课程特别关注函数式编程如何优雅地处理移动应用、Web 应用或后端服务中常见的数据集合。

map、filter 和 fold 函数几乎足以应对所有需求

尽管在处理数据集合时面临无穷无尽的问题，但大多数问题都可以归结为数据的转换、过滤和聚合。因此，我们通常通过组合 map、filter 和 fold 来完成大部分集合处理任务。

举个例子，假设我们在开发一个电商应用，需要处理商品数据。在 OCaml 中，我们可以使用记录类型来表示商品。为了简化，我们只考虑商品的名称、类型和价格。

1type product_type = ELECTRONIC | BOOK | COSMETIC
2type product = { name: string; product_type: product_type; price : float}

我们可以将一组商品存储在一个列表中。

1let products = [{name = "iPad"; product_type = ELECTRONIC ; price = 800.0}; 
2                {name = "Pride and Prejudice"; product_type = BOOK; price = 10.0}; 
3                {name = "Mac Pro"; product_type = ELECTRONIC; price = 2000.0}; 
4                {name = "Smart TV"; product_type = ELECTRONIC; price = 500.0}]

给定这样一个商品集合，我们通常需要对其进行计算。例如，可以计算所有电子产品的总价。这类问题非常适合使用 map、filter 和 fold。具体来说，我们可以构建一个数据流程序，让商品集合经过三个阶段：

• 第一阶段：使用 filter 筛选出电子商品。
• 第二阶段：使用 map 提取每个电子商品的价格。
• 第三阶段：使用 fold 累加总价格。

我们可以将这一解决方案可视化为如下数据流图：

以下 OCaml 代码实现了该数据流图：

1(** [product_type] 数据类型定义商品类型。 *)
2type product_type = ELECTRONIC | BOOK | COSMETIC
3
4(** [product] 数据类型定义商品的结构。 *)
5type product = { name: string; product_type: product_type; price : float}
6
7(** [products] 是一组示例商品。 *)
8let products = [{name = "iPad"; product_type = ELECTRONIC ; price = 800.0};
9                {name = "Pride and Prejudice"; product_type = BOOK; price = 10.0}; 
10                {name = "Mac Pro"; product_type = ELECTRONIC; price = 2000.0};
11                {name = "Smart TV"; product_type = ELECTRONIC; price = 500.0}]
12
13(** 打印商品总价到控制台。 *)
14let _ = print_float (products |> List.filter (fun product -> product.product_type = ELECTRONIC) 
15                                |> List.map (fun product -> product.price) 
16                                |> List.fold_left (+.) 0.)

虽然 map、filter 和 fold 非常强大，但它们非常通用。从实际角度看，为集合定义一些可复用的专用函数往往更有意义。这使得集合处理的解决方案更容易组合。这些专用函数通常可以通过 map、filter 和 fold 构建而成。在本课程的后续部分，我们将讨论几种常见的集合操作函数。

获取单个元素

在处理集合时，我们经常需要从中获取单个元素。例如，可能需要找到价格低于某个阈值的第一个商品。这个问题本质上是寻找满足某个谓词的第一个元素。

在 OCaml 中，一种实现方式是使用 List.filter 过滤出符合条件的元素，再用 List.hd 提取结果列表的第一个元素。

1let find p l = List.filter p l |> List.hd

注意：如果未找到匹配元素，该函数会抛出异常。

实际上，OCaml 的 List 模块已经提供了 find 函数，正好满足我们的需求。下面使用它找出价格低于 1000 的第一个商品。

1(** [product_type] 数据类型定义商品类型。 *)
2type product_type = ELECTRONIC | BOOK | COSMETIC
3
4(** [product] 数据类型定义商品的结构。 *)
5type product = { name: string; product_type: product_type; price : float}
6
7(** [print_product_record p] 将商品记录打印到控制台。 *)
8let print_product_record p =
9   let product_type_to_string t = match t with
10                                  | ELECTRONIC -> "ELECTRONIC"
11                                  | BOOK -> "BOOK"
12                                  | COSMETIC -> "COSMETIC"
13   in Printf.printf "{name = \"%s\"; product_type = %s; price = %f}" p.name (product_type_to_string p.product_type) p.price
14 
15(** [products] 是一组示例商品。 *)
16let products = [{name = "iPad"; product_type = ELECTRONIC ; price = 800.0};
17                {name = "Pride and Prejudice"; product_type = BOOK; price = 10.0}; 
18                {name = "Mac Pro"; product_type = ELECTRONIC; price = 2000.0};
19                {name = "Smart TV"; product_type = ELECTRONIC; price = 500.0}]
20
21(** [first_product] 是价格低于 1000.0 的第一个商品。 *)
22let first_product = List.find (fun product -> product.price <= 1000.0) products
23
24(** 打印 [first_product] 的结果到控制台。 *)
25let _ = print_product_record (first_product)

我们可以将 find 视为一个数据流组件。

find 函数仅适用于有序集合。对于无序集合（如集合 Set），其语义可以稍作调整，改为返回任意一个满足条件的元素。

我们还可以定义一个高阶函数 contains，用于判断列表中是否存在满足某个谓词的元素。

1(** [product_type] 数据类型定义商品类型。 *)
2type product_type = ELECTRONIC | BOOK | COSMETIC
3
4(** [product] 数据类型定义商品的结构。 *)
5type product = { name: string; product_type: product_type; price : float}
6
7(** [products] 是一组示例商品。 *)
8let products = [{name = "iPad"; product_type = ELECTRONIC ; price = 800.0};
9                {name = "Pride and Prejudice"; product_type = BOOK; price = 10.0}; 
10                {name = "Mac Pro"; product_type = ELECTRONIC; price = 2000.0};
11                {name = "Smart TV"; product_type = ELECTRONIC; price = 500.0}]
12
13(** [contains p l] 如果列表 [l] 中存在满足谓词 [p] 的元素，则返回 [true]。 *)
14let contains p l = List.filter p l <> []
15
16(** 打印 [contains (fun product -> product.price <= 1000.0) products] 的结果到控制台。 *)
17let _ = print_string (string_of_bool (contains (fun product -> product.price <= 1000.0) products))

对集合元素进行排序

对有序集合进行排序是另一个极其重要的操作。OCaml 的 List 模块提供了一个 sort 函数，它接收一个比较函数和一个列表，并返回排序后的列表。

在我们的电商应用中，当用户选择按价格从低到高显示商品时，就可以使用 sort 实现。我们可以使用 OCaml 内置的 Stdlib.compare 函数来比较两个浮点数价格。

1(** [product_type] 数据类型定义商品类型。 *)
2type product_type = ELECTRONIC | BOOK | COSMETIC
3
4(** [product] 数据类型定义商品的结构。 *)
5type product = { name: string; product_type: product_type; price : float}
6
7(** [product_record_list_to_string p] 是商品列表的字符串表示。 *)
8let product_record_list_to_string l = 
9   let product_record_to_string p =
10      let product_type_to_string t = match t with
11                                     | ELECTRONIC -> "ELECTRONIC"
12                                     | BOOK -> "BOOK"
13                                     | COSMETIC -> "COSMETIC"
14      in Printf.sprintf "{name = \"%s\"; product_type = %s; price = %f}" p.name (product_type_to_string p.product_type) p.price
15   in Printf.sprintf "[%s]" (String.concat "; " (List.map product_record_to_string l))
16 
17(** [products] 是一组示例商品。 *)
18let products = [{name = "iPad"; product_type = ELECTRONIC ; price = 800.0};
19                {name = "Pride and Prejudice"; product_type = BOOK; price = 10.0}; 
20                {name = "Mac Pro"; product_type = ELECTRONIC; price = 2000.0};
21                {name = "Smart TV"; product_type = ELECTRONIC; price = 500.0}]
22
23(** [sorted_products] 是按价格升序排列的商品列表。 *)
24let sorted_products = List.sort (fun product1 product2 -> Stdlib.compare product1.price product2.price) products
25
26(** 打印 [sorted_products] 到控制台。 *)
27let _ = print_string (product_record_list_to_string (sorted_products))

另一个有用的运算是反转集合。我们可以使用 List.fold_right 在 OCaml 中实现 reverse 函数。

1(** [product_type] 数据类型定义商品类型。 *)
2type product_type = ELECTRONIC | BOOK | COSMETIC
3
4(** [product] 数据类型定义商品的结构。 *)
5type product = { name: string; product_type: product_type; price : float}
6
7(** [product_record_list_to_string p] 是商品列表的字符串表示。 *)
8let product_record_list_to_string l = 
9   let product_record_to_string p =
10      let product_type_to_string t = match t with
11                                     | ELECTRONIC -> "ELECTRONIC"
12                                     | BOOK -> "BOOK"
13                                     | COSMETIC -> "COSMETIC"
14      in Printf.sprintf "{name = \"%s\"; product_type = %s; price = %f}" p.name (product_type_to_string p.product_type) p.price
15   in Printf.sprintf "[%s]" (String.concat "; " (List.map product_record_to_string l))
16 
17(** [products] 是一组示例商品。 *)
18let products = [{name = "iPad"; product_type = ELECTRONIC ; price = 800.0};
19                {name = "Pride and Prejudice"; product_type = BOOK; price = 10.0};
20                {name = "Mac Pro"; product_type = ELECTRONIC; price = 2000.0};
21                {name = "Smart TV"; product_type = ELECTRONIC; price = 500.0}]
22
23(** [reverse l] 反转列表 [l] *)
24let reverse l = List.fold_right (fun x acc -> acc @ [x]) l []
25
26(** 打印 [reverse products] 到控制台。 *)
27let _ = print_string (product_record_list_to_string (reverse products))

获取集合的部分内容

在处理集合时，我们可能只需要其中的一部分。例如，在电商应用中，用户可能只想查看最便宜的前两个商品。针对这种场景，我们可以定义一个方便的操作 take，用于从集合中取出前 n 个元素。

在 OCaml 中，我们可以将 take 实现为列表上的函数，如下所示：

1let rec take n l = 
2   if n <= 0 then [] else match l with
3                          | [] -> []
4                          | hd :: tl -> hd :: (take (n-1) tl)

该函数接受两个参数：整数 n 和列表 l。它返回一个新的列表，包含 l 的前 n 个元素。如果 n 大于列表长度，结果就是原列表本身。

我们可以使用这个函数来展示最便宜的两个商品，如下所示：

1(** [product_type] 数据类型定义商品类型。 *)
2type product_type = ELECTRONIC | BOOK | COSMETIC
3
4(** [product] 数据类型定义商品的结构。 *)
5type product = { name: string; product_type: product_type; price : float}
6
7(** [product_record_list_to_string p] 是商品列表的字符串表示。 *)
8let product_record_list_to_string l = 
9   let product_record_to_string p =
10      let product_type_to_string t = match t with
11                                     | ELECTRONIC -> "ELECTRONIC"
12                                     | BOOK -> "BOOK"
13                                     | COSMETIC -> "COSMETIC"
14      in Printf.sprintf "{name = \"%s\"; product_type = %s; price = %f}" p.name (product_type_to_string p.product_type) p.price
15   in Printf.sprintf "[%s]" (String.concat "; " (List.map product_record_to_string l))
16 
17(** [products] 是一组示例商品。 *)
18let products = [{name = "iPad"; product_type = ELECTRONIC ; price = 800.0};
19                {name = "Pride and Prejudice"; product_type = BOOK; price = 10.0};
20                {name = "Mac Pro"; product_type = ELECTRONIC; price = 2000.0};
21                {name = "Smart TV"; product_type = ELECTRONIC; price = 500.0}]
22
23(** [take n l] 从列表 [l] 中取出前 [n] 个元素。 *)
24let rec take n l = 
25   if n <= 0 then [] else match l with
26                          | [] -> []
27                          | hd :: tl -> hd :: (take (n-1) tl)
28
29(** [top_two_cheapest_product] 是最便宜的两个商品组成的列表。 *)
30let top_two_cheapest_product = List.sort (fun product1 product2 -> Stdlib.compare product1.price product2.price) products |> take 2
31
32(** 打印 [top_two_cheapest_product] 到控制台。 *)
33let _ = print_string (product_record_list_to_string (top_two_cheapest_product))

我们还可以定义一个更通用的高阶函数 take_while，它持续从集合中取出满足某个谓词的元素，直到遇到第一个不满足谓词的元素为止。

以下是 OCaml 中 take_while 的实现：

1let rec take_while p l = match l with
2                         | [] -> []
3                         | hd :: tl -> if p hd then hd :: (take_while p tl) else []

使用此函数，我们可以只显示价格从低到高、且价格低于 1000.0 的商品，如下所示：

1(** [product_type] 数据类型定义商品类型。 *)
2type product_type = ELECTRONIC | BOOK | COSMETIC
3
4(** [product] 数据类型定义商品的结构。 *)
5type product = { name: string; product_type: product_type; price : float}
6
7(** [product_record_list_to_string p] 是商品列表的字符串表示。 *)
8let product_record_list_to_string l = 
9   let product_record_to_string p =
10      let product_type_to_string t = match t with
11                                     | ELECTRONIC -> "ELECTRONIC"
12                                     | BOOK -> "BOOK"
13                                     | COSMETIC -> "COSMETIC"
14      in Printf.sprintf "{name = \"%s\"; product_type = %s; price = %f}" p.name (product_type_to_string p.product_type) p.price
15   in Printf.sprintf "[%s]" (String.concat "; " (List.map product_record_to_string l))
16 
17(** [products] 是一组示例商品。 *)
18let products = [{name = "iPad"; product_type = ELECTRONIC ; price = 800.0};
19                {name = "Pride and Prejudice"; product_type = BOOK; price = 10.0};
20                {name = "Mac Pro"; product_type = ELECTRONIC; price = 2000.0};
21                {name = "Smart TV"; product_type = ELECTRONIC; price = 500.0}]
22
23(** [take_while p l] 从列表 [l] 中取出满足谓词 [p] 的连续元素，直到第一个不满足的元素为止。 *)
24let rec take_while p l = match l with
25                         | [] -> []
26                         | hd :: tl -> if p hd then hd :: (take_while p tl) else []
27
28(** [product_cheaper_than_1000_in_ascending_price] 是价格低于 1000.0 且按升序排列的商品列表。 *)
29let product_cheaper_than_1000_in_ascending_price = 
30    List.sort (fun product1 product2 -> Stdlib.compare product1.price product2.price) products 
31    |> take_while (fun product -> product.price < 1000.)
32
33(** 打印 [product_cheaper_than_1000_in_ascending_price] 到控制台。 *)
34let _ = print_string (product_record_list_to_string (product_cheaper_than_1000_in_ascending_price))

针对集合的领域特定语言

本课程实质上构建了一个针对集合的领域特定语言（DSL）。具体来说，我们使用列表类型来存储集合元素，然后定义各种函数和高阶函数，以捕捉操作集合的常见模式。

下图直观展示了该集合 DSL 如何建立在 OCaml 之上：

该集合 DSL 允许我们在更高层次的抽象上思考和编程，因为我们可以将整个元素集合视为一个整体单元。无需单独命名和处理每个集合元素。此外，我们可以组合函数，利用数据流编程范式的优雅性来解决集合处理问题。这是因为在函数式编程中，集合充当了共享接口。

我们可以将本课程所介绍的技术应用于其他编程语言（如 Swift、Kotlin、JavaScript 和 Java）开发移动或 Web 应用时的数据集合处理。函数式风格使代码极具可读性，同时最大化代码复用性，因为解决方案是通过组合现有操作构建而成的。