# 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

[ Top | Parent | Contents | Index | Root ]

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