Search Top Index

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.