Module Base.HashtblSource
A hash table is a mutable data structure implementing a map between keys and values. It supports constant-time lookup and in-place modification.
Usage
As a simple example, we'll create a hash table with string keys using the create constructor, which expects a module defining the key's type:
let h = Hashtbl.create (module String);;
val h : (string, '_a) Hashtbl.t = <abstr>
We can set the values of individual keys with set. If the key already has a value, it will be overwritten.
Hashtbl.set h ~key:"foo" ~data:5;;
- : unit = ()
Hashtbl.set h ~key:"foo" ~data:6;;
- : unit = ()
Hashtbl.set h ~key:"bar" ~data:6;;
- : unit = ()
We can access values by key, or dump all of the hash table's data:
Hashtbl.find h "foo";;
- : int option = Some 6
Hashtbl.find_exn h "foo";;
- : int = 6
Hashtbl.to_alist h;;
- : (string * int) list = [("foo", 6); ("bar", 6)]change lets us change a key's value by applying the given function:
Hashtbl.change h "foo" (fun x ->
match x with
| Some x -> Some (x * 2)
| None -> None
);;
- : unit = ()
Hashtbl.to_alist h;;
- : (string * int) list = [("foo", 12); ("bar", 6)]We can use merge to merge two hashtables with fine-grained control over how we choose values when a key is present in the first ("left") hashtable, the second ("right"), or both. Here, we'll cons the values when both hashtables have a key:
let h1 = Hashtbl.of_alist_exn (module Int) [(1, 5); (2, 3232)] in
let h2 = Hashtbl.of_alist_exn (module Int) [(1, 3)] in
Hashtbl.merge h1 h2 ~f:(fun ~key:_ -> function
| `Left x -> Some (`Left x)
| `Right x -> Some (`Right x)
| `Both (x, y) -> if x=y then None else Some (`Both (x,y))
) |> Hashtbl.to_alist;;
- : (int * [> `Both of int * int | `Left of int | `Right of int ]) list =
[(2, `Left 3232); (1, `Both (5, 3))]
Interface
Sourceval hash_param : int -> int -> 'a -> int We provide a sexp_of_t but not a t_of_sexp for this type because one needs to be explicit about the hash and comparison functions used when creating a hashtable. Note that Hashtbl.Poly.t does have [@@deriving sexp], and uses OCaml's built-in polymorphic comparison and and polymorphic hashing.
Creators
Sourceval create :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
('a, 'b) t The module you pass to create must have a type that is hashable, sexpable, and comparable.
Example:
Hashtbl.create (module Int);;
- : (int, '_a) Hashtbl.t = <abstr>;;
Sourceval of_alist :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
('a * 'b) list ->
[ `Ok of ('a, 'b) t | `Duplicate_key of 'a ] Example:
Hashtbl.of_alist (module Int) [(3, "something"); (2, "whatever")]
- : [ `Duplicate_key of int | `Ok of (int, string) Hashtbl.t ] = `Ok <abstr>
Sourceval of_alist_report_all_dups :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
('a * 'b) list ->
[ `Ok of ('a, 'b) t | `Duplicate_keys of 'a list ] Whereas of_alist will report Duplicate_key no matter how many dups there are in your list, of_alist_report_all_dups will report each and every duplicate entry.
For example:
Hashtbl.of_alist (module Int) [(1, "foo"); (1, "bar"); (2, "foo"); (2, "bar")];;
- : [ `Duplicate_key of int | `Ok of (int, string) Hashtbl.t ] = `Duplicate_key 1
Hashtbl.of_alist_report_all_dups (module Int) [(1, "foo"); (1, "bar"); (2, "foo"); (2, "bar")];;
- : [ `Duplicate_keys of int list | `Ok of (int, string) Hashtbl.t ] = `Duplicate_keys [1; 2]
Sourceval of_alist_or_error :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
('a * 'b) list ->
('a, 'b) t Or_error.t Sourceval of_alist_exn :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
('a * 'b) list ->
('a, 'b) t Sourceval of_alist_multi :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
('a * 'b) list ->
('a, 'b list) t Creates a "multi" hashtable, i.e., a hashtable where each key points to a list potentially containing multiple values. So instead of short-circuiting with a `Duplicate_key variant on duplicates, as in of_alist, of_alist_multi folds those values into a list for the given key:
let h = Hashtbl.of_alist_multi (module Int) [(1, "a"); (1, "b"); (2, "c"); (2, "d")];;
val h : (int, string list) Hashtbl.t = <abstr>
Hashtbl.find_exn h 1;;
- : string list = ["b"; "a"]
Sourceval create_mapped :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
get_key:('r -> 'a) ->
get_data:('r -> 'b) ->
'r list ->
[ `Ok of ('a, 'b) t | `Duplicate_keys of 'a list ] Applies the get_key and get_data functions to the 'r list to create the initial keys and values, respectively, for the new hashtable.
create_mapped get_key get_data [x1;...;xn]
= of_alist [get_key x1, get_data x1; ...; get_key xn, get_data xn]
Example:
let h =
Hashtbl.create_mapped (module Int)
~get_key:(fun x -> x)
~get_data:(fun x -> x + 1)
[1; 2; 3];;
val h : [ `Duplicate_keys of int list | `Ok of (int, int) Hashtbl.t ] = `Ok <abstr>
let h =
match h with
| `Ok x -> x
| `Duplicate_keys _ -> failwith ""
in
Hashtbl.find_exn h 1;;
- : int = 2Sourceval create_with_key :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S 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]
Sourceval create_with_key_or_error :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
get_key:('r -> 'a) ->
'r list ->
('a, 'r) t Or_error.t Sourceval create_with_key_exn :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
get_key:('r -> 'a) ->
'r list ->
('a, 'r) t Sourceval group :
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'a) ->
get_key:('r -> 'a) ->
get_data:('r -> 'b) ->
combine:('b -> 'b -> 'b) ->
'r list ->
('a, 'b) t Like create_mapped, applies the get_key and get_data functions to the 'r list to create the initial keys and values, respectively, for the new hashtable -- and then, like add_multi, folds together values belonging to the same keys. Here, though, the function used for the folding is given by combine (instead of just being a cons).
Example:
Hashtbl.group (module Int)
~get_key:(fun x -> x / 2)
~get_data:(fun x -> x)
~combine:(fun x y -> x * y)
[ 1; 2; 3; 4]
|> Hashtbl.to_alist;;
- : (int * int) list = [(2, 4); (1, 6); (0, 1)]Accessors
Sourceval copy : ('a, 'b) t -> ('a, 'b) t Sourceval 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.
Sourceval iter_keys : ('a, _) t -> f:('a key -> unit) -> unit Sourceval iter : (_, 'b) t -> f:('b -> unit) -> unit Sourceval iteri : ('a, 'b) t -> f:(key:'a key -> data:'b -> unit) -> unit Iterates over both keys and values.
Example:
let h = Hashtbl.of_alist_exn (module Int) [(1, 4); (5, 6)] in
Hashtbl.iteri h ~f:(fun ~key ~data ->
print_endline (Printf.sprintf "%d-%d" key data));;
1-4
5-6
- : unit = ()
Sourceval existsi : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> bool Sourceval exists : (_, 'b) t -> f:('b -> bool) -> bool Sourceval for_alli : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> bool Sourceval for_all : (_, 'b) t -> f:('b -> bool) -> bool Sourceval counti : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> int Sourceval count : (_, 'b) t -> f:('b -> bool) -> int Sourceval is_empty : (_, _) t -> bool Sourceval choose : ('a, 'b) t -> ('a key * 'b) option Sourceval set : ('a, 'b) t -> key:'a key -> data:'b -> unit Sets the given key to data.
Sourceval 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.
Sourceval add_exn : ('a, 'b) t -> key:'a key -> data:'b -> unit Sourceval 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).
Sourceval 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)).
Sourceval map : ('a, 'b) t -> f:('b -> 'c) -> ('a, 'c) t map t f returns a new table with values replaced by the result of applying f to the current values.
Example:
let h = Hashtbl.of_alist_exn (module Int) [(1, 4); (5, 6)] in
let h' = Hashtbl.map h ~f:(fun x -> x * 2) in
Hashtbl.to_alist h';;
- : (int * int) list = [(5, 12); (1, 8)]
Sourceval mapi : ('a, 'b) t -> f:(key:'a key -> data:'b -> 'c) -> ('a, 'c) t Like map, but the function f takes both key and data as arguments.
Sourceval filter_map : ('a, 'b) t -> f:('b -> 'c option) -> ('a, 'c) t Returns a new table by filtering the given table's values by f: the keys for which f applied to the current value returns Some are kept, and those for which it returns None are discarded.
Example:
let h = Hashtbl.of_alist_exn (module Int) [(1, 4); (5, 6)] in
Hashtbl.filter_map h ~f:(fun x -> if x > 5 then Some x else None)
|> Hashtbl.to_alist;;
- : (int * int) list = [(5, 6)]
Sourceval filter_mapi :
('a, 'b) t ->
f:(key:'a key -> data:'b -> 'c option) ->
('a, 'c) t Like filter_map, but the function f takes both key and data as arguments.
Sourceval filter_keys : ('a, 'b) t -> f:('a key -> bool) -> ('a, 'b) t Sourceval filter : ('a, 'b) t -> f:('b -> bool) -> ('a, 'b) t Sourceval filteri : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> ('a, 'b) t Sourceval partition_map :
('a, 'b) t ->
f:('b -> ('c, 'd) Either.t) ->
('a, 'c) t * ('a, 'd) t Returns new tables with bound values partitioned by f applied to the bound values.
Sourceval partition_mapi :
('a, 'b) t ->
f:(key:'a key -> data:'b -> ('c, 'd) Either.t) ->
('a, 'c) t * ('a, 'd) t Like partition_map, but the function f takes both key and data as arguments.
Sourceval 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 the rest.
Sourceval partitioni_tf :
('a, 'b) t ->
f:(key:'a key -> data:'b -> bool) ->
('a, 'b) t * ('a, 'b) t Like partition_tf, but the function f takes both key and data as arguments.
Sourceval 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, and otherwise assigns k the value returned by default ().
Sourceval 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.
Sourceval 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.
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.
Sourceval 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.
Sourceval find_and_call1 :
('a, 'b) t ->
'a key ->
a:'d ->
if_found:('b -> 'd -> 'c) ->
if_not_found:('a key -> 'd -> 'c) ->
'c Just like find_and_call, but takes an extra argument which is passed to if_found and if_not_found, so that the client code can avoid allocating closures or using refs to pass this additional information. This function is only useful in code which tries to minimize heap allocation.
Sourceval find_and_call2 :
('a, 'b) t ->
'a key ->
a:'d ->
b:'e ->
if_found:('b -> 'd -> 'e -> 'c) ->
if_not_found:('a key -> 'd -> 'e -> 'c) ->
'c Sourceval findi_and_call :
('a, 'b) t ->
'a key ->
if_found:(key:'a key -> data:'b -> 'c) ->
if_not_found:('a key -> 'c) ->
'c Sourceval findi_and_call1 :
('a, 'b) t ->
'a key ->
a:'d ->
if_found:(key:'a key -> data:'b -> 'd -> 'c) ->
if_not_found:('a key -> 'd -> 'c) ->
'c Sourceval findi_and_call2 :
('a, 'b) t ->
'a key ->
a:'d ->
b:'e ->
if_found:(key:'a key -> data:'b -> 'd -> 'e -> 'c) ->
if_not_found:('a key -> 'd -> 'e -> 'c) ->
'c Sourceval 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.
Sourceval 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 Merges 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 (`Left d1) if k in h1 maps to d1, and h2 does not have data for k;
f ~key:k (`Right d2) if k in h2 maps to d2, and h1 does not have data for k;
f ~key:k (`Both (d1, d2)) otherwise, where k in h1 maps to d1 and k in h2 maps to d2.
Each key k is mapped to a single piece of data x, where d(k) = Some x.
Example:
let h1 = Hashtbl.of_alist_exn (module Int) [(1, 5); (2, 3232)] in
let h2 = Hashtbl.of_alist_exn (module Int) [(1, 3)] in
Hashtbl.merge h1 h2 ~f:(fun ~key:_ -> function
| `Left x -> Some (`Left x)
| `Right x -> Some (`Right x)
| `Both (x, y) -> if x=y then None else Some (`Both (x,y))
) |> Hashtbl.to_alist;;
- : (int * [> `Both of int * int | `Left of int | `Right of int ]) list =
[(2, `Left 3232); (1, `Both (5, 3))]
Sourceval merge_into :
src:('k, 'a) t ->
dst:('k, 'b) t ->
f:
(key:'k key ->
'a ->
'b option ->
'b Base__.Hashtbl_intf.Merge_into_action.t) ->
unit Every key in src will be removed or set in dst according to the return value of f.
Returns the list of all keys for given hashtable.
Sourceval data : (_, 'b) t -> 'b list Returns the list of all data for given hashtable.
Sourceval 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.
Sourceval filter_inplace : (_, 'b) t -> f:('b -> bool) -> unit Sourceval filteri_inplace : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> unit Sourceval map_inplace : (_, 'b) t -> f:('b -> 'b) -> unit map_inplace t ~f applies f to all elements in t, transforming them in place.
Sourceval mapi_inplace : ('a, 'b) t -> f:(key:'a key -> data:'b -> 'b) -> unit Sourceval filter_map_inplace : (_, 'b) t -> f:('b -> 'b option) -> unit filter_map_inplace combines the effects of map_inplace and filter_inplace.
Sourceval filter_mapi_inplace :
('a, 'b) t ->
f:(key:'a key -> data:'b -> 'b option) ->
unit Sourceval equal : ('b -> 'b -> bool) -> ('a, 'b) t -> ('a, 'b) t -> bool equal f t1 t2 and similar f t1 t2 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.
Sourceval similar : ('b1 -> 'b2 -> bool) -> ('a, 'b1) t -> ('a, 'b2) t -> bool Sourceval to_alist : ('a, 'b) t -> ('a key * 'b) list Returns the list of all (key, data) pairs for given hashtable.
Sourceval incr : ?by:int -> ?remove_if_zero:bool -> ('a, int) t -> 'a key -> unit remove_if_zero's default is false.
Sourceval decr : ?by:int -> ?remove_if_zero:bool -> ('a, int) t -> 'a key -> unit Sourceval 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.
Sourceval 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.
Sourceval 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.
Sourceval hashable_s :
('key, _) t ->
(module Base__.Hashtbl_intf.Key.S
with type t = 'key) include Invariant.S2 with type ('a, 'b) t := ('a, 'b) t
Sourceval invariant : ('a -> unit) -> ('b -> unit) -> ('a, 'b) t -> unit Sourcetype nonrec ('key, 'data, 'z) create_options =
?growth_allowed:bool ->
?size:int ->
(module Base__.Hashtbl_intf.Key.S with type t = 'key) ->
'z M is meant to be used in combination with OCaml applicative functor types: