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