Модуль Map.S

module type S = sig .. end

Выходная сигнатура функтора Map.Make.

Карты

type key

Тип ключей карты.

type !+'a t

Тип карт от типа key до типа 'a.

val empty : 'a t

Пустая карта.

val add : key -> 'a -> 'a t -> 'a t

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

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

val add_to_list : key -> 'a -> 'a list t -> 'a list t

add_to_list key data m это m с key сопоставленным с l таким образом, что l это data :: Map.find key m если key была связана в m и [v] в противном случае.

С 5.1

val update : key -> ('a option -> 'a option) -> 'a t -> 'a t

update key f m возвращает карту, содержащую те же связи, что и m, за исключением связи key. В зависимости от значения y, где y есть f (find_opt key m), связь key добавляется, удаляется или обновляется. Если y равно None, связь удаляется, если она существует; в противном случае, если y равно Some z, то key ассоциируется с z в результирующей карте. Если key уже было связано в m со значением, физически равным z, то m возвращается без изменений (результат функции тогда физически равен m).

С 4.06

val singleton : key -> 'a -> 'a t

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

С 3.12

val remove : key -> 'a t -> 'a t

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

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

val merge : (key -> 'a option -> 'b option -> 'c option) ->       'a t -> 'b t -> 'c t

merge f m1 m2 вычисляет карту, ключи которой являются подмножеством ключей m1 и m2 . Присутствие каждой такой связи, а также соответствующее значение, определяется функцией f. В терминах операции find_opt мы имеем find_opt x (merge f m1 m2) = f x (find_opt x m1) (find_opt x m2) для любого ключа x, при условии, что f x None None = None.

С 3.12

val union : (key -> 'a -> 'a -> 'a option) ->       'a t -> 'a t -> 'a t

union f m1 m2 вычисляет карту, ключи которой являются подмножеством ключей m1 и m2 . Когда одна и та же связь определена в обоих аргументах, функция f используется для их объединения. Это частный случай merge: union f m1 m2 эквивалентно merge f' m1 m2, где

f' _key None None = None
f' _key (Some v) None = Some v
f' _key None (Some v) = Some v
f' key (Some v1) (Some v2) = f key v1 v2

С 4.03

val cardinal : 'a t -> int

Возвращает количество связей в карте.

С 3.12

Связи

val bindings : 'a t -> (key * 'a) list

Возвращает список всех связей данной карты. Возвращаемый список отсортирован в порядке возрастания ключей относительно порядка Ord.compare, где Ord — аргумент, переданный Map.Make.

С 3.12

val min_binding : 'a t -> key * 'a

Возвращает связь с наименьшим ключом в данной карте (относительно порядка Ord.compare ), или вызывает исключение Not_found, если карта пуста.

С 3.12

val min_binding_opt : 'a t -> (key * 'a) option

Возвращает связь с наименьшим ключом в данной карте (относительно порядка Ord.compare ), или None, если карта пуста.

С 4.05

val max_binding : 'a t -> key * 'a

То же, что и Map.S.min_binding, но возвращает связь с наибольшим ключом в данной карте.

С 3.12

val max_binding_opt : 'a t -> (key * 'a) option

То же, что и Map.S.min_binding_opt, но возвращает связь с наибольшим ключом в данной карте.

С 4.05

val choose : 'a t -> key * 'a

Возвращает одну связь данной карты, или вызывает исключение Not_found, если карта пуста. Какой связь выбирается, не определено, но одинаковые связи будут выбраны для одинаковых карт.

С 3.12

val choose_opt : 'a t -> (key * 'a) option

Возвращает одну связь данной карты, или None, если карта пуста. Какой связь выбирается, не определено, но одинаковые связи будут выбраны для одинаковых карт.

С 4.05

Поиск

val find : key -> 'a t -> 'a

find x m возвращает текущее значение x в m, или вызывает исключение Not_found, если нет связи для x.

val find_opt : key -> 'a t -> 'a option

find_opt x m возвращает Some v, если текущее значение x в m равно v, или None, если нет связи для x.

С 4.05

