HELP SETS JL Cunningham, April 1982
This library provides a collection of procedures to manipulate 'sets'. The
sets are implemented using records (see HELP * CLASSES). Initially, the
library expects to be manipulating sets of WORDS, but this default can easily
be changed (see below).
------------------------
The procedures provided are:
ISSET(S) returns <true> if S is a set
CONSSET(L) ** constructs a set record, should not normally
be used, instead use LISTTOSET
ELEMENTS(S) returns the list of elements in set S
LISTTOSET(L) returns a set formed from a list of valid set elements
(see ISELEMENTTYPE below)
INTERSECT(S1,S2) returns the intersection of two sets, i.e. a set of all
the elements that occur both in S1 and S2.
UNION(S1,S2) returns the union of two sets, i.e. a set of all the
elements from either (or both) S1 or S2.
ELEMENTOF(E,S) returns <true> if E is an element of S
MAKESUBSET(S,P) applies P to each element of S, and returns the
subset of S for which P did not return <false>
SINGLETON(S) if S is a singleton set then returns its element,
otherwise <false>
SETDIFF(S1,S2) the asymmetric difference of sets S1 and S2, i.e.
all those elements of S1 which do not occur in S2
SUBSET(S1,S2) returns <true> if S1 is a subset of S2 else <false>
defined as (setdiff(s1,s2) = emptyset), so a mishap
occurs unless both S1 and S2 are sets
EMPTYSET This is a variable initialised to an empty set.
NOTES (A)
=========
The symmetric difference is not defined, but may easily be defined as
union(setdiff(s1,s2),setdiff(s2,s1))
or as
setdiff(union(s1,s2),intersect(s1,s2))
------------------------
User defined procedures:
=======================
ISELEMENTTYPE(E)
This variable can be defined by the user. It initially has as its value
the procedure ISWORD. It is used to check whether its argument is a legal
value for a set element, so that ELEMENTORDER (see below) is protected from
being called with illegal arguments (unless CONSSET is used explicitly with
bad a bad argument.)
ELEMENTORDER(E1,E2)
This variable can be defined by the user. It initially has as its value
the procedure ALPHABEFORE. It is used for two purposes:
a) recognising element identity
If E1 and E2 are to be regarded as the same element, then
ELEMENTORDER should return the number 1. Normally, this will
be when they are '=', see NOTES (B) below.
b) providing an ordering for set elements, so that sets may be sorted
into a 'canonical form'. If E1 precedes E2 then ELEMENTORDER
should return <true>, if E2 precedes E1 then <false>. Any elements
which are identical (ELEMENTORDER returns 1) should be in the same
place when the elements are sorted.
NOTES (B)
=========
If the element identity test is '=', then set identity will also be '=',
i.e. two sets will be '=' exactly when they have the same elements.
If the element identity test is '==' then identical sets will be '=', but
not necessarily '==', and also some non-identical sets may be '='.
If ELEMENTORDER never returns '1' then strange things will happen, because an
element will not be identical to itself.
If the element identity test is weaker than '=', then identical sets may
not be '='. In this case, a simple test for set-equality is whether the
symmetric difference (see NOTES (A)) of the two sets is '=' to the EMPTYSET,
however, it might be better to explicitly compare corresponding elements
from both sets. Remember that different variants of a single element should
produce the same ordering relative to other elements using ELEMENTORDER.