9.3 Set Comparisons

9.3.1 Set Equality and Inequality

Two sets are equal when their list of elements is identical. In mathematics, one simply writes A = B to express equality, and A <> B to express set inequality. Both may also be used in the sense of Boolean expressions.

The Modula-2 notation for the boolean expression "A is equal to B" is written A = B, and the Modula-2 notation for the boolean expression "A is not equal to B" is written A <> B or A # B.

Of course, the two sets being compared must be of the same type, or a compiler error results. Here are some examples:

If one has:

TYPE
  CharSet = SET OF CHAR;
  CapSet = SET OF ['A' .. 'Z'];

VAR
  firstCharSet, secondCharSet : CharSet;
  firstCapSet, secondCapSet : CapSet;

BEGIN
  firstCharSet := CharSet {'A', 'B'};
  secondCharSet := CharSet {'B', 'C'};
  firstCapSet := CapSet {'A', 'B'};
  secondCapSet := CapSet {'A', 'B', 'C'};

then here are some comparisons with the outcome:

IF firstCapSet = firstCharSet ..  (* error, wrong types *)
IF firstCapSet <> secondCapSet..  (* not equal, so acts on TRUE *)

Notice that the "=" and "<>" (or #) symbols have been used for equality/inequality tests of both individual numerical equality and for equality of sets. The symbol "=" used to compare two sets has a different meaning than the symbol "=" used to compare two numbers. The compiler must sort out which meaning is intended by the programmer according to the correct context in which the symbol is used.

Whenever a symbol or operator is used with two or more different meanings in different contexts, it is said to be overloaded.

Sometimes overloading is less obvious. Strictly speaking, the "+" operator is overloaded just because it can be used with all three of the cardinal, integer, and real types, even though the mathematical meaning of the symbol is essentially the same for all three. However, the overloading of operators like "+" is more obvious when it is also used to represent set union. As the following sections illustrate, the "=" and "#" are not the only relational operators to be overloaded.

9.3.2 Subset

If all the elements of a set A are contained in a set B one says that A is a subset of B. The mathematical notation is A B, and the relationship is illustrated in figure 9.2.

The Modula-2 notation for the boolean expression "A is a subset of B" is written A <= B.

For example, {1,2,4} {1,2,4,7} and {a,b} {a,b,c,d}, or, to put it in Modula-2 notation, if result is a boolean variable, then

result := DigitSet{1,2,4} <= DigitSet{1,2,4,7};

or

result := DigitSet{1,2,4} <= DigitSet{1,2,4};

leaves result holding TRUE, and

result := DigitSet{1,2,4,5} <= DigitSet{1,2,4,7};

or

result := NOT (Charset{"a","b"} <= Charset{"a","b","c","d"});

leaves result holding FALSE.

If, in addition to A being a subset of B, B and A are known not to be equal, then A is a proper subset of B. The mathematical notation is A B. Although one might expect the Modula-2 notation for the boolean expression "A is a proper subset of B" to be written A < B, this notation is not in fact used, and it is necessary to employ (A < B) AND (A # B) for proper subset.

9.3.3 Superset

Sometimes the set containment symbols are written the other way around. One might have occasion to write B A rather than A B, for instance. Rather than read this from right to left, it is quite in order to say "B is a superset of A."

The Modula-2 notation for the boolean expression "A is a superset of B" is written A >= B.

Likewise, one might have occasion to say B A rather than A B. This could be read "B is a proper superset of A." There is no single Modula-2 notation for proper superset; it must be written as a compound Boolean expression as above.


Contents