集合

简介

Set 提供了函子 Set.Make。您需要先将一个模块传递给 Set.Make。它指定了集合的元素类型。作为回报，您将获得另一个包含这些元素的集合操作的模块。

免责声明： 本教程中的示例需要 OCaml 5.1。如果您运行的是早期版本的 OCaml，您可以使用 elements 而不是 to_list，to_list 是 OCaml 5.1 中的一个新函数，或者通过运行 opam update，然后 opam upgrade ocaml 来升级 OCaml。您可以使用 ocaml --version 检查您的当前版本。

如果您需要使用字符串集合，则必须调用 Set.Make(String)。这将返回一个新模块。

# module StringSet = Set.Make(String);;
module StringSet :
  sig
    type elt = string
    type t = Set.Make(String).t
    val empty : t
    val add : elt -> t -> t
    val singleton : elt -> t
    val remove : elt -> t -> t
    val union : t -> t -> t
    val inter : t -> t -> t
...
  end

将新创建的模块命名为 StringSet 后，OCaml 的顶层将显示该模块的签名。由于它包含大量函数，这里复制的输出为了简洁起见进行了缩短（...）。

该模块还定义了两种类型

• type elt = string 用于元素，以及
• type t = Set.Make(String).t 用于集合。

创建集合

1. 我们可以使用 StringSet.empty 创建一个空集合

# StringSet.empty ;;
- : StringSet.t = <abstr>

# StringSet.empty |> StringSet.to_list;;
- : string list = []

对于 StringSet.empty，您可以看到 OCaml 顶层显示了占位符 <abstr> 而不是实际值。但是，使用 StringSet.to_list 将字符串集合转换为列表将导致一个空列表。

(请记住，对于 OCaml 5.1 之前的版本，它将是 StringeSet.empty |> StringSet.elements;;)

2. 使用 StringSet.singleton 创建一个具有单个元素的集合

# StringSet.singleton "hello";;
- : StringSet.t = <abstr>

# StringSet.(singleton "hello" |> to_list);;
- : string list = ["hello"]

3. 使用 StringSet.of_list 将列表转换为集合

# StringSet.of_list ["hello"; "hi"];;
- : StringSet.t = <abstr>

# StringSet.(of_list ["hello"; "hi"] |> to_list);;
- : string list = ["hello"; "hi"]

还有一个相关的函数 StringSet.of_seq: string Seq.t -> StringSet.t，它从 序列 创建一个集合。

使用集合

让我们看一下使用这两个集合进行集合操作的一些函数。

# let first_set = ["hello"; "hi"] |> StringSet.of_list;;
- : val first_set : StringSet.t = <abstr>

# let second_set = ["good morning"; "hi"] |> StringSet.of_list;;
- : val second_set : StringSet.t = <abstr>

向集合添加元素

# StringSet.(first_set |> add "good morning" |> to_list);;
- : string list = ["good morning"; "hello"; "hi"]

函数 StringSet.add 类型为 string -> StringSet.t -> StringSet.t，它同时接受一个字符串和一个字符串集合。它返回一个新的字符串集合。在 OCaml 中，使用 Set.Make 函子创建的集合是不可变的，因此每次您向集合添加或删除元素时，都会创建一个新集合。旧值保持不变。

从集合中删除元素

# StringSet.(first_set |> remove "hello" |> to_list);;
- : string list = ["hi"]

函数 StringSet.remove 类型为 string -> StringSet.t -> StringSet.t，它同时接受一个字符串和一个字符串集合。它返回一个新的字符串集合，其中不包含给定的字符串。

两个集合的并集

# StringSet.(union first_set second_set |> to_list);;
- : string list = ["good morning"; "hello"; "hi"]

使用函数 StringSet.union，我们可以计算两个集合的并集。

两个集合的交集

# StringSet.(inter first_set second_set |> to_list);;
- : string list = ["hi"]

使用函数 StringSet.inter，我们可以计算两个集合的交集。

从另一个集合中减去一个集合

# StringSet.(diff first_set second_set |> to_list);;
- : string list = ["hello"]

使用函数 StringSet.diff，我们可以从第一个集合中删除第二个集合的元素。

过滤集合

# ["good morning"; "hello"; "hi"]
  |> StringSet.of_list
  |> StringSet.filter (fun str -> String.length str <= 5)
  |> StringSet.to_list;;
- : string list = ["hello"; "hi"]

函数 StringSet.filter 类型为 (string -> bool) -> StringSet.t -> StringSet.t，它通过保留现有集合中满足谓词的元素来创建一个新集合。

检查元素是否包含在集合中

# ["good morning"; "hello"; "hi"]
  |> StringSet.of_list
  |> StringSet.mem "hello";;
- : bool = true

要检查元素是否包含在集合中，请使用 StringSet.mem 函数。

使用自定义比较器的集合

Set.Make 函数式期望一个包含两个定义的模块：一个表示元素类型的 t 类型和一个签名为 t -> t -> int 的函数 compare。String 模块符合这种结构，因此我们可以直接将 String 作为参数传递给 Set.Make。顺便说一下，许多其他模块也具有这种结构，包括 Int 和 Float，因此它们也可以直接传递给 Set.Make 以构建相应的集合模块。

我们创建的 StringSet 模块使用 String 模块提供的内置 compare 函数。

假设我们想要创建一个字符串集合，该集合执行不区分大小写的比较，而不是 String.compare 提供的区分大小写的比较。

我们可以通过将一个临时模块传递给 Set.Make 函数来实现这一点。

# module CISS = Set.Make(struct
  type t = string
  let compare a b = compare (String.lowercase_ascii a) (String.lowercase_ascii b)
end);;
- : sig
    type elt = string
    type t
    val empty : t
    val is_empty : t -> bool
    val mem : elt -> t -> bool
    val add : elt -> t -> t
(...)

我们将生成的模块命名为 CISS（代表“不区分大小写字符串集”）。

您可以看到该模块具有预期的行为

# CISS.singleton "hello" |> CISS.add "HELLO" |> CISS.to_list;;
- : string list = ["hello"]

值 "HELLO" 未添加到集合中，因为它被认为等于集合中已经包含的值 "hello"。

您可以对元素使用任何类型，只要您定义一个有意义的 compare 操作。

# type color = Red | Green | Blue;;
type color = Red | Green | Blue

# module SC = Set.Make(struct
  type t = color
  let compare a b =
    match a, b with
    | (Red, Red) -> 0
    | (Red, Green) -> 1
    | (Red, Blue) -> 1
    | (Green, Red) -> -1
    | (Green, Green) -> 0
    | (Green, Blue) -> 1
    | (Blue, Red) -> -1
    | (Blue, Green) -> -1
    | (Blue, Blue) -> 0
end);;
...

结论

我们通过使用 Set.Make 函数式创建一个 StringSet 模块，概述了 OCaml 的 Set 模块。此外，我们还研究了如何根据自定义比较函数创建集合。有关更多信息，请参阅标准库文档中的 Set。