1.11 About Sets

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.

Previous Up Top Next
Index

GAP 3.4.4
April 1997