Module IndexSet.Map

Module for maps from index sets to values.

type 'n key = 'n t

StdMapS1

This signature provides a parameterized version of the standard library's StdMap.S signature. It is lifted to work with parameterized keys 'n key instead of ground ones key.

Note. The type ('n, 'a) t represents a map indexed by keys parameterized by 'n and carrying values of type 'a. This is a direct adaptation of the standard library's StdMap.S signature, generalized to support parameterized keys.

@see StdMap.S (standard library) for the original signature upon which this is based.

type ('n, 'a) t = private 'a IntSetMap.t

Basic operations

val empty : ('n, 'a) t

empty is the empty map.

val is_empty : ('n, 'a) t -> bool

is_empty m returns true if m is the empty map.

val mem : 'n key -> ('n, 'a) t -> bool

mem k m returns true if key k is bound in map m.

val add : 'n key -> 'a -> ('n, 'a) t -> ('n, 'a) t

add k d m returns a map that is the extension of m with binding k ↦ d. If k was already bound in m, the old binding is replaced by the new one.

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

update k f m returns a map same as m, except that the binding for k is modified by f. If the binding for k is present in m, f is called with the current value, otherwise f is called with None. The result of f determines the binding state for k in the resulting map.

val singleton : 'n key -> 'a -> ('n, 'a) t

singleton k d returns a map containing the single binding k ↦ d.

val remove : 'n key -> ('n, 'a) t -> ('n, 'a) t

remove m k returns a map containing the same bindings as m, except that k is unbound in the result.

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

merge f m1 m2 returns a map with the same bindings as m1 and m2, except that bindings that appear in both maps are combined using f. Specifically, for each key k, if k is bound in m1 to a1 and in m2 to a2, then k is bound in the result to f k a1 a2.

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

union f m1 m2 is an alias for merge with the union combinator.

Comparisons

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

compare cmp m1 m2 compares the two maps m1 and m2 using cmp to compare values. Returns a negative number if m1 is strictly smaller than m2, a positive number if m1 is strictly greater than m2, or zero if they are equal.

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

equal eq m1 m2 returns true if the two maps are equal up to eq, which compares values.

Iteration

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

iter f m invokes f k d for each binding k ↦ d in m. Bindings are presented in ascending key order.

val fold : ('n key -> 'a -> 'b -> 'b) -> ('n, 'a) t -> 'b -> 'b

fold f m seed computes f k d acc for each binding in m, in ascending key order. The initial value of acc is seed; the final value is the returned value.

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

for_all f m returns true if f k d is true for all bindings k ↦ d in m.

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

exists f m returns true if f k d is true for at least one binding k ↦ d in m.

Filtering

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

filter f m returns the map with the same bindings as m, but only those bindings k ↦ d for which f k d returns true.

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

filter_map f m returns the map with bindings k ↦ d' for each binding k ↦ d in m such that f k d returns Some d'.

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

partition f m returns the pair (m1, m2) where m1 contains all bindings k ↦ d in m such that f k d is true, and m2 contains the others.

Cardinality

val cardinal : ('n, 'a) t -> int

cardinal m returns the number of bindings in m.

Bindings extraction

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

bindings m is the list of all bindings in m, in ascending order.

val min_binding : ('n, 'a) t -> 'n key * 'a

min_binding m returns the pair (k, d) where k is the smallest key bound in m and d is its binding. Raises Not_found if m is empty.

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

min_binding_opt m returns Some (k, d) where (k, d) is the smallest key bound in m, or None if m is empty.

val max_binding : ('n, 'a) t -> 'n key * 'a

max_binding m returns the pair (k, d) where k is the largest key bound in m and d is its binding. Raises Not_found if m is empty.

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

max_binding_opt m returns Some (k, d) where (k, d) is the largest key bound in m, or None if m is empty.

val choose : ('n, 'a) t -> 'n key * 'a

choose m returns an arbitrarily chosen binding (k, d) from m. Raises Not_found if m is empty.

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

choose_opt m returns Some (k, d) if k is bound in m, or None if m is empty.

Splitting

val split : 'n key -> ('n, 'a) t -> ('n, 'a) t * 'a option * ('n, 'a) t

split k m returns (m1, opt, m2) where:

  • m1 contains all bindings with keys strictly smaller than k
  • m2 contains all bindings with keys strictly larger than k
  • opt is Some d if k is bound to d in m, or None otherwise

Find operations

val find : 'n key -> ('n, 'a) t -> 'a

find k m returns the value d associated with key k in m. Raises Not_found if k is not bound in m.

val find_opt : 'n key -> ('n, 'a) t -> 'a option

find_opt k m returns Some d if k is bound to d in m, or None otherwise.

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

find_first f m returns the first binding (k, d) such that f k d is true, or raises Not_found if no such binding exists.

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

find_first_opt f m returns Some (k, d) for the first binding such that f k d is true, or None if no such binding exists.

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

find_last f m returns the last binding (k, d) such that f k d is true, or raises Not_found if no such binding exists.

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

find_last_opt f m returns Some (k, d) for the last binding such that f k d is true, or None if no such binding exists.

Mapping

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

map f m returns the map with the same keys as m, where each value d has been replaced by f d.

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

mapi f m returns the map with the same keys as m, where each value has been replaced by f k d for the corresponding key k.

Sequences

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

to_seq m returns a sequence of all bindings in m, in ascending key order.

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

to_rev_seq m returns a sequence of all bindings in m, in descending key order.

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

to_seq_from k m returns a sequence of all bindings in m with keys greater than or equal to k.

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

add_seq s m returns the map that is the union of m and all bindings in sequence s.

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

of_seq s returns the map containing all bindings from sequence s.