Functor Map.Make

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

Functor создающий реализацию структуры карты, заданной для полностью упорядоченного типа.

Параметры:

Ord : OrderedType

Карты

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