alice
library
manual.

Home
Tour
Language
Library
CP Tutorial
Tools
Site Map

The SET signature

    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
  

type item

The type of elements in the set.

type set
type t = set

The type of sets over elements of type item.

exception Unknown of item

Indicates that an item could not be found in the set.

exception Collision of item

Indicates an attempt to add an item that already is in the set when using functions that disallow replacement.

empty

The empty set.

singleton x

The set only containing the value x.

fromList l

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.

fromVector v

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).

toList s

Returns the list of items in the set s. For red-black sets, the items are delivered in increasing order.

toVector s

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).

insert (s, x)
insertDisjoint (s, x)
insertWith f (s, x)

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)

remove (s, x)
removeExistent (s, x)
removeWith f (s, x)

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)

union (s1, s2)
unionDisjoint (s1, s2)
unionWith f (s1, s2)

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)

intersect (s1, s2)

Returns the intersection of sets s1 and s1.

difference (s1, s2)

Returns the difference of sets s1 and s1, i.e. the sets of elements that are in s1 but not in s2.

size s

Returns the cardinality of the set s, i.e. the number of elements it contains.

isEmpty s

Returns true if s is the empty set, false otherwise. Equivalent to size s = 0.

member (s, x)

Returns true if the set s contains an element equal to x, false otherwise.

choose s

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.

equal (s1, s2)

Returns true if s1 and s2 are sets with equal elements, false otherwise.

subset (s1, s2)

Returns true if s1 is a subset of s2, false otherwise.

disjoint (s1, s2)

Returns true if s1 and s2 are disjoint sets, false otherwise.

compare (s1, s2)

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.

app f s

Applies f to each element in set s. For red-black trees, this happens in increasing order. Equivalent to List.app f (toList s).

map f 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)).

mapPartial f 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)).

fold f a 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).

all f 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).

exists f 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).

find f 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).

filter f 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)).

partition f 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)).