Map(3) OCaml library Map(3)
NAME
Map - Association tables over ordered types.
Module
Module Map
Documentation
Module Map
: sig end
Association tables over ordered types.
This module implements applicative association tables, also known as finite maps or dictionaries, given a total ordering function over the
keys. All operations over maps are purely applicative (no side-effects). The implementation uses balanced binary trees, and therefore
searching and insertion take time logarithmic in the size of the map.
module type OrderedType = sig end
Input signature of the functor Map.Make .
module type S = sig end
Output signature of the functor Map.Make .
module Make : functor (Ord : OrderedType) -> sig end
Functor building an implementation of the map structure given a totally ordered type.
OCamldoc 2014-06-09 Map(3)
Check Out this Related Man Page
Hashtbl(3o) OCaml library Hashtbl(3o)
NAME
Hashtbl - Hash tables and hash functions.
Module
Module Hashtbl
Documentation
Module Hashtbl
: sig end
Hash tables and hash functions.
Hash tables are hashed association tables, with in-place modification.
=== Generic interface ===
type ('a, 'b) t
The type of hash tables from type 'a to type 'b .
val create : int -> ('a, 'b) t
Hashtbl.create n creates a new, empty hash table, with initial size n . For best results, n should be on the order of the expected number
of elements that will be in the table. The table grows as needed, so n is just an initial guess.
val clear : ('a, 'b) t -> unit
Empty a hash table.
val add : ('a, 'b) t -> 'a -> 'b -> unit
Hashtbl.add tbl x y adds a binding of x to y in table tbl . Previous bindings for x are not removed, but simply hidden. That is, after
performing Hashtbl.remove tbl x , the previous binding for x , if any, is restored. (Same behavior as with association lists.)
val copy : ('a, 'b) t -> ('a, 'b) t
Return a copy of the given hashtable.
val find : ('a, 'b) t -> 'a -> 'b
Hashtbl.find tbl x returns the current binding of x in tbl , or raises Not_found if no such binding exists.
val find_all : ('a, 'b) t -> 'a -> 'b list
Hashtbl.find_all tbl x returns the list of all data associated with x in tbl . The current binding is returned first, then the previous
bindings, in reverse order of introduction in the table.
val mem : ('a, 'b) t -> 'a -> bool
Hashtbl.mem tbl x checks if x is bound in tbl .
val remove : ('a, 'b) t -> 'a -> unit
Hashtbl.remove tbl x removes the current binding of x in tbl , restoring the previous binding if it exists. It does nothing if x is not
bound in tbl .
val replace : ('a, 'b) t -> 'a -> 'b -> unit
Hashtbl.replace tbl x y replaces the current binding of x in tbl by a binding of x to y . If x is unbound in tbl , a binding of x to y is
added to tbl . This is functionally equivalent to Hashtbl.remove tbl x followed by Hashtbl.add tbl x y .
val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
Hashtbl.iter f tbl applies f to all bindings in table tbl . f receives the key as first argument, and the associated value as second argu-
ment. Each binding is presented exactly once to f . The order in which the bindings are passed to f is unspecified. However, if the table
contains several bindings for the same key, they are passed to f in reverse order of introduction, that is, the most recent binding is
passed first.
val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
Hashtbl.fold f tbl init computes (f kN dN ... (f k1 d1 init)...) , where k1 ... kN are the keys of all bindings in tbl , and d1 ... dN are
the associated values. Each binding is presented exactly once to f . The order in which the bindings are passed to f is unspecified.
However, if the table contains several bindings for the same key, they are passed to f in reverse order of introduction, that is, the most
recent binding is passed first.
val length : ('a, 'b) t -> int
Hashtbl.length tbl returns the number of bindings in tbl . Multiple bindings are counted multiply, so Hashtbl.length gives the number of
times Hashtbl.iter calls its first argument.
=== Functorial interface ===
module type HashedType = sig end
The input signature of the functor Hashtbl.Make .
module type S = sig end
The output signature of the functor Hashtbl.Make .
module Make : functor (H : HashedType) -> sig end
Functor building an implementation of the hashtable structure. The functor Hashtbl.Make returns a structure containing a type key of keys
and a type 'a t of hash tables associating data of type 'a to keys of type key . The operations perform similarly to those of the generic
interface, but use the hashing and equality functions specified in the functor argument H instead of generic equality and hashing.
=== The polymorphic hash primitive ===
val hash : 'a -> int
Hashtbl.hash x associates a positive integer to any value of any type. It is guaranteed that if x = y or Pervasives.compare x y = 0 , then
hash x = hash y . Moreover, hash always terminates, even on cyclic structures.
val hash_param : int -> int -> 'a -> int
Hashtbl.hash_param n m x computes a hash value for x , with the same properties as for hash . The two extra parameters n and m give more
precise control over hashing. Hashing performs a depth-first, right-to-left traversal of the structure x , stopping after n meaningful
nodes were encountered, or m nodes, meaningful or not, were encountered. Meaningful nodes are: integers; floating-point numbers; strings;
characters; booleans; and constant constructors. Larger values of m and n means that more nodes are taken into account to compute the final
hash value, and therefore collisions are less likely to happen. However, hashing takes longer. The parameters m and n govern the tradeoff
between accuracy and speed.
OCamldoc 2012-06-26 Hashtbl(3o)