signature IMP_SET functor MkHashImpSet (Item : HASHABLE) :> IMP_SET where type item = Item.t functor MkRedBlackImpSet (Item : ORDERED) :> IMP_SET where type item = Item.t
The SET signature provides an imperative interface to finite sets. The MkHashImpSet functor provides an implementation of this interface based on hash tables, while the MkRedBlackImpSet functor provides an implementation based on red-black trees.
Note that imperative sets 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 set.
See also: SET, IMP_MAP, HASHABLE, ORDERED
import signature IMP_SET from "x-alice:/lib/data/IMP_SET-sig" import functor MkHashImpSet from "x-alice:/lib/data/MkHashImpSet" import functor MkRedBlackImpSet from "x-alice:/lib/data/MkRedBlackImpSet"
signature IMP_SET = sig type item eqtype set type t = set exception Unknown of item exception Collision of item val set : unit -> set val clone : set -> set val fromList : item list -> set val fromVector : item vector -> set val toList : set -> item list val toVector : set -> item vector val insert : set * item -> unit val insertDisjoint : set * item -> unit val insertWith : (item -> unit) -> set * item -> unit val remove : set * item -> unit val removeExistent : set * item -> unit val removeWith : (item -> unit) -> set * item -> unit val removeAll : set -> unit val union : set * set -> unit val unionDisjoint : set * set -> unit val unionWith : (item -> unit) -> set * set -> unit val intersect : set * set -> unit val difference : set * set -> unit val size : set -> int val isEmpty : set -> bool val member : set * item -> bool val choose : set -> item option val equal : set * set -> bool val subset : set * set -> bool val disjoint : set * set -> bool val compare : set * set -> order val app : (item -> unit) -> set -> unit val fold : (item * 'a -> 'a) -> 'a -> set -> 'a val all : (item -> bool) -> set -> bool val exists : (item -> bool) -> set -> bool val find : (item -> bool) -> set -> item option val filter : (item -> bool) -> set -> unit end
The type of elements in the set.
The type of sets over elements of type item. Only sets created by the same function application are equal.
Indicates that an item could not be found in the set.
Indicates an attempt to add an item that already is in the set when using functions that disallow replacement.
Creates an empty set.
Creates a copy of the set s.
Creates a set containing the elements from list l. Raises Collision x if x is an element in the list that is followed by at least one other element equal to x.
Creates a set containing the elements from list v. Raises Collision x if x is an element of the vector that is followed by at least one other element equal to x. Equivalent to fromList(Vector.toList v).
Returns the list of items in the set s. For red-black sets, the items are delivered in increasing order.
Returns the vector of items in the set s. For red-black sets, the items are delivered in increasing order. Equivalent to Vector.fromList(toList s).
Extends the set s with element x. In the first form, if s already contains an element y equal to x, then it gets replaced by x. In the second form, Collision y will be raised. In the third form, f is applied to y before the set is modified. The following equivalences hold:
insert = insertWith ignore insertDisjoint = insertWith (fn y => raise Collision y)
Removes the element x from the set s. In the first form, if no element equal to x is contained in s, then the set is left unchanged. In the second form, Unknown x will be raised. In the third form, f is applied to x before the set is modified. The following equivalences hold:
remove = removeWith ignore removeExistent = removeWith (fn y => raise Unknown y)
Removes all elements from the set s.
Inserts all elements from set s2 into s1. In the first form, if s2 contains an element x2 equal to an element x1 in set s1, then it will get replaced by x2. In the second form, Collision x2 will be raised. In the third form, f is applied to x2 before the set is modified as in the first form. The following equivalences hold:
union = unionWith ignore unionDisjoint = unionWith (fn y => raise Collision y)
Removes all elements from set s1 that are not contained in s2.
Removes all elements from set s1 that are contained in s2.
Returns the cardinality of the set s, i.e. the number of elements it contains.
Returns true if s is an empty set, false otherwise. Equivalent to size s = 0.
Returns true if the set s contains an element equal to x, false otherwise.
Returns SOME x, where x is an element of the set s. Returns NONE if s is empty. For red-black sets, x will be the smallest element in the set.
Returns true if s1 and s2 are sets with equal elements, false otherwise.
Returns true if s1 is a subset of s2, false otherwise.
Returns true if s1 and s2 are disjoint sets, false otherwise.
Returns EQUAL if s1 and s2 are equal sets, LESS if s1 is a subset of s2, and GREATER if s2 is a subset of s1. Otherwise it raises Unordered.
Applies f to each element in set s. For red-black trees, this happens in increasing order. Equivalent to List.app f (toList s).
Sequentially applies f to the pair of a set item and the result of the previous application, starting with initial value a. For red-black trees, folding is performed in increasing order. Equivalent to List.foldl f a (toList s).
Applies f to each element x of set s until f x delivers false. Returns false if such an x exists, true otherwise. For red-black trees, f is applied in increasing order. Equivalent to List.all f (toList s).
Applies f to each element x of set s until f x delivers true. Returns true if such an x exists, false otherwise. For red-black trees, f is applied in increasing order. Equivalent to List.exists f (toList s).
Applies f to each element x of set s until f x delivers true. Returns SOME x if such an x exists, NONE otherwise. For red-black trees, f is applied in increasing order. Equivalent to List.find f (toList s).
Applies f to each element x of set s and removes all elements for which f x delivered false. For red-black trees, f is applied in increasing order.