Модуль типа Set.S

module type S = sig .. end

Подпись результата применения функтора Set.Make.

Множества

type elt

Тип элементов множества.

type t

Тип множеств.

val empty : t

Пустое множество.

val add : elt -> t -> t

add x s возвращает множество, содержащее все элементы s, плюс x. Если x уже присутствует в s, то s возвращается без изменений (результат функции в этом случае физически равен s).

До 4.03 Физическое равенство не гарантировалось.

val singleton : elt -> t

singleton x возвращает одноэлементное множество, содержащее только x.

val remove : elt -> t -> t

remove x s возвращает множество, содержащее все элементы s, за исключением x. Если x не присутствует в s, то s возвращается без изменений (результат функции в этом случае физически равен s).

До 4.03 Физическое равенство не гарантировалось.

val union : t -> t -> t

Объединение множеств.

val inter : t -> t -> t

Пересечение множеств.

val disjoint : t -> t -> bool

Проверка, являются ли два множества непересекающимися.

С 4.08

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, если множество пусто.

С 4.05

val max_elt : t -> elt

Аналогично Set.S.min_elt, но возвращает наибольший элемент заданного множества.

val max_elt_opt : t -> elt option

Аналогично Set.S.min_elt_opt, но возвращает наибольший элемент заданного множества.

С 4.05

val choose : t -> elt

Возвращает один элемент заданного множества, или генерирует исключение Not_found, если множество пусто. Выбор элемента не определен, но для равных множеств выбираются равные элементы.

val choose_opt : t -> elt option

Возвращает один элемент заданного множества, или None, если множество пусто. Выбор элемента не определен, но для равных множеств выбираются равные элементы.

С 4.05

Поиск

val find : elt -> t -> elt

find x s возвращает элемент s, равный x, (согласно Ord.compare), или генерирует исключение Not_found, если такой элемент не существует.

С 4.01

val find_opt : elt -> t -> elt option

find_opt x s возвращает элемент s, равный x, (согласно Ord.compare), или None, если такой элемент не существует.

С 4.05

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

find_first f s, где f — монотонно возрастающая функция, возвращает наименьший элемент e множества s, такой что f e, или генерирует исключение Not_found, если такого элемента нет.

Например, find_first (fun e -> Ord.compare e x >= 0) s вернёт первый элемент e из s, где Ord.compare e x >= 0 (интуитивно: e >= x), или генерирует исключение Not_found, если x больше любого элемента s.

С 4.05

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

find_first_opt f s, где f — монотонно возрастающая функция, возвращает опцию, содержащую наименьший элемент e множества s, такой что f e, или None, если такого элемента нет.

С 4.05

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

find_last f s, где f — монотонно убывающая функция, возвращает наибольший элемент e множества s, такой что f e, или генерирует исключение Not_found, если такого элемента нет.

С 4.05

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

find_last_opt f s, где f — монотонно убывающая функция, возвращает опцию, содержащую наибольший элемент e множества s, такой что f e, или None, если такого элемента нет.

С 4.05

Проход

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

iter f s последовательно применяет f к каждому элементу s . Элементы s подаются в f в порядке возрастания относительно порядка над типом элементов.

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

fold f s init вычисляет (f xN ... (f x2 (f x1 init))...), где x1 ... xN — элементы s, упорядоченные по возрастанию.

Преобразование

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

map f s — множество, элементы которого равны f a0, f a1,... f aN, где a0, a1,... aN — элементы s.

Элементы передаются в f в порядке возрастания относительно порядка над типом элементов.

Если ни один элемент s не изменяется функцией f, то s возвращается без изменений. (Если каждый результат f физически равен своему входу, то возвращаемое множество физически равно s.)

С 4.04

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

filter f s возвращает множество всех элементов s , удовлетворяющих предикату f. Если f выполняется для всех элементов s, то s возвращается без изменений (результат функции в этом случае физически равен s).

До 4.03 Физическое равенство не гарантировалось.

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

filter_map f s возвращает множество всех v таких, что f x = Some v для некоторого элемента x множества s.

Например,

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

является множеством половин чётных элементов s.

Если ни один элемент s не изменяется или удаляется функцией f (если f x = Some x для каждого элемента x), то s возвращается без изменений: результат функции физически равен s.

С 4.11

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

partition f s возвращает пару множеств (s1, s2), где s1 — множество всех элементов s , удовлетворяющих предикату f, а s2 — множество всех элементов s , не удовлетворяющих предикату f.

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

split x s возвращает тройку (l, present, r), где l — множество элементов s , строго меньших x; r — множество элементов s , строго больших x; present равно false , если s не содержит элементов, равных x, или true , если s содержит элемент, равный x.

Предикаты и сравнения

val is_empty : t -> bool

Проверка, является ли множество пустым.

val mem : elt -> t -> bool

mem x s проверяет, принадлежит ли x множеству s.

val equal : t -> t -> bool

equal s1 s2 проверяет, равны ли множества s1 и s2, то есть содержат ли они одинаковые элементы.

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.

Since 5.1

val of_list : elt list -> t

of_list l создаёт множество из списка элементов. Обычно это более эффективно, чем применение функции add к списку, за исключением, возможно, списков с множеством дублирующихся элементов.

Since 4.02

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

to_seq_from x s итерируется по подмножеству элементов s в порядке возрастания, начиная с x или выше.

Since 4.07

val to_seq : t -> elt Seq.t

Итерирование по всему множеству в порядке возрастания

Since 4.07

val to_rev_seq : t -> elt Seq.t

Итерирование по всему множеству в порядке убывания

Since 4.12

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

Добавление заданных элементов в множество в указанном порядке.

Since 4.07

val of_seq : elt Seq.t -> t

Создание множества из заданных связываний

Since 4.07