Module Base.Hashtbl

Hash tables, mutable lookup-tables supporting constant-time lookup and in-place modification.

val hash : 'a ‑> int
val hash_param : int ‑> int ‑> 'a ‑> int
type ('a, 'b) t

We use [@@deriving_inline sexp_of][@@@end] but not [@@deriving sexp] because we want people to be explicit about the hash and comparison functions used when creating hashtables. One can use Hashtbl.Poly.t, which does have [@@deriving_inline sexp][@@@end], to use polymorphic comparison and hashing.

include sig ... end
val sexp_of_t : ('a ‑> Sexp.t) ‑> ('b ‑> Sexp.t) ‑> ('a, 'b) t ‑> Sexp.t
include Invariant.S2 with type (a, b) t := (a, b) t
type ('a, 'b) t
include Base__.Hashtbl_intf.Creators with type (a, b) t := (a, b) t
type ('a, 'b) t
val create : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> ('a, 'b) t
val of_alist : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> ('a * 'b) list ‑> [ `Ok of ('a, 'b) t | `Duplicate_key of 'a ]
val of_alist_report_all_dups : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> ('a * 'b) list ‑> [ `Ok of ('a, 'b) t | `Duplicate_keys of 'a list ]
val of_alist_or_error : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> ('a * 'b) list ‑> ('a, 'b) t Or_error.t
val of_alist_exn : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> ('a * 'b) list ‑> ('a, 'b) t
val of_alist_multi : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> ('a * 'b) list ‑> ('a, 'b list) t
val create_mapped : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> get_key:('r ‑> 'a) ‑> get_data:('r ‑> 'b) ‑> 'r list ‑> [ `Ok of ('a, 'b) t | `Duplicate_keys of 'a list ]
create_mapped get_key get_data [x1,...,xn]
         = of_alist [get_key x1, get_data x1; ...; get_key xn, get_data xn]
val create_with_key : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> get_key:('r ‑> 'a) ‑> 'r list ‑> [ `Ok of ('a, 'r) t | `Duplicate_keys of 'a list ]
create_with_key ~get_key [x1,...,xn]
         = of_alist [get_key x1, x1; ...; get_key xn, xn]
