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.