Module Map.Make

Parameters

module Ord : OrderedType

Signature

module M : sig ... end

4.05 Compatibility Functions

These 4.05 functions provide compatibility with earlier versions of the standard library. If Prelude is linked with 4.05 or later, the official functions will be used instead.

Official OCaml Map Functions

include module type of struct include M end
type key = Ord.t
type !'a t = 'a Stdlib__Map.Make(Ord).t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge : (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val min_binding_opt : 'a t -> (key * 'a) option
val max_binding : 'a t -> key * 'a
val max_binding_opt : 'a t -> (key * 'a) option
val choose : 'a t -> key * 'a
val choose_opt : 'a t -> (key * 'a) option
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val find_opt : key -> 'a t -> 'a option
val find_first : (key -> bool) -> 'a t -> key * 'a
val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
val find_last : (key -> bool) -> 'a t -> key * 'a
val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
val to_seq : 'a t -> (key * 'a) Stdlib.Seq.t
val to_rev_seq : 'a t -> (key * 'a) Stdlib.Seq.t
val to_seq_from : key -> 'a t -> (key * 'a) Stdlib.Seq.t
val add_seq : (key * 'a) Stdlib.Seq.t -> 'a t -> 'a t
val of_seq : (key * 'a) Stdlib.Seq.t -> 'a t

Additional Map Functions

Development Utils

val string_of_binding : ?sep:string -> key:('a -> string) -> value:('b -> string) -> ('a * 'b) -> string

(string_of_binding ~key ~value (k,v)) is a string representation of the binding of k to v, separated by sep (default: " -> "), where the string representation of each key is given by ~key and the string representation of each value is given by ~value.

val to_string : ?sep:string -> key:(key -> string) -> value:('a -> string) -> 'a t -> string

(to_string ?(sep=", ") f t) returns a string representation of the map t, where the string representation of each key is given by ~key and the string representation of each value is given by ~value.

val print : ?sep:string -> key:(key -> string) -> value:('a -> string) -> 'a t -> unit

(print ?sep ~key ~value t) is (to_string ?sep ~key ~value t |> print_endline).

Creation

val random : ?size:(unit -> int) -> key:(unit -> key) -> value:(unit -> 'a) -> unit -> 'a t

(random ?size ~key ~value ()) is a random map of size (size ()) (default: < 100), and each binding is given by (key (), value ()).

val cmp : Ord.t -> Ord.t -> int

cmp is Ord.compare and is the comparison function that implements this map.

Map Size

val size : 'a t -> int

size is cardinal.

Access

val lookup : Ord.t -> 'a t -> key * 'a

(lookup key) is like find but returns the complete binding (key,value).

This is useful when Ord.compare maps many keys to one, e.g. (let compare = String.(on compare lowercase_ascii)).

Adding Values to the Map

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

(replace k v t) replaces the binding for k in t with a new binding (k,v).

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

(of_list t alist) adds all the bindings in alist to t (which could be empty).

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

(adjoin vadd empty) returns a function (f k v m) that adjoins v to a collection of values associated with key k. vadd and empty might be Lists.cons and [] for list accumulators, or S.add and S.empty for some set S.

See Multiset for common situations.

Examples:

  • accumulate the case-insensitive spellings of words:

    module M = Map.Make (String)
let each k = M.adjoin cons [] (String.lowercase_ascii k) k in
List.foldr each M.empty (split "Foo Bar bAR FOO") |> M.to_list
= [[("bar", ["Bar"; "bAR"]); ("foo", ["Foo"; "FOO"])]]

  • separate out the even versus the odd numbers in xs (indexed under 0 for even, 1 for odd):

    foldr (fun x m -> adjoin cons [] (abs (x mod 2)) x m) empty xs
val classify : ('a -> key) -> ('a -> 'b -> 'b) -> 'b -> 'a -> 'b t -> 'b t

(classify f vadd empty) is a classifying adjoiner.

 module M = Map.Make (struct type t = bool let compare = compare end)
M.(foldr (classify Int.even cons []) empty (1--10) |> to_list)
= [(false, [1; 3; 5; 7; 9]); (true, [2; 4; 6; 8; 10])]
val incr : ?z:int -> ?i:int -> key -> int t -> int t

(incr ?z ?i k m) is (adjoin (+) z k i m), i.e. incr generates a function for counting instances of items (k) in an (int t) (m).

~z is the "zero" for the counters (default: 0); ~i is the increment (default: 1).

Count the chars in a string:

String.foldr M.incr "abbcccd" M.empty |> M.to_list =
[('a', 1); ('b', 2); ('c', 3); ('d', 1)]

Accessing Bindings in Key Order

The most efficient way to access the bindings of a map in key order is to use fold, but sometimes access is required in a non-fold context. OCaml's map doesn't provide this access directly, so these functions do it by calling partition, so each call to one of these functions is proportional to the size of the map.

val neighbors : Ord.t -> 'a t -> (key * 'a) Option.t * (key * 'a) Option.t

(neighbors k m) is the pair (prev,next) where prev and next are, respectively, options carrying the binding prior to and succeeding the key k in the map m, in Ord.compare order.

If k is the first key in m (i.e. would be returned by min_binding), then prev is None. Likewise, if k is the last key in the map (i.e. would be returned by max_binding), then next is None.

Otherwise, prev and next are of the form (Some (k',v)), where (k',v) is the appropriate binding.

val prev : Ord.t -> 'a t -> (key * 'a) Option.t

(prev k m) is (neighbors k m |> fst), the binding prior to k in map m.

val prev_key : Ord.t -> 'a t -> key option

(prev_key k m) is just the key part of the binding prior to k in map m.

val next : Ord.t -> 'a t -> (key * 'a) Option.t

(next k m) is (neighbors k m |> snd), the binding succeding k in map m.

val next_key : Ord.t -> 'a t -> 'a option

(next_key k m) is just the key part of the binding succeeding k in map m.

Extracting Data from the Map

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

to_list is bindings.

val keys : 'a t -> key list

(keys m) is the keys in the map m as a list, in Ord.compare key-order.

val values : 'a t -> 'a list

(values m) is the values in the map m as a list, in Ord.compare key-order (not value-order).