1% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
2% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
3\newcommand{\SetXmpTitle}{Set}
4\newcommand{\SetXmpNumber}{9.75}
5%
6% =====================================================================
7\begin{page}{SetXmpPage}{9.75 Set}
8% =====================================================================
9\beginscroll
10
11%
12%
13%
14%
15%
16
17
18%
19
20The \spadtype{Set} domain allows one to represent explicit finite sets of values.
21These are similar to lists, but duplicate elements are not allowed.
22\xtc{
23Sets can be created by giving a fixed set of values \ldots
24}{
25\spadpaste{s := set [x^2-1, y^2-1, z^2-1] \bound{s}}
26}
27\xtc{
28or by using a collect form, just as for lists.
29In either case, the set is formed from a finite collection of values.
30}{
31\spadpaste{t := set [x^i - i+1 for i in 2..10 | prime? i] \bound{t}}
32}
33
34\xtc{
35The basic operations on sets are
36\spadfunFrom{intersect}{Set}, \spadfunFrom{union}{Set},
37\spadfunFrom{difference}{Set},
38and \spadfunFrom{symmetricDifference}{Set}.
39}{
40\spadpaste{i := intersect(s,t)      \free{s t}\bound{i}}
41}
42\xtc{
43}{
44\spadpaste{u := union(s,t)          \free{s t}\bound{u}}
45}
46\xtc{
47The set \spad{difference(s,t)} contains those members of \spad{s} which
48are not in \spad{t}.
49}{
50\spadpaste{difference(s,t)          \free{s t}}
51}
52\xtc{
53The set \spad{symmetricDifference(s,t)} contains those elements which are
54in \spad{s} or \spad{t} but not in both.
55}{
56\spadpaste{symmetricDifference(s,t)          \free{s t}}
57}
58
59\xtc{
60Set membership is tested using the \spadfunFrom{member?}{Set} operation.
61}{
62\spadpaste{member?(y, s)               \free{s}}
63}
64\xtc{
65}{
66\spadpaste{member?((y+1)*(y-1), s)     \free{s}}
67}
68\xtc{
69The \spadfunFrom{subset?}{Set} function determines whether one set is a subset
70of another.
71}{
72\spadpaste{subset?(i, s)               \free{i s}}
73}
74\xtc{
75}{
76\spadpaste{subset?(u, s)               \free{u s}}
77}
78
79\xtc{
80When the base type is finite, the absolute complement of a set is
81defined.
82This finds the set of all multiplicative generators of
83\spadtype{PrimeField 11}---the integers mod \spad{11.}
84}{
85\spadpaste{gs := set [g for i in 1..11 | primitive?(g := i::PF 11)] \bound{gs}}
86}
87\xtc{
88The following values are not generators.
89}{
90\spadpaste{complement gs \free{gs}}
91}
92
93Often the members of a set are computed individually; in addition,
94values can be inserted or removed from a set over the course of a
95computation.
96\xtc{
97There are two ways to do this:
98}{
99\spadpaste{a := set [i^2 for i in 1..5] \bound{a}}
100}
101\xtc{
102One is to view a set as a data structure and to apply updating operations.
103}{
104\spadpaste{insert!(32, a) \free{a}\bound{ainsert}}
105}
106\xtc{
107}{
108\spadpaste{remove!(25, a) \free{a}\bound{aremove}}
109}
110\xtc{
111}{
112\spadpaste{a \free{aremove ainsert}}
113}
114\xtc{
115The other way is to view a set as a mathematical entity and to
116create new sets from old.
117}{
118\spadpaste{b := b0 := set [i^2 for i in 1..5] \bound{b}}
119}
120\xtc{
121}{
122\spadpaste{b := union(b, {32})         \free{b}\bound{binsert}}
123}
124\xtc{
125}{
126\spadpaste{b := difference(b, {25})    \free{binsert}\bound{bremove}}
127}
128\xtc{
129}{
130\spadpaste{b0 \free{bremove}}
131}
132
133For more information about lists, see \downlink{`List'}{ListXmpPage}\ignore{List}.
134\showBlurb{Set}
135\endscroll
136\autobuttons
137\end{page}
138%
139