val find_first : (key -> bool) -> 'a t -> key * 'a

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

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

С 4.05

val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option

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

С 4.05

val find_last : (key -> bool) -> 'a t -> key * 'a

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

С 4.05

val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option

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

С 4.05

Перебор

val iter : (key -> 'a -> unit) -> 'a t -> unit

iter f m применяет f ко всем связям в карте m . f получает ключ в качестве первого аргумента и соответствующее значение как второй аргумент. Связи передаются в f в порядке возрастания относительно порядка над типом ключей.

val fold : (key -> 'a -> 'acc -> 'acc) -> 'a t -> 'acc -> 'acc

fold f m init вычисляет (f kN dN ... (f k1 d1 init)...), где k1 ... kN — ключи всех связей в m (в порядке возрастания), а d1 ... dN — связанные данные.

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

val map : ('a -> 'b) -> 'a t -> 'b t

map f m возвращает карту с тем же доменом, что и m, где связанное значение a всех связей m было заменено результатом применения f к a . Связи передаются в f в порядке возрастания относительно порядка над типом ключей.

val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t

То же самое, что и Map.S.map, но функция получает в качестве аргументов и ключ, и соответствующее значение для каждой связи карты.

val filter : (key -> 'a -> bool) -> 'a t -> 'a t

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

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

val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t

filter_map f m применяет функцию f к каждой связи m, и строит карту из результатов. Для каждой связи (k, v) в входной карте:

если f k v это None, то k не будет в результате,
если f k v это Some v', то связь (k, v') будет в выходной карте.

Например, следующая функция для карт, значениями которых являются списки

        filter_map
          (fun _k li -> match li with [] -> None | _::tl -> Some tl)
          m

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

С 4.11

val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t

partition f m возвращает пару карт (m1, m2), где m1 содержит все связи m , которые удовлетворяют предикату f, и m2 — это карта со всеми связями m , которые не удовлетворяют f.

С 3.12

val split : key -> 'a t -> 'a t * 'a option * 'a t

split x m возвращает тройку (l, data, r), где l — это карта со всеми связями m , ключ которых строго меньше x; r — это карта со всеми связями m , ключ которых строго больше x; data — это None , если m не содержит связи для x, или Some v , если m связывает v с x.

С 3.12

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

val is_empty : 'a t -> bool

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

val mem : key -> 'a t -> bool

mem x m возвращает true , если m содержит связь для x, и false в противном случае.

val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool

equal cmp m1 m2 проверяет, равны ли карты m1 и m2, то есть, содержат ли они одинаковые ключи и связывают ли их с одинаковыми данными. cmp — это предикат равенства, используемый для сравнения данных, связанных с ключами.

val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int

Полный порядок между картами. Первый аргумент — это полный порядок, используемый для сравнения данных, связанных с одинаковыми ключами в двух картах.

val for_all : (key -> 'a -> bool) -> 'a t -> bool

for_all f m проверяет, удовлетворяют ли все связи карты предикату f.

С 3.12

val exists : (key -> 'a -> bool) -> 'a t -> bool

exists f m проверяет, удовлетворяет ли хотя бы одна связь карты предикату f.

С 3.12

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

val to_list : 'a t -> (key * 'a) list

to_list m это Map.S.bindings m.

С 5.1

val of_list : (key * 'a) list -> 'a t

of_list bs добавляет связи bs в пустую карту в порядке списка (если ключ связан дважды в bs, последний берет верх).

С 5.1

val to_seq : 'a t -> (key * 'a) Seq.t

Итерация по всей карте в порядке возрастания ключей

С 4.07

val to_rev_seq : 'a t -> (key * 'a) Seq.t

Итерация по всей карте в порядке убывания ключей

С 4.12

val to_seq_from : key -> 'a t -> (key * 'a) Seq.t

to_seq_from k m итерируется по подмножеству связей m, в порядке возрастания ключей, от ключа k или выше.

С 4.07

val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t

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

С 4.07

val of_seq : (key * 'a) Seq.t -> 'a t

Построение карты из заданных связей

С 4.07