val create_with_key_or_error : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> get_key:('r ‑> 'a) ‑> 'r list ‑> ('a, 'r) t Or_error.t
val create_with_key_exn : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> get_key:('r ‑> 'a) ‑> 'r list ‑> ('a, 'r) t
val group : ?⁠growth_allowed:bool ‑> ?⁠size:int ‑> (module Base__.Hashtbl_intf.Key with type t = 'a) ‑> get_key:('r ‑> 'a) ‑> get_data:('r ‑> 'b) ‑> combine:('b ‑> 'b ‑> 'b) ‑> 'r list ‑> ('a, 'b) t
include Base__.Hashtbl_intf.Accessors with type (a, b) t := (a, b) t with type 'a key = 'a
type ('a, 'b) t
type 'a key = 'a
val sexp_of_key : ('a, _) t ‑> 'a key ‑> Sexp.t
val clear : (_, _) t ‑> unit
val copy : ('a, 'b) t ‑> ('a, 'b) t
val fold : ('a, 'b) t ‑> init:'c ‑> f:(key:'a key ‑> data:'b ‑> 'c ‑> 'c) ‑> 'c

Attempting to modify (set, remove, etc.) the hashtable during iteration (fold, iter, iter_keys, iteri) will raise an exception.

val iter_keys : ('a, _) t ‑> f:('a key ‑> unit) ‑> unit
val iter : (_, 'b) t ‑> f:('b ‑> unit) ‑> unit
val iteri : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> unit) ‑> unit
val existsi : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> bool) ‑> bool
val exists : (_, 'b) t ‑> f:('b ‑> bool) ‑> bool
val for_alli : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> bool) ‑> bool
val for_all : (_, 'b) t ‑> f:('b ‑> bool) ‑> bool
val counti : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> bool) ‑> int
val count : (_, 'b) t ‑> f:('b ‑> bool) ‑> int
val length : (_, _) t ‑> int
val is_empty : (_, _) t ‑> bool
val mem : ('a, _) t ‑> 'a key ‑> bool
val remove : ('a, _) t ‑> 'a key ‑> unit
val set : ('a, 'b) t ‑> key:'a key ‑> data:'b ‑> unit
val add : ('a, 'b) t ‑> key:'a key ‑> data:'b ‑> [ `Ok | `Duplicate ]

add and add_exn leave the table unchanged if the key was already present.

val add_exn : ('a, 'b) t ‑> key:'a key ‑> data:'b ‑> unit
val change : ('a, 'b) t ‑> 'a key ‑> f:('b option ‑> 'b option) ‑> unit

change t key ~f changes t's value for key to be f (find t key).

val update : ('a, 'b) t ‑> 'a key ‑> f:('b option ‑> 'b) ‑> unit

update t key ~f is change t key ~f:(fun o -> Some (f o)).

val map : ('a, 'b) t ‑> f:('b ‑> 'c) ‑> ('a, 'c) t

map t f returns new table with bound values replaced by f applied to the bound values

val mapi : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> 'c) ‑> ('a, 'c) t

like map, but function takes both key and data as arguments

val filter_map : ('a, 'b) t ‑> f:('b ‑> 'c option) ‑> ('a, 'c) t

returns new table with bound values filtered by f applied to the bound values

val filter_mapi : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> 'c option) ‑> ('a, 'c) t

like filter_map, but function takes both key and data as arguments

val filter_keys : ('a, 'b) t ‑> f:('a key ‑> bool) ‑> ('a, 'b) t
val filter : ('a, 'b) t ‑> f:('b ‑> bool) ‑> ('a, 'b) t
val filteri : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> bool) ‑> ('a, 'b) t
val partition_map : ('a, 'b) t ‑> f:('b ‑> [ `Fst of 'c | `Snd of 'd ]) ‑> ('a, 'c) t * ('a, 'd) t

returns new tables with bound values partitioned by f applied to the bound values

val partition_mapi : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> [ `Fst of 'c | `Snd of 'd ]) ‑> ('a, 'c) t * ('a, 'd) t

like partition_map, but function takes both key and data as arguments

val partition_tf : ('a, 'b) t ‑> f:('b ‑> bool) ‑> ('a, 'b) t * ('a, 'b) t

returns a pair of tables (t1, t2), where t1 contains all the elements of the initial table which satisfy the predicate f, and t2 contains all the elements which do not satisfy f.

val partitioni_tf : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> bool) ‑> ('a, 'b) t * ('a, 'b) t

like partition_tf, but function takes both key and data as arguments

val find_or_add : ('a, 'b) t ‑> 'a key ‑> default:(unit ‑> 'b) ‑> 'b

find_or_add t k ~default returns the data associated with key k if it is in the table t, otherwise it lets d = default() and adds it to the table.

val findi_or_add : ('a, 'b) t ‑> 'a key ‑> default:('a key ‑> 'b) ‑> 'b

like find_or_add but default takes the key as an argument.

val find : ('a, 'b) t ‑> 'a key ‑> 'b option

find t k returns Some (the current binding) of k in t, or None if no such binding exists

val find_exn : ('a, 'b) t ‑> 'a key ‑> 'b

find_exn t k returns the current binding of k in t, or raises Caml.Not_found or Not_found_s if no such binding exists.

val find_and_call : ('a, 'b) t ‑> 'a key ‑> if_found:('b ‑> 'c) ‑> if_not_found:('a key ‑> 'c) ‑> 'c

find_and_call t k ~if_found ~if_not_found

is equivalent to:

match find t k with Some v -> if_found v | None -> if_not_found k

except that it doesn't allocate the option.

val findi_and_call : ('a, 'b) t ‑> 'a key ‑> if_found:(key:'a key ‑> data:'b ‑> 'c) ‑> if_not_found:('a key ‑> 'c) ‑> 'c
val find_and_remove : ('a, 'b) t ‑> 'a key ‑> 'b option

find_and_remove t k returns Some (the current binding) of k in t and removes it, or None is no such binding exists

val merge : ('k, 'a) t ‑> ('k, 'b) t ‑> f:(key:'k key ‑> [ `Left of 'a | `Right of 'b | `Both of 'a * 'b ] ‑> 'c option) ‑> ('k, 'c) t

Merge two hashtables.

The result of merge f h1 h2 has as keys the set of all k in the union of the sets of keys of h1 and h2 for which d(k) is not None, where:

d(k) =

  • f ~key:k (Some d1) None if k in h1 is to d1, and h2 does not map k;
  • f ~key:k None (Some d2) if k in h2 is to d2, and h1 does not map k;
  • f ~key:k (Some d1) (Some d2) otherwise, where k in h1 is to d1 and k in h2 is to d2.

Each key k is mapped to a single piece of data x, where d(k) = Some x.

