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