GAP knows several special kinds of lists. A set in GAP is a special kind of list. A set contains no holes and its elements are sorted according to the GAP ordering of all its objects. Moreover a set contains no object twice.
The function IsSet tests whether an object is a set. It returns a
boolean value. For any list there exists a corresponding set. This set
is constructed by the function Set which takes the list as its argument
and returns a set obtained from this list by ignoring holes and
duplicates and by sorting the elements.
The elements of the sets used in the examples of this section are strings.
gap> fruits:= ["apple", "strawberry", "cherry", "plum"];
[ "apple", "strawberry", "cherry", "plum" ]
gap> IsSet(fruits);
false
gap> fruits:= Set(fruits);
[ "apple", "cherry", "plum", "strawberry" ]
Note that the original list fruits is not changed by the function
Set. We have to make a new assignment to the variable fruits in
order to make it a set.
The in operator is used to test whether an object is an element of a
set. It returns a boolean value true or false.
gap> "apple" in fruits;
true
gap> "banana" in fruits;
false
The in operator may as well be applied to ordinary lists. It is
however much faster to perform a membership test for sets since sets are
always sorted and a binary search can be used instead of a linear search.
New elements may be added to a set by the function AddSet which takes
the set fruits as its first argument and an element as its second
argument and adds the element to the set if it wasn't already there.
Note that the object fruits is changed.
gap> AddSet(fruits, "banana");
gap> fruits; # The banana is inserted in the right place.
[ "apple", "banana", "cherry", "plum", "strawberry" ]
gap> AddSet(fruits, "apple");
gap> fruits; # 'fruits' has not changed.
[ "apple", "banana", "cherry", "plum", "strawberry" ]
Sets can be intersected by the function Intersection and united by the
function Union which both take two sets as their arguments and return
the intersection (union) of the two sets as a new object.
gap> breakfast:= ["tea", "apple", "egg"];
[ "tea", "apple", "egg" ]
gap> Intersection(breakfast, fruits);
[ "apple" ]
It is however not necessary for the objects collected in a set to be of
the same type. You may as well have additional integers and boolean
values for breakfast.
The arguments of the functions Intersection and Union may as well be
ordinary lists, while their result is always a set. Note that in the
preceding example at least one argument of Intersection was not a set.
The functions IntersectSet and UniteSet also form the intersection
resp.~union of two sets. They will however not return the result but
change their first argument to be the result. Try them carefully.
In this section you have seen that sets are a special kind of list.
There are functions to expand sets, intersect or unite sets, and there is
the membership test with the in operator.
Strings and Characters. Sets are described in more detail in chapter Sets.
GAP 3.4.4