type 'a merge_into_action =
| Remove
| Set_to of 'a

Every key in src will be removed or set in dst according to the return value of f.

val merge_into : src:('k, 'a) t ‑> dst:('k, 'b) t ‑> f:(key:'k key ‑> 'a ‑> 'b option ‑> 'b merge_into_action) ‑> unit
val keys : ('a, _) t ‑> 'a key list

Returns the list of all keys for given hashtable.

val data : (_, 'b) t ‑> 'b list

Returns the list of all data for given hashtable.

val filter_keys_inplace : ('a, _) t ‑> f:('a key ‑> bool) ‑> unit

filter_inplace t ~f removes all the elements from t that don't satisfy f.

val filter_inplace : (_, 'b) t ‑> f:('b ‑> bool) ‑> unit
val filteri_inplace : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> bool) ‑> unit
val map_inplace : (_, 'b) t ‑> f:('b ‑> 'b) ‑> unit

map_inplace t ~f applies f to all elements in t, transforming them in place

val mapi_inplace : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> 'b) ‑> unit
val filter_map_inplace : (_, 'b) t ‑> f:('b ‑> 'b option) ‑> unit

filter_map_inplace combines the effects of map_inplace and filter_inplace

val filter_mapi_inplace : ('a, 'b) t ‑> f:(key:'a key ‑> data:'b ‑> 'b option) ‑> unit
val equal : ('a, 'b) t ‑> ('a, 'b) t ‑> ('b ‑> 'b ‑> bool) ‑> bool

equal t1 t2 f and similar t1 t2 f both return true iff t1 and t2 have the same keys and for all keys k, f (find_exn t1 k) (find_exn t2 k). equal and similar only differ in their types.

val similar : ('a, 'b1) t ‑> ('a, 'b2) t ‑> ('b1 ‑> 'b2 ‑> bool) ‑> bool
val to_alist : ('a, 'b) t ‑> ('a key * 'b) list

Returns the list of all (key,data) pairs for given hashtable.

val validate : name:('a key ‑> string) ‑> 'b Validate.check ‑> ('a, 'b) t Validate.check
val incr : ?⁠by:int ‑> ?⁠remove_if_zero:bool ‑> ('a, int) t ‑> 'a key ‑> unit

remove_if_zero's default is false.

val decr : ?⁠by:int ‑> ?⁠remove_if_zero:bool ‑> ('a, int) t ‑> 'a key ‑> unit
include Base__.Hashtbl_intf.Multi with type (a, b) t := (a, b) t with type a key := a key
type ('a, 'b) t
type 'a key
val add_multi : ('a, 'b list) t ‑> key:'a key ‑> data:'b ‑> unit

add_multi t ~key ~data if key is present in the table then cons data on the list, otherwise add key with a single element list.

val remove_multi : ('a, _ list) t ‑> 'a key ‑> unit

remove_multi t key updates the table, removing the head of the list bound to key. If the list has only one element (or is empty) then the binding is removed.

val find_multi : ('a, 'b list) t ‑> 'a key ‑> 'b list

find_multi t key returns the empty list if key is not present in the table, returns t's values for key otherwise

val hashable_s : ('key, _) t ‑> (module Base__.Hashtbl_intf.Key with type t = 'key)
module type Accessors = Base__.Hashtbl_intf.Accessors
module type Creators = Base__.Hashtbl_intf.Creators
module type Key = Base__.Hashtbl_intf.Key
module type Multi = Base__.Hashtbl_intf.Multi
module type S_poly = Base__.Hashtbl_intf.S_poly
module type S_without_submodules = Base__.Hashtbl_intf.S_without_submodules
type ('key, 'data, 'z) create_options = ('key, 'data, 'z) Base__.Hashtbl_intf.create_options
module Creators : functor (Key : sig ... end) -> sig ... end
module Poly : S_poly with type ('a, 'b) t = ('a, 'b) t
module M : functor (K : T.T) -> sig ... end

M is meant to be used in combination with OCaml applicative functor types:

module type Sexp_of_m : sig ... end
module type M_of_sexp : sig ... end
val sexp_of_m__t : (module Sexp_of_m with type t = 'k) ‑> ('v ‑> Sexp.t) ‑> ('k, 'v) t ‑> Sexp.t
val m__t_of_sexp : (module M_of_sexp with type t = 'k) ‑> (Sexp.t ‑> 'v) ‑> Sexp.t ‑> ('k, 'v) t