Finite maps.
The FMap module provides a purely functional finite map datastructure based on balanced binary trees. Most operations on single elements, for example adding bindings or testing membership, can be performed in time logarithmic in the size of the map.
This module provides a superset of the operations in the Map module in the OCaml standard library, but with a polymorphic interface in addition to the standard functorial interface.
A map provided by this module requires a strict order on its domain elements. When using the polymorphic interface, domain elements are compared using the structural comparison operators (=) and (<). For this reason, the polymorphic interface can only be used if semantic equality in the domain type is equivalent to structural equality.
The type of finite maps with domain type 'a and range type 'b. Values of this type can be considered as finite sets of pairs where an element (x, y) represents the mapping of x to y. The domain of a map m is the set of values x such that m contains a pair (x, y) for some y (m maps x to some value); the range of m is the set of values y such that m contains a pair (x, y) for some x (some value is mapped to y by m).
val size : ('a, 'b) t -> intReturns the size of the domain of a map.
equal cmp m1 m2 tests whether the maps m1 and m2 are equal. Two maps are equal if they have equal domains and map each domain element to equal values, where the values are compared using cmp.
compare cmp returns a total ordering on maps using cmp to compare values.
val empty : ('a, 'b) tThe empty map.
add x y m returns a map that maps x to y and all other elements to the values they are mapped to by m.
remove x m returns a map that is undefined at x and maps all other elements to the values they are mapped to by m.
val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unititer f m applies f to all pairs x and y, where (x, y) is an element of m. The elements of m are processed in increasing domain order.
val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'cfold f m a returns (f xn yn ... (f x2 y2 (f x1 y1 a)) ... ), where (x1, y1), ..., (xn, yn) are the elements of m in increasing domain order.
val rev_fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'cfold f m a returns (f x1 y1 (f x2 y2 ... (f xn yn a)) ... ), where (x1, y1), ..., (xn, yn) are the elements of m in increasing domain order.
map f m returns a map that has the same domain as m and maps all elements x in its domain to f (find x m).
mapi f m returns a map that has the same domain as m and maps all elements x in its domain to f x (find x m).
val is_empty : ('a, 'b) t -> boolTests whether a map has an empty domain.
val for_all : ('a -> 'b -> bool) -> ('a, 'b) t -> boolfor_all p m returns true if p x y = true for all elements (x, y) of m, and false otherwise.
val exists : ('a -> 'b -> bool) -> ('a, 'b) t -> boolfor_all p m returns true if p x y = true some element (x, y) of m, and false otherwise.
val mem : 'a -> ('a, 'b) t -> boolmem x m tests whether m is defined at x.
val is_defined : 'a -> ('a, 'b) t -> boolis_defined x m tests whether m is defined at x (the same as mem).
val find : 'a -> ('a, 'b) t -> 'bfind x m returns the value x is mapped to by m.
val apply : ('a, 'b) t -> 'a -> 'bapply m x returns the value x is mapped to by m (the same as find).
val to_list : ('a, 'b) t -> ('a * 'b) listReturns an association list containing all element of the map in increasing order of the domain elements.
val of_list : ('a * 'b) list -> ('a, 'b) tCreates a map from an association list.
module type OrderedType = sig ... endInput signature of the functor FSet.Make.