集合
簡介
Set 提供了函子 Set.Make。您必須先傳遞一個模組給 Set.Make。它會指定您集合的元素類型。作為回傳，您會得到另一個具有這些元素集合操作的模組。
免責聲明：本教學中的範例需要 OCaml 5.1。如果您正在執行舊版的 OCaml，您可以改用 elements 而不是 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表示集合。
建立集合
- 我們可以使用
StringSet.empty建立一個空集合
# StringSet.empty ;;
- : StringSet.t = <abstr>
# StringSet.empty |> StringSet.to_list;;
- : string list = []
對於 StringSet.empty，您可以看到 OCaml 頂層顯示佔位符 <abstr> 而不是實際值。但是，使用 StringSet.to_list 將字串集合轉換為列表會產生一個空列表。
（請記住，對於 5.1 之前的 OCaml 版本，它會是 StringeSet.empty |> StringSet.elements;;）
- 使用
StringSet.singleton建立具有單個元素的集合
# StringSet.singleton "hello";;
- : StringSet.t = <abstr>
# StringSet.(singleton "hello" |> to_list);;
- : string list = ["hello"]
- 使用
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"]
類型為 string -> StringSet.t -> StringSet.t 的函式 StringSet.add 接受字串和字串集合。它會回傳一個新的字串集合。在 OCaml 中使用 Set.Make 函子建立的集合是不可變的，因此每次您從集合中新增或移除元素時，都會建立一個新的集合。舊的值不會變更。
從集合中移除元素
# StringSet.(first_set |> remove "hello" |> to_list);;
- : string list = ["hi"]
類型為 string -> StringSet.t -> StringSet.t 的函式 StringSet.remove 接受字串和字串集合。它會回傳一個不包含給定字串的新字串集合。
兩個集合的聯集
# 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"]
類型為 (string -> bool) -> StringSet.t -> StringSet.t 的函式 StringSet.filter 會透過保留現有集合中滿足謂詞的元素來建立新的集合。
檢查元素是否包含在集合中
# ["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 (「Case Insensitive String Set」的縮寫，即「不區分大小寫的字串集合」)。
您可以觀察到這個模組具有預期的行為。
# 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。