函子 Set.Make

module Make: 
functor (Ord : OrderedType-> S with type elt = Ord.t

给定一个全序类型,该函子构建集合结构的实现。

参数
Ord : OrderedType

集合

type elt 

集合元素的类型。

type t 

集合的类型。

val empty : t

空集合。

val add : elt -> t -> t

add x s 返回一个包含 s 的所有元素以及 x 的集合。如果 x 已经在 s 中,则返回未更改的 s(此时函数的结果与 s 物理相等)。

val singleton : elt -> t

singleton x 返回仅包含 x 的单元素集合。

val remove : elt -> t -> t

remove x s 返回一个包含 s 的所有元素(除 x 之外)的集合。如果 x 不在 s 中,则返回未更改的 s(此时函数的结果与 s 物理相等)。

val union : t -> t -> t

集合并集。

val inter : t -> t -> t

集合交集。

val disjoint : t -> t -> bool

测试两个集合是否不相交。

val diff : t -> t -> t

集合差集:diff s1 s2 包含 s1 中不在 s2 中的元素。

val cardinal : t -> int

返回集合中元素的数量。

元素

val elements : t -> elt list

返回给定集合的所有元素的列表。返回的列表按 Ord.compare 排序递增,其中 Ord 是提供给 Set.Make 的参数。

val min_elt : t -> elt

返回给定集合的最小元素(根据 Ord.compare 排序),如果集合为空,则引发 Not_found 异常。

val min_elt_opt : t -> elt option

返回给定集合的最小元素(根据 Ord.compare 排序),如果集合为空,则返回 None

val max_elt : t -> elt

Set.S.min_elt 相同,但返回给定集合的最大元素。

val max_elt_opt : t -> elt option

Set.S.min_elt_opt 相同,但返回给定集合的最大元素。

val choose : t -> elt

返回给定集合的一个元素,如果集合为空,则引发 Not_found 异常。选择的元素未指定,但相等集合将选择相等元素。

val choose_opt : t -> elt option

返回给定集合的一个元素,如果集合为空,则返回 None。选择的元素未指定,但相等集合将选择相等元素。

搜索

val find : elt -> t -> elt

find x s 返回 s 中等于 x 的元素(根据 Ord.compare),如果没有这样的元素,则引发 Not_found 异常。

val find_opt : elt -> t -> elt option

find_opt x s 返回 s 中等于 x 的元素(根据 Ord.compare),如果没有这样的元素,则返回 None

val find_first : (elt -> bool) -> t -> elt

find_first f s,其中 f 是单调递增函数,返回 s 中满足 f e 的最小元素 e,如果没有这样的元素,则引发 Not_found 异常。

例如,find_first (fun e -> Ord.compare e x >= 0) s 将返回 s 中第一个满足 Ord.compare e x >= 0 的元素 e(直观地说:e >= x),如果 x 大于 s 中的任何元素,则引发 Not_found 异常。

val find_first_opt : (elt -> bool) -> t -> elt option

find_first_opt f s,其中 f 是单调递增函数,返回一个包含 s 中满足 f e 的最小元素 e 的选项,如果没有这样的元素,则返回 None

val find_last : (elt -> bool) -> t -> elt

find_last f s,其中 f 是单调递减函数,返回 s 中满足 f e 的最大元素 e,如果没有这样的元素,则引发 Not_found 异常。

val find_last_opt : (elt -> bool) -> t -> elt option

find_last_opt f s,其中 f 是单调递减函数,返回一个包含 s 中满足 f e 的最大元素 e 的选项,如果没有这样的元素,则返回 None

遍历

val iter : (elt -> unit) -> t -> unit

iter f sf 依次应用于 s 的所有元素。 s 的元素按元素类型上的排序递增顺序呈现给 f

val fold : (elt -> 'acc -> 'acc) -> t -> 'acc -> 'acc

fold f s init 计算 (f xN ... (f x2 (f x1 init))...),其中 x1 ... xNs 的元素,按递增顺序排列。

转换

val map : (elt -> elt) -> t -> t

map f s 是一个集合,其元素是 f a0f a1... f aN,其中 a0a1...aNs 的元素。

元素按元素类型上的排序递增顺序传递给 f

如果 s 的任何元素都没有被 f 更改,则返回未更改的 s。(如果 f 的每个输出与其输入物理相等,则返回的集合与 s 物理相等。)

val filter : (elt -> bool) -> t -> t

filter f s 返回 s 中满足谓词 f 的所有元素的集合。如果 f 满足 s 中的每个元素,则返回未更改的 s(此时函数的结果与 s 物理相等)。

val filter_map : (elt -> elt option) -> t -> t

filter_map f s 返回所有 v 的集合,其中对于 s 的某个元素 xf x = Some v

例如,

filter_map (fun n -> if n mod 2 = 0 then Some (n / 2) else None) s

s 中偶数元素的一半的集合。

如果 s 的任何元素都没有被 f 更改或删除(如果对于每个元素 xf x = Some x),则返回未更改的 s:此时函数的结果与 s 物理相等。

val partition : (elt -> bool) -> t -> t * t

partition f s 返回一对集合 (s1, s2),其中 s1s 中满足谓词 f 的所有元素的集合,s2s 中不满足 f 的所有元素的集合。

val split : elt -> t -> t * bool * t

split x s 返回一个三元组 (l, present, r),其中 ls 中严格小于 x 的元素的集合;rs 中严格大于 x 的元素的集合;如果 s 不包含等于 x 的元素,则 presentfalse,如果 s 包含等于 x 的元素,则 presenttrue

谓词和比较

val is_empty : t -> bool

测试集合是否为空。

val mem : elt -> t -> bool

mem x s 用于测试 x 是否属于集合 s

val equal : t -> t -> bool

equal s1 s2 用于测试集合 s1s2 是否相等,即包含相同的元素。

val compare : t -> t -> int

集合间的全序关系。可用作集合的集合的排序函数。

val subset : t -> t -> bool

subset s1 s2 用于测试集合 s1 是否是集合 s2 的子集。

val for_all : (elt -> bool) -> t -> bool

for_all f s 检查集合的所有元素是否都满足谓词 f

val exists : (elt -> bool) -> t -> bool

exists f s 检查集合中是否至少有一个元素满足谓词 f

转换

val to_list : t -> elt list

to_list s 等同于 Set.S.elements s

val of_list : elt list -> t

of_list l 从元素列表创建集合。这通常比对列表折叠 add 操作更有效,除非列表中包含许多重复元素。

val to_seq_from : elt -> t -> elt Seq.t

to_seq_from x s 迭代 s 的一个子集,按升序排列,从 x 或更大的元素开始。

val to_seq : t -> elt Seq.t

按升序迭代整个集合。

val to_rev_seq : t -> elt Seq.t

按降序迭代整个集合。

val add_seq : elt Seq.t -> t -> t

将给定元素按顺序添加到集合中。

val of_seq : elt Seq.t -> t

根据给定的绑定构建一个集合。