SML/NJ Library Manual

The ORD_SET signature

Synopsis

signature ORD_SET
structure IntBinarySet :> ORD_SET
structure IntListSet :> ORD_SET


The ORD_SET signature provides an abstract description of applicative-style sets on a linearly ordered type.

Interface

structure Key : ORD_KEY
type item = Key.ord_key
type set
val empty : set
val singleton : item -> set
val add : (set * item) -> set
val add' : (item * set) -> set
val addList : (set * item list) -> set
val delete : (set * item) -> set
val member : (set * item) -> bool
val isEmpty : set -> bool
val equal : (set * set) -> bool
val compare : (set * set) -> order
val isSubset : (set * set) -> bool
val numItems : set -> int
val listItems : set -> item list
val union : (set * set) -> set
val intersection : (set * set) -> set
val difference : (set * set) -> set
val map : (item -> item) -> set -> set
val app : (item -> unit) -> set -> unit
val foldl : ((item * 'b) -> 'b) -> 'b -> set -> 'b
val foldr : ((item * 'b) -> 'b) -> 'b -> set -> 'b
val filter : (item -> bool) -> set -> set
val exists : (item -> bool) -> set -> bool
val find : (item -> bool) -> set -> item option


Description

type item

type set

val empty

The empty set.

singleton v

creates a singleton set containing v.

add (se, v)

returns a set that is the union of se and {v}.

add' (v, se)

returns a set that is the union of se and {v}. This differs from add only in the order of its arguments, for use with fold functions.

addList (se, l)

returns the set consisting of the union of se with the items in l. This is equivalent to:

          List.foldl add' se l
          

delete (se, v)

removes the item v from se and returns the resulting set. Raises the exception NotFound if the element is not found.

member (se, v)

returns true if and only if v is an element in the set.

isEmpty se

returns true if and only if the set is empty.

equal (se, se2)

returns true if and only if the two sets are equal.

compare (se, se2)

does a lexical comparison of two sets.

isSubset (se, se2)

returns true if and only if the first set is a subset of the second.

numItems se

returns the number of items in the set.

listItems se

returns the items in se, listed in increasing order.

union (se, se2)

returns the union of the two sets.

intersection (se, se2)

returns the intersection of the two sets.

difference (se, se2)

returns the difference of the two sets, i.e., those elements in se not in se2.

map f se

creates a new set by applying f to all the elements in se. This is equivalent to:

          List.foldl add' empty (List.map f (listItems se))
          

app f se

applies f to the entries of se in increasing order. This is equivalent to:

          List.app f (listItems se)
          

foldl f a se

applies the folding function f to the entries of se in increasing order. This is equivalent to:

          List.foldl f a (listItems se)
          

foldr f a se

applies the folding function f to the entries of se in decreasing order. This is equivalent to:

          List.foldr f a (listItems se)
          

filter f se

creates a new set containing only those elements of se that satisfy the predicate f. This is equivalent to:

          List.foldl add' empty (List.filter f (listItems se))
          

exists f se

returns true if and only if some element in se satisfies the predicate f.

find f se

returns an item in se satisfying the predicate f, if one exists. Otherwise, it returns NONE.

See Also

ORD_MAP, ORD_KEY, BinarySetFn, SplaySetFn, ListSetFn

Last Modified June 9, 1998
Comments to John Reppy
Copyright © 1998 Bell Labs, Lucent Technologies