alice
library
manual.
signature IMP_MAP
functor MkHashImpMap (Key : HASHABLE) :> IMP_MAP where type key = Key.t
functor MkRedBlackImpMap (Key : ORDERED) :> IMP_MAP where type key = Key.t
The MAP signature provides an imperative interface to finite maps. The MkHashImpMap functor provides an implementation of this interface based on hash tables, while the MkRedBlackImpMap functor provides an implementation based on red-black trees.
Note that imperative maps are not thread-safe. Explicit locking has to be used if they need to be accessed concurrently. Also note that the behaviour of iterator functionals is unspecified if the passed argument function tries to modify the map.
See also: RefMap, MAP, IMP_SET, HASHABLE, ORDERED
import signature IMP_MAP from "x-alice:/lib/data/IMP_MAP-sig"
import functor MkHashImpMap from "x-alice:/lib/data/MkHashImpMap"
import functor MkRedBlackImpMap from "x-alice:/lib/data/MkRedBlackImpMap"
signature IMP_MAP =
sig
type key
eqtype 'a map
type 'a t = 'a map
exception Unknown of key
exception Collision of key
val map : unit -> 'a map
val clone : 'a map -> 'a map
val fromList : (key * 'a) list -> 'a map
val fromVector : (key * 'a) vector -> 'a map
val toList : 'a map -> (key * 'a) list
val toVector : 'a map -> (key * 'a) vector
val insert : 'a map * key * 'a -> unit
val insertDisjoint : 'a map * key * 'a -> unit
val insertWith : ('a * 'a -> 'a) -> 'a map * key * 'a -> unit
val insertWithi : (key * 'a * 'a -> 'a) -> 'a map * key * 'a -> unit
val remove : 'a map * key -> unit
val removeExistent : 'a map * key -> unit
val removeWith : (key -> unit) -> 'a map * key -> unit
val removeAll : 'a map -> unit
val union : 'a map * 'a map -> unit
val unionDisjoint : 'a map * 'a map -> unit
val unionWith : ('a * 'a -> 'a) -> 'a map * 'a map -> unit
val unionWithi : (key * 'a * 'a -> 'a) -> 'a map * 'a map -> unit
val intersect : 'a map * 'a map -> unit
val intersectWith : ('a * 'a -> 'a) -> 'a map * 'a map -> unit
val intersectWithi : (key * 'a * 'a -> 'a) -> 'a map * 'a map -> unit
val difference : 'a map * 'a map -> unit
val size : 'a map -> int
val isEmpty : 'a map -> bool
val member : 'a map * key -> bool
val lookup : 'a map * key -> 'a option
val lookupExistent : 'a map * key -> 'a
val choose : 'a map -> 'a option
val choosei : 'a map -> (key * 'a) option
val equal : ('a * 'a -> bool) -> 'a map * 'a map -> bool
val submap : ('a * 'a -> bool) -> 'a map * 'a map -> bool
val disjoint : 'a map * 'a map -> bool
val app : ('a -> unit) -> 'a map -> unit
val modify : ('a -> 'a) -> 'a map -> unit
val fold : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
val all : ('a -> bool) -> 'a map -> bool
val exists : ('a -> bool) -> 'a map -> bool
val find : ('a -> bool) -> 'a map -> 'a option
val filter : ('a -> bool) -> 'a map -> unit
val appi : (key * 'a -> unit) -> 'a map -> unit
val modifyi : (key * 'a -> 'a) -> 'a map -> unit
val foldi : (key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
val alli : (key * 'a -> bool) -> 'a map -> bool
val existsi : (key * 'a -> bool) -> 'a map -> bool
val findi : (key * 'a -> bool) -> 'a map -> (key * 'a) option
val filteri : (key * 'a -> bool) -> 'a map -> unit
end
The type of keys.
The type of finite maps from keys of type key to values of type 'a. Only maps created by the same function application are equal. Like ref and array, the map type always admits equality, independently from its argument.
Indicates that a key could not be found in the map.
Indicates an attempt to add a key that already is in the map when using functions that disallow replacement.
Creates an empty map.
Creates a copy of the map m.
Constructs a map from a list of key/value pairs. Raises Collision k is a key in the list that is followed by at least one other key equal to k.
Constructs a map from a vector of key/value pairs. Raises Collision k if k is a key in the vector that is followed by at least one other entry with a key equal to k. Equivalent to fromList(Vector.toList v).
Returns the list of key/value pairs from map m. For red-black maps, the pairs are delivered in increasing key order.
Returns the vector of key/value pairs from map m. For red-black maps, the pairs are delivered in increasing key order. Equivalent to Vector.fromList(toList m).
Extends the map m with the entry k->x. In the first form, if m already contains a key k' equal to k, then the corresponding entry gets replaced by k->x. In the second form, Collision k' will be raised. In the third form, the entry is replaced by k->f(x', x), where x' is the value k' maps to. In the forth form, k' is additionally passed to f. The following equivalences hold:
insert = insertWith #2
insertDisjoint = insertWithi (fn (k,_,_) => raise Collision k)
insertWith f = insertWithi (fn (_,x,y) => f(x, y))
Removes the entry corresponding to key k from the map m. In the first form, if no key equal to k is contained in m, then the map is left unchanged. In the second form, Unknown k will be raised. In the third form, f is applied to k before the map is modified. The following equivalences hold:
remove = removeWith ignore
removeExistent = removeWith (fn k => raise Unknown k)
Removes all entries from the map m.
Inserts all entries from map m2 into map m1. In the first form, if m1 and m2 contain entries k1->x1 and k2->x2 with equal keys k1 and k2, respectively, then the entry in m1 will get replaced by k2->x2. In the second form, Collision k2 will be raised. In the third form, the entry will get replaced by k2->f(x1,x2). In the forth form, k2 is additionally passed to f. The following equivalences hold:
union = unionWith #2
unionDisjoint = unionWithi (fn (k,_,_) => raise Collision k)
unionWith f = unionWithi (fn (_,x,y) => f(x, y))
Removes all entries k1->x1 from map m1 for which no key k2 equal to k1 is not in the domain of m2. In the first form, if m2 contains a corresponding entry k2->x2, respectively, then the entry in m1 will get replaced by k2->x2. In the second form, the entry will get replaced by k2->f(x1,x2). In the third form, k2 is additionally passed to f. The following equivalences hold:
intersect = intersectWith #2
intersectWith f = intersectWithi (fn (_,x,y) => f(x, y))
Removes all entries k1->x1 from map m1 for which a key k2 equal to k1 is in the domain of m2.
Returns the cardinality of the map m, i.e. the number of entries it contains.
Returns true if m is an empty map, false otherwise. Equivalent to size m = 0.
Returns true if the map m contains a key equal to k, false otherwise.
In the first form, returns SOME x if the map m contains an entry k'->x, where key k' is equal to k, NONE otherwise. In the second form, returns x unwrapped, or raises Unknown k if no such entry exists.
In the first form, returns SOME x, such that k->x is an entry of the map m. In the second form, returns SOME(k,x). Returns NONE if m is the empty map. For red-black maps, k will be the smallest key in the map.
Returns true if m1 and m2 are maps with equal entries, false otherwise. Two entries k1->x1 and k2->x2 are considered equal if Key.equal(k1, k2) andalso f(x1, x2) evaluates to true.
Returns true if m1 contains an entry k1->x1 for every entry k2->x2 in m2, such that Key.equal(k1, k2) andalso f(x1, x2) evaluates to true.
Returns true if m1 and m2 are maps with disjoint domains, false otherwise.
In the second form, applies f to each entry in the map m. In the first form, applies f to the value in the entry only. For red-black trees, this happens in increasing order. The following equivalences hold:
app f m = appi (f o #2) m
appi f m = List.app f (toList m)
In the second form, modifies the map by replacing each entry k->x by k->f(k, x). In the first form, only x is passed to f. For red-black trees, f is applied in order of increasing keys. The following equivalences hold:
modify f m = modifyi (f o #2) m
modifyi f m = List.app (fn (k, x) => insert(k, f (k, x))) (toList m)
In the second form, sequentially applies f to the triple of each map entry's key and value and the result of the previous application, starting with initial value a. In the first form, only an entry's value and the previous result are passed to f. For red-black trees, folding is performed in increasing order. The following equivalences hold:
fold f a m = fold (fn (_,x,y) => f (x,y)) a m
foldi f a m = List.foldl f a (toList m)
In the second form, applies f to each entry (k, x) of map ms until f(k, x) delivers false. Returns false if such an entry exists, true otherwise. In the first form, only x is passed to f. For red-black trees, f is applied in increasing order. The following equivalences hold:
all f m = alli (f o #2) m
alli f m = List.all f (toList m)
In the second form, applies f to each entry (k, x) of map ms until f(k, x) delivers true. Returns true if such an entry exists, false otherwise. In the first form, only x is passed to f. For red-black trees, f is applied in increasing order. The following equivalences hold:
exists f m = existsi (f o #2) m
existsi f m = List.exists f (toList m)
In the second form, applies f to each entry (k, x) of map m until f(k, x) delivers true. Returns SOME(k, x) if such an entry exists, NONE otherwise. In the first form, only x is passed to f, and on success SOME x is returned. For red-black trees, f is applied in increasing order. The following equivalences hold:
find f m = Option.map #2 (findi (f o #2) m)
findi f m = List.find f (toList m)
In the second form, applies f to each entry (k, x) of map m and removes all entries from the map for which f(k, x) delivered false. In the first form, only x is passed to f. For red-black trees, f is applied in increasing order. The following equivalences hold:
filter f m = filteri (f o #2) m
filteri f m = fromList (List.filter f (toList m))