Functor MoreLabels.Map.Make

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

Функтор, создающий реализацию структуры map для заданного типа с полным порядком.

Параметры:

Ord : OrderedType

Мапы

type key

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

type !+'a t

Тип мап из типа key в тип 'a.

val empty : 'a t

Пустая мапа.

val add : key:key ->       data:'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:key ->       data:'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:key ->       f:('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 : f:(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 : f:(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 — аргумент, переданный в MoreLabels.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

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

С 3.12

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

Аналогично MoreLabels.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 : f:(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 : f:(key -> bool) ->       'a t -> (key * 'a) option

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

С 4.05

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

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

С 4.05

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

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

С 4.05

Обход

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

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

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

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

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

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

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

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

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

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

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

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

val filter_map : f:(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 : f:(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 : cmp:('a -> 'a -> bool) ->       'a t -> 'a t -> bool

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

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

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

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

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

С 3.12

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

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

С 3.12

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

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

to_list m это MoreLabels.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