signature SET functor MkRedBlackSet (Item : ORDERED) :> SET where type item = Item.t
The SET signature provides a functional interface to finite sets. The MkRedBlackSet functor provides an implementation of this interface based on red-black trees.
See also: IMP_SET, MAP, ORDERED
import signature SET from "x-alice:/lib/data/SET-sig" import functor MkRedBlackSet from "x-alice:/lib/data/MkRedBlackSet"
signature SET = sig type item type set type t = set exception Unknown of item exception Collision of item val empty : set val singleton : item -> 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 -> set val insertDisjoint : set * item -> set val insertWith : (item -> unit) -> set * item -> set val remove : set * item -> set val removeExistent : set * item -> set val removeWith : (item -> unit) -> set * item -> set val union : set * set -> set val unionDisjoint : set * set -> set val unionWith : (item -> unit) -> set * set -> set val intersect : set * set -> set val difference : set * set -> set 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 map : (item -> item) -> set -> set val mapPartial : (item -> item option) -> set -> set 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 -> set val partition : (item -> bool) -> set -> set * set end
The type of elements in the set.
The type of sets over elements of type item.
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.
The empty set.
The set only containing the value x.
Returns the 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.
Returns the 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).
Returns the set s extended 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 returned as in the first form. The following equivalences hold:
insert = insertWith ignore insertDisjoint = insertWith (fn y => raise Collision y)
Returns the set s with element x removed. In the first form, if no element equal to x is contained in s, then the set is returned unchanged. In the second form, Unknown x will be raised. In the third form, f is applied to x before the set is returned unchanged. The following equivalences hold:
remove = removeWith ignore removeExistent = removeWith (fn y => raise Unknown y)
Returns the union of sets s1 and s1. In the first form, if s2 contains an element x2 equal to an element x1 in set s1, then the resulting set will contain x2. In the second form, Collision x2 will be raised. In the third form, f is applied to x2 before the set is returned as in the first form. The following equivalences hold:
union = unionWith ignore unionDisjoint = unionWith (fn y => raise Collision y)
Returns the intersection of sets s1 and s1.
Returns the difference of sets s1 and s1, i.e. the sets of elements that are in s1 but not in s2.
Returns the cardinality of the set s, i.e. the number of elements it contains.
Returns true if s is the 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 the empty set. 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).
Returns the set which contains the results of applying f to each element in set s. For red-black trees, the function is applied in increasing order. Raises Collision x, if two applications of f return equal values x. Equivalent to fromList(List.map f (toList s)).
Applies f to each element in set s and returns the set of defined results. For red-black trees, the function is applied in increasing order. Raises Collision x, if two applications of f return equal results x. Equivalent to fromList(List.mapPartial 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 returns the set of elements for which f x delivered true. For red-black trees, f is applied in increasing order. Equivalent to fromList(List.filter f (toList s)).
Applies f to each element x of set s and returns the pair (s1, s2) of sets where s1 contains all elements for which f x delivered true, and s2 all elements for which it delivered false. For red-black trees, f is applied in increasing order. Equivalent to Pair.map (fromList, fromList) (List.partition f (toList s)).