<html><head><title>[ref] 28 Collections</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP027.htm">Previous</a>] [<a href ="CHAP029.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>28 Collections</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP028.htm#SECT001">Collection Families</a>
<li> <A HREF="CHAP028.htm#SECT002">Lists and Collections</a>
<li> <A HREF="CHAP028.htm#SECT003">Attributes and Properties for Collections</a>
<li> <A HREF="CHAP028.htm#SECT004">Operations for Collections</a>
<li> <A HREF="CHAP028.htm#SECT005">Membership Test for Collections</a>
<li> <A HREF="CHAP028.htm#SECT006">Random Elements</a>
<li> <A HREF="CHAP028.htm#SECT007">Iterators</a>
</ol><p>
<p>
A <strong>collection</strong> in <font face="Gill Sans,Helvetica,Arial">GAP</font> consists of elements in the same family
(see <a href="CHAP013.htm#SECT001">Families</a>).
The most important kinds of collections are <strong>homogeneous lists</strong>
(see <a href="CHAP021.htm">Lists</a>) and <strong>domains</strong> (see <a href="CHAP012.htm#SECT004">Domains</a>).
Note that a list is never a domain, and a domain is never a list.
A list is a collection if and only if it is nonempty and homogeneous.
<p>
Basic operations for collections are <code>Size</code> (see <a href="CHAP028.htm#SSEC003.6">Size</a>)
and <code>Enumerator</code> (see <a href="CHAP028.htm#SSEC002.2">Enumerator</a>);
for <strong>finite</strong> collections, <code>Enumerator</code> admits to delegate the other
operations for collections
(see <a href="CHAP028.htm#SECT003">Attributes and Properties for Collections</a>
and <a href="CHAP028.htm#SECT004">Operations for Collections</a>)
to functions for lists (see <a href="CHAP021.htm">Lists</a>).
Obviously, special methods depending on the arguments are needed for
the computation of e.g. the intersection of two <strong>infinite</strong> domains.
<p>
<a name = ""></a>
<li><code>IsCollection( </code><var>obj</var><code> ) C</code>
<p>
tests whether an object is a collection.
<p>
Some of the functions for lists and collections have been described in the
chapter about lists, mainly in Section <a href="CHAP021.htm#SECT020">Operations for Lists</a>.
In this chapter, we describe those functions for which the
``collection aspect'' seems to be more important than the ``list aspect''.
As in Chapter <a href="CHAP021.htm">Lists</a>, an argument that is a list will be denoted by <var>list</var>,
and an argument that is a collection will be denoted by <var>C</var>.
<p>
<p>
<h2><a name="SECT001">28.1 Collection Families</a></h2>
<p><p>
<a name = "SSEC001.1"></a>
<li><code>CollectionsFamily( </code><var>Fam</var><code> ) A</code>
<p>
For a family <var>Fam</var>, <code>CollectionsFamily</code> returns the family of all
collections that consist of elements in <var>Fam</var>.
<p>
Note that families (see <a href="CHAP013.htm#SECT001">Families</a>) are used to describe relations
between objects.
Important such relations are that between an element <var>elm</var> and each
collection of elements that lie in the same family as <var>elm</var>,
and that between two collections whose elements lie in the same family.
Therefore, all collections of elements in the family <var>Fam</var> form the new
family <code>CollectionsFamily( </code><var>Fam</var><code> )</code>.
<p>
<a name = "SSEC001.2"></a>
<li><code>IsCollectionFamily( </code><var>Fam</var><code> ) C</code>
<p>
is <code>true</code> if <var>Fam</var> is a family of collections, and <code>false</code> otherwise.
<p>
<a name = "SSEC001.3"></a>
<li><code>ElementsFamily( </code><var>Fam</var><code> ) A</code>
<p>
returns the family from which the collections family <var>Fam</var> was created
by <code>CollectionsFamily</code>.
The way a collections family is created, it always has its elements
family stored.
If <var>Fam</var> is not a collections family (see <a href="CHAP028.htm#SSEC001.2">IsCollectionFamily</a>)
then an error is signalled.
<p>
<pre>
gap> fam:= FamilyObj( (1,2) );;
gap> collfam:= CollectionsFamily( fam );;
gap> fam = collfam; fam = ElementsFamily( collfam );
false
true
gap> collfam = FamilyObj( [ (1,2,3) ] ); collfam = FamilyObj( Group( () ) );
true
true
gap> collfam = CollectionsFamily( collfam );
false
</pre>
<p>
<a name = "SSEC001.4"></a>
<li><code>CategoryCollections( </code><var>filter</var><code> ) F</code>
<p>
Let <var>filter</var> be a filter that is <code>true</code> for all elements of a family
<var>Fam</var>, by construction of <var>Fam</var>.
Then <code>CategoryCollections</code> returns a category that is <code>true</code> for all
elements in <code>CollectionsFamily( </code><var>Fam</var><code> )</code>.
<p>
For example, the construction of <code>PermutationsFamily</code> guarantees that
each of its elements lies in the filter <code>IsPerm</code>,
and each collection of permutations lies in the category
<code>CategoryCollections( IsPerm )</code>.
<p>
Note that this works only if the collections category is created <strong>before</strong>
the collections family.
So it is necessary to construct interesting collections categories
immediately after the underlying category has been created.
<p>
<p>
<h2><a name="SECT002">28.2 Lists and Collections</a></h2>
<p><p>
<a name = "I0"></a>
<a name = "SSEC002.1"></a>
<li><code>IsListOrCollection( </code><var>obj</var><code> ) C</code>
<p>
Several functions are defined for both lists and collections,
for example <code>Intersection</code> (see <a href="CHAP028.htm#SSEC004.2">Intersection</a>), <code>Iterator</code>
(see <a href="CHAP028.htm#SSEC007.1">Iterator</a>), and <code>Random</code> (see <a href="CHAP014.htm#SSEC005.2">Random</a>).
<code>IsListOrCollection</code> is a supercategory of <code>IsList</code> and <code>IsCollection</code>
(that is, all lists and collections lie in this category),
which is used to describe the arguments of functions such as the ones
listed above.
<p>
The following functions take a <strong>list or collection</strong> as argument,
and return a corresponding <strong>list</strong>.
They differ in whether or not the result is
mutable or immutable (see <a href="CHAP012.htm#SECT006">Mutability and Copyability</a>),
guaranteed to be sorted,
or guaranteed to admit list access in constant time
(see <a href="CHAP021.htm#SSEC001.5">IsConstantTimeAccessList</a>).
<p>
<a name = "SSEC002.2"></a>
<li><code>Enumerator( </code><var>C</var><code> ) A</code>
<li><code>Enumerator( </code><var>list</var><code> ) A</code>
<p>
<code>Enumerator</code> returns an immutable list <var>enum</var>.
If the argument is a list <var>list</var> (which may contain holes),
then <code>Length( </code><var>enum</var><code> )</code> is <code>Length( </code><var>list</var><code> )</code>,
and <var>enum</var> contains the elements (and holes) of <var>list</var> in the same order.
If the argument is a collection <var>C</var> that is not a list,
then <code>Length( </code><var>enum</var><code> )</code> is the number of different elements of <var>C</var>,
and <var>enum</var> contains the different elements of <var>C</var> in an unspecified
order, which may change for repeated calls of <code>Enumerator</code>.
<code></code><var>enum</var><code>[</code><var>pos</var><code>]</code> may not execute in constant time
(see <a href="CHAP021.htm#SSEC001.5">IsConstantTimeAccessList</a>),
and the size of <var>enum</var> in memory is as small as is feasible.
<p>
For lists <var>list</var>, the default method is <code>Immutable</code>.
For collections <var>C</var> that are not lists, there is no default method.
<p>
<a name = "SSEC002.3"></a>
<li><code>EnumeratorSorted( </code><var>C</var><code> ) A</code>
<li><code>EnumeratorSorted( </code><var>list</var><code> ) A</code>
<p>
<code>EnumeratorSorted</code> returns an immutable list <var>enum</var>.
The argument must be a collection <var>C</var> or a list <var>list</var> which may contain
holes but whose elements lie in the same family (see <a href="CHAP013.htm#SECT001">Families</a>).
<code>Length( </code><var>enum</var><code> )</code> is the number of different elements of
<var>C</var> resp. <var>list</var>,
and <var>enum</var> contains the different elements in sorted order, w.r.t. <code><</code>.
<code></code><var>enum</var><code>[</code><var>pos</var><code>]</code> may not execute in constant time
(see <a href="CHAP021.htm#SSEC001.5">IsConstantTimeAccessList</a>),
and the size of <var>enum</var> in memory is as small as is feasible.
<p>
<pre>
gap> Enumerator( [ 1, 3,, 2 ] );
[ 1, 3,, 2 ]
gap> enum:= Enumerator( Rationals );; elm:= enum[ 10^6 ];
-69/907
gap> Position( enum, elm );
1000000
gap> IsMutable( enum ); IsSortedList( enum );
false
false
gap> IsConstantTimeAccessList( enum );
false
gap> EnumeratorSorted( [ 1, 3,, 2 ] );
[ 1, 2, 3 ]
</pre>
<p>
<a name = "SSEC002.4"></a>
<li><code>EnumeratorByFunctions( </code><var>D</var><code>, </code><var>record</var><code> ) F</code>
<li><code>EnumeratorByFunctions( </code><var>Fam</var><code>, </code><var>record</var><code> ) F</code>
<p>
<code>EnumeratorByFunctions</code> returns an immutable, dense, and duplicate-free
list <var>enum</var> for which <code>IsBound</code>, element access, <code>Length</code>, and <code>Position</code>
are computed via prescribed functions.
<p>
Let <var>record</var> be a record with at least the following components.
<p>
<dl compact>
<dt><code>ElementNumber</code> <dd>
a function taking two arguments <var>enum</var> and <var>pos</var>,
which returns <code></code><var>enum</var><code>[ </code><var>pos</var><code> ]</code> (see <a href="CHAP021.htm#SECT002">Basic Operations for Lists</a>);
it can be assumed that the argument <var>pos</var> is a positive integer,
but <var>pos</var> may be larger than the length of <var>enum</var> (in which case
an error must be signalled);
note that the result must be immutable since <var>enum</var> itself is
immutable,
<p>
<dt><code>NumberElement</code> <dd>
a function taking two arguments <var>enum</var> and <var>elm</var>,
which returns <code>Position( </code><var>enum</var><code>, </code><var>elm</var><code> )</code> (see <a href="CHAP021.htm#SSEC016.1">Position</a>);
it cannot be assumed that <var>elm</var> is really contained in <var>enum</var>
(and <code>fail</code> must be returned if not);
note that for the three argument version of <code>Position</code>, the
method that is available for duplicate-free lists suffices.
</dl>
Further (data) components may be contained in <var>record</var> which can be used
by these function.
<p>
If the first argument is a domain <var>D</var> then <var>enum</var> lists the elements of
<var>D</var> (in general <var>enum</var> is <strong>not</strong> sorted),
and methods for <code>Length</code>, <code>IsBound</code>, and <code>PrintObj</code> may use <var>D</var>.
<p>
If one wants to describe the result without creating a domain then the
elements are given implicitly by the functions in <var>record</var>,
and the first argument must be a family <var>Fam</var> which will become the
family of <var>enum</var>;
if <var>enum</var> is not homogeneous then <var>Fam</var> must be <code>ListsFamily</code>,
otherwise it must be the collections family of any element in <var>enum</var>.
In this case, additionally the following component in <var>record</var> is
needed.
<p>
<dl compact>
<dt><code>Length</code> <dd>
a function taking the argument <var>enum</var>,
which returns the length of <var>enum</var> (see <a href="CHAP021.htm#SSEC017.5">Length</a>).
</dl>
<p>
The following components are optional; they are used if they are present
but default methods are installed for the case that they are missing.
<p>
<dl compact>
<dt><code>IsBound\[\]</code> <dd>
a function taking two arguments <var>enum</var> and <var>k</var>,
which returns <code>IsBound( </code><var>enum</var><code>[ </code><var>k</var><code> ] )</code>
(see <a href="CHAP021.htm#SECT002">Basic Operations for Lists</a>);
if this component is missing then <code>Length</code> is used for computing the
result,
<p>
<dt><code>Membership</code> <dd>
a function taking two arguments <var>elm</var> and <var>enum</var>,
which returns <code>true</code> is <var>elm</var> is an element of <var>enum</var>,
and <code>false</code> otherwise (see <a href="CHAP021.htm#SECT002">Basic Operations for Lists</a>);
if this component is missing then <code>NumberElement</code> is used
for computing the result,
<p>
<dt><code>AsList</code> <dd>
a function taking one argument <var>enum</var>, which returns a list with the
property that the access to each of its elements will take roughly
the same time (see <a href="CHAP021.htm#SSEC001.5">IsConstantTimeAccessList</a>);
if this component is missing then <code>ConstantTimeAccessList</code> is used
for computing the result,
<p>
<dt><code>ViewObj</code> and <code>PrintObj</code> <dd>
two functions that print what one wants to be printed when
<code>View( </code><var>enum</var><code> )</code> or <code>Print( </code><var>enum</var><code> )</code> is called
(see <a href="CHAP006.htm#SECT003">View and Print</a>),
if the <code>ViewObj</code> component is missing then the <code>PrintObj</code> method is
used as a default.
</dl>
<p>
If the result is known to have additional properties such as being
strictly sorted (see <a href="CHAP021.htm#SSEC017.4">IsSSortedList</a>) then it can be useful to set
these properties after the construction of the enumerator,
before it is used for the first time.
And in the case that a new sorted enumerator of a domain is implemented
via <code>EnumeratorByFunctions</code>, and this construction is installed as a
method for the operation <code>Enumerator</code> (see <a href="CHAP028.htm#SSEC002.2">Enumerator</a>),
then it should be installed also as a method for <code>EnumeratorSorted</code>
(see <a href="CHAP028.htm#SSEC002.3">EnumeratorSorted</a>).
<p>
Note that it is <strong>not</strong> checked that <code>EnumeratorByFunctions</code> really returns
a dense and duplicate-free list.
<code>EnumeratorByFunctions</code> does <strong>not</strong> make a shallow copy of <var>record</var>,
this record is changed in place
(see <a href="../prg/CHAP003.htm#SECT008">Creating Objects</a> in ``Programming in <font face="Gill Sans,Helvetica,Arial">GAP</font>'').
<p>
It would be easy to implement a slightly generalized setup for
enumerators that need not be duplicate-free (where the three argument
version of <code>Position</code> is supported),
but the resulting overhead for the methods seems not to be justified.
<p>
<code> List( </code><var>C</var><code> )</code>
<br><code> List( </code><var>list</var><code> )</code>
<p>
This function is described in <a href="CHAP021.htm#SSEC020.17">List</a>,
together with the probably more frequently used version
which takes a function as second argument and returns the list of function
values of the list elements.
<pre>
gap> l:= List( Group( (1,2,3) ) );
[ (), (1,3,2), (1,2,3) ]
gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );
true
false
true
</pre>
<p>
<a name = "SSEC002.5"></a>
<li><code>SortedList( </code><var>C</var><code> ) O</code>
<li><code>SortedList( </code><var>list</var><code> ) O</code>
<p>
<code>SortedList</code> returns a new mutable and dense list <var>new</var>.
The argument must be a collection <var>C</var> or a list <var>list</var> which may contain
holes but whose elements lie in the same family (see <a href="CHAP013.htm#SECT001">Families</a>).
<code>Length( </code><var>new</var><code> )</code> is the number of elements of <var>C</var> resp. <var>list</var>,
and <var>new</var> contains the elements in sorted order, w.r.t. <code><=</code>.
<code></code><var>new</var><code>[</code><var>pos</var><code>]</code> executes in constant time
(see <a href="CHAP021.htm#SSEC001.5">IsConstantTimeAccessList</a>),
and the size of <var>new</var> in memory is proportional to its length.
<p>
<pre>
gap> l:= SortedList( Group( (1,2,3) ) );
[ (), (1,2,3), (1,3,2) ]
gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );
true
true
true
gap> SortedList( [ 1, 2, 1,, 3, 2 ] );
[ 1, 1, 2, 2, 3 ]
</pre>
<p>
<a name = "SSEC002.6"></a>
<li><code>SSortedList( </code><var>C</var><code> ) O</code>
<li><code>SSortedList( </code><var>list</var><code> ) O</code>
<a name = "SSEC002.6"></a>
<li><code>Set( </code><var>C</var><code> ) O</code>
<p>
<code>SSortedList</code> (``strictly sorted list'') returns a new dense, mutable,
and duplicate free list <var>new</var>.
The argument must be a collection <var>C</var> or a list <var>list</var> which may contain
holes but whose elements lie in the same family (see <a href="CHAP013.htm#SECT001">Families</a>).
<code>Length( </code><var>new</var><code> )</code> is the number of different elements of <var>C</var>
resp. <var>list</var>,
and <var>new</var> contains the different elements in strictly sorted order,
w.r.t. <code><</code>.
<code></code><var>new</var><code>[</code><var>pos</var><code>]</code> executes in constant time
(see <a href="CHAP021.htm#SSEC001.5">IsConstantTimeAccessList</a>),
and the size of <var>new</var> in memory is proportional to its length.
<p>
<code>Set</code> is simply a synonym for <code>SSortedList</code>.
<p>
<pre>
gap> l:= SSortedList( Group( (1,2,3) ) );
[ (), (1,2,3), (1,3,2) ]
gap> IsMutable( l ); IsSSortedList( l ); IsConstantTimeAccessList( l );
true
true
true
gap> SSortedList( [ 1, 2, 1,, 3, 2 ] );
[ 1, 2, 3 ]
</pre>
<p>
<a name = "SSEC002.7"></a>
<li><code>AsList( </code><var>C</var><code> ) A</code>
<li><code>AsList( </code><var>list</var><code> ) A</code>
<p>
<code>AsList</code> returns a immutable list <var>imm</var>.
If the argument is a list <var>list</var> (which may contain holes),
then <code>Length( </code><var>imm</var><code> )</code> is <code>Length( </code><var>list</var><code> )</code>,
and <var>imm</var> contains the elements (and holes) of <var>list</var> in the same order.
If the argument is a collection <var>C</var> that is not a list,
then <code>Length( </code><var>imm</var><code> )</code> is the number of different elements of <var>C</var>,
and <var>imm</var> contains the different elements of <var>C</var> in an unspecified
order, which may change for repeated calls of <code>AsList</code>.
<code></code><var>imm</var><code>[</code><var>pos</var><code>]</code> executes in constant time
(see <a href="CHAP021.htm#SSEC001.5">IsConstantTimeAccessList</a>),
and the size of <var>imm</var> in memory is proportional to its length.
<p>
If you expect to do many element tests in the resulting list, it might
be worth to use a sorted list instead, using <code>AsSSortedList</code>.
<p>
<pre>
gap> l:= AsList( [ 1, 3, 3,, 2 ] );
[ 1, 3, 3,, 2 ]
gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );
false
false
true
gap> AsList( Group( (1,2,3), (1,2) ) );
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
</pre>
<p>
<a name = "SSEC002.8"></a>
<li><code>AsSortedList( </code><var>C</var><code> ) A</code>
<li><code>AsSortedList( </code><var>list</var><code> ) A</code>
<p>
<code>AsSortedList</code> returns a dense and immutable list <var>imm</var>.
The argument must be a collection <var>C</var> or a list <var>list</var> which may contain
holes but whose elements lie in the same family (see <a href="CHAP013.htm#SECT001">Families</a>).
<code>Length( </code><var>imm</var><code> )</code> is the number of elements of <var>C</var> resp. <var>list</var>,
and <var>imm</var> contains the elements in sorted order, w.r.t. <code><=</code>.
<code></code><var>new</var><code>[</code><var>pos</var><code>]</code> executes in constant time
(see <a href="CHAP021.htm#SSEC001.5">IsConstantTimeAccessList</a>),
and the size of <var>imm</var> in memory is proportional to its length.
<p>
The only difference to the operation <code>SortedList</code> (see <a href="CHAP028.htm#SSEC002.5">SortedList</a>)
is that <code>AsSortedList</code> returns an <strong>immutable</strong> list.
<p>
<pre>
gap> l:= AsSortedList( [ 1, 3, 3,, 2 ] );
[ 1, 2, 3, 3 ]
gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l );
false
true
true
gap> IsSSortedList( l );
false
</pre>
<p>
<a name = "SSEC002.9"></a>
<li><code>AsSSortedList( </code><var>C</var><code> ) A</code>
<li><code>AsSSortedList( </code><var>list</var><code> ) A</code>
<a name = "SSEC002.9"></a>
<li><code>AsSet( </code><var>C</var><code> ) A</code>
<p>
<code>AsSSortedList</code> (``as strictly sorted list'') returns a dense, immutable,
and duplicate free list <var>imm</var>.
The argument must be a collection <var>C</var> or a list <var>list</var> which may contain
holes but whose elements lie in the same family (see <a href="CHAP013.htm#SECT001">Families</a>).
<code>Length( </code><var>imm</var><code> )</code> is the number of different elements of <var>C</var>
resp. <var>list</var>,
and <var>imm</var> contains the different elements in strictly sorted order,
w.r.t. <code><</code>.
<code></code><var>imm</var><code>[</code><var>pos</var><code>]</code> executes in constant time
(see <a href="CHAP021.htm#SSEC001.5">IsConstantTimeAccessList</a>),
and the size of <var>imm</var> in memory is proportional to its length.
<p>
Because the comparisons required for sorting can be very expensive for
some kinds of objects, you should use <code>AsList</code> instead if you do not
require the result to be sorted.
<p>
The only difference to the operation <code>SSortedList</code> (see <a href="CHAP028.htm#SSEC002.6">SSortedList</a>)
is that <code>AsSSortedList</code> returns an <strong>immutable</strong> list.
<p>
<code>AsSet</code> is simply a synonym for <code>AsSSortedList</code>.
<p>
In general a function that returns a set of elements is free, in fact
encouraged, to return a domain instead of the proper set of its elements.
This allows one to keep a given structure, and moreover the
representation by a domain object is usually more space efficient.
<code>AsSSortedList</code> must of course <strong>not</strong> do this,
its only purpose is to create the proper set of elements.
<p>
<a name = "I1"></a>
<pre>
gap> l:= AsSSortedList( l );
[ 1, 2, 3 ]
gap> IsMutable( l ); IsSSortedList( l ); IsConstantTimeAccessList( l );
false
true
true
gap> AsSSortedList( Group( (1,2,3), (1,2) ) );
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
</pre>
<p>
<a name = "SSEC002.10"></a>
<li><code>Elements( </code><var>C</var><code> ) F</code>
<p>
<code>Elements</code> does the same as <code>AsSSortedList</code> (see <a href="CHAP028.htm#SSEC002.9">AsSSortedList</a>),
that is, the return value is a strictly sorted list of the elements in
the list or collection <var>C</var>.
<p>
<code>Elements</code> is only supported for backwards compatibility.
In many situations, the sortedness of the ``element list'' for a
collection is in fact not needed, and one can save a lot of time by
asking for a list that is <strong>not</strong> necessarily sorted, using <code>AsList</code>
(see <a href="CHAP028.htm#SSEC002.7">AsList</a>).
If one is really interested in the strictly sorted list of elements in
<var>C</var> then one should use <code>AsSet</code> or <code>AsSSortedList</code> instead.
<p>
<p>
<h2><a name="SECT003">28.3 Attributes and Properties for Collections</a></h2>
<p><p>
<a name = "SSEC003.1"></a>
<li><code>IsEmpty( </code><var>C</var><code> ) P</code>
<li><code>IsEmpty( </code><var>list</var><code> ) P</code>
<p>
<code>IsEmpty</code> returns <code>true</code> if the collection <var>C</var> resp. the list <var>list</var> is
<strong>empty</strong> (that is it contains no elements), and <code>false</code> otherwise.
<p>
<a name = "SSEC003.2"></a>
<li><code>IsFinite( </code><var>C</var><code> ) P</code>
<p>
<code>IsFinite</code> returns <code>true</code> if the collection <var>C</var> is finite, and <code>false</code>
otherwise.
<p>
The default method for <code>IsFinite</code> checks the size (see <a href="CHAP028.htm#SSEC003.6">Size</a>) of <var>C</var>.
<p>
Methods for <code>IsFinite</code> may call <code>Size</code>,
but methods for <code>Size</code> must <strong>not</strong> call <code>IsFinite</code>.
<p>
<a name = "I2"></a>
<a name = "SSEC003.3"></a>
<li><code>IsTrivial( </code><var>C</var><code> ) P</code>
<p>
<code>IsTrivial</code> returns <code>true</code> if the collection <var>C</var> consists of exactly one
element.
<p>
<a name = "SSEC003.4"></a>
<li><code>IsNonTrivial( </code><var>C</var><code> ) P</code>
<p>
<code>IsNonTrivial</code> returns <code>true</code> if the collection <var>C</var> is empty or consists
of at least two elements (see <a href="CHAP028.htm#SSEC003.3">IsTrivial</a>).
<p>
<pre>
gap> IsEmpty( [] ); IsEmpty( [ 1 .. 100 ] ); IsEmpty( Group( (1,2,3) ) );
true
false
false
gap> IsFinite( [ 1 .. 100 ] ); IsFinite( Integers );
true
false
gap> IsTrivial( Integers ); IsTrivial( Group( () ) );
false
true
gap> IsNonTrivial( Integers ); IsNonTrivial( Group( () ) );
true
false
</pre>
<p>
<a name = "SSEC003.5"></a>
<li><code>IsWholeFamily( </code><var>C</var><code> ) P</code>
<p>
<code>IsWholeFamily</code> returns <code>true</code> if the collection <var>C</var> contains the whole
family (see <a href="CHAP013.htm#SECT001">Families</a>) of its elements.
<p>
<pre>
gap> IsWholeFamily( Integers )
> ; # all rationals and cyclotomics lie in the family
false
gap> IsWholeFamily( Integers mod 3 )
> ; # all finite field elements in char. 3 lie in this family
false
gap> IsWholeFamily( Integers mod 4 );
true
gap> IsWholeFamily( FreeGroup( 2 ) );
true
</pre>
<p>
<a name = "SSEC003.6"></a>
<li><code>Size( </code><var>C</var><code> ) A</code>
<li><code>Size( </code><var>list</var><code> ) A</code>
<p>
<code>Size</code> returns the size of the collection <var>C</var>, which is either an integer
or <code>infinity</code>.
The argument may also be a list <var>list</var>, in which case the result is the
length of <var>list</var> (see <a href="CHAP021.htm#SSEC017.5">Length</a>).
<p>
The default method for <code>Size</code> checks the length of an enumerator of <var>C</var>.
<p>
Methods for <code>IsFinite</code> may call <code>Size</code>,
but methods for <code>Size</code> must not call <code>IsFinite</code>.
<p>
<a name = "I3"></a>
<a name = "I4"></a>
<pre>
gap> Size( [1,2,3] ); Size( Group( () ) ); Size( Integers );
3
1
infinity
</pre>
<p>
<a name = "SSEC003.7"></a>
<li><code>Representative( </code><var>C</var><code> ) A</code>
<p>
<code>Representative</code> returns a <strong>representative</strong> of the collection <var>C</var>.
<p>
Note that <code>Representative</code> is free in choosing a representative if
there are several elements in <var>C</var>.
It is not even guaranteed that <code>Representative</code> returns the same
representative if it is called several times for one collection.
The main difference between <code>Representative</code> and <code>Random</code>
(see <a href="CHAP014.htm#SSEC005.2">Random</a>) is that <code>Representative</code> is free to choose a value that is
cheap to compute,
while <code>Random</code> must make an effort to randomly distribute its answers.
<p>
If <var>C</var> is a domain then there are methods for <code>Representative</code> that try
to fetch an element from any known generator list of <var>C</var>,
see <a href="CHAP030.htm">Domains and their Elements</a>.
Note that <code>Representative</code> does not try to <strong>compute</strong> generators of <var>C</var>,
thus <code>Representative</code> may give up and signal an error if <var>C</var> has no
generators stored at all.
<p>
<a name = "I5"></a>
<a name = "SSEC003.8"></a>
<li><code>RepresentativeSmallest( </code><var>C</var><code> ) A</code>
<p>
returns the smallest element in the collection <var>C</var>, w.r.t. the ordering
<code><</code>.
While the operation defaults to comparing all elements,
better methods are installed for some collections.
<p>
<pre>
gap> Representative( Rationals );
1
gap> Representative( [ -1, -2 .. -100 ] );
-1
gap> RepresentativeSmallest( [ -1, -2 .. -100 ] );
-100
</pre>
<p>
<p>
<h2><a name="SECT004">28.4 Operations for Collections</a></h2>
<p><p>
<a name = "SSEC004.1"></a>
<li><code>IsSubset( </code><var>C1</var><code>, </code><var>C2</var><code> ) O</code>
<p>
<code>IsSubset</code> returns <code>true</code> if <var>C2</var>, which must be a collection, is a
<strong>subset</strong> of <var>C1</var>, which also must be a collection, and <code>false</code> otherwise.
<p>
<var>C2</var> is considered a subset of <var>C1</var> if and only if each element of <var>C2</var>
is also an element of <var>C1</var>.
That is <code>IsSubset</code> behaves as if implemented as
<code>IsSubsetSet( AsSSortedList( </code><var>C1</var><code> ), AsSSortedList( </code><var>C2</var><code> ) )</code>,
except that it will also sometimes, but not always,
work for infinite collections,
and that it will usually work much faster than the above definition.
Either argument may also be a proper set (see <a href="CHAP021.htm#SECT019">Sorted Lists and Sets</a>).
<p>
<a name = "I6"></a>
<pre>
gap> IsSubset( Rationals, Integers );
true
gap> IsSubset( Integers, [ 1, 2, 3 ] );
true
gap> IsSubset( Group( (1,2,3,4) ), [ (1,2,3) ] );
false
</pre>
<p>
<a name = "SSEC004.2"></a>
<li><code>Intersection( </code><var>C1</var><code>, </code><var>C2</var><code> ... ) F</code>
<li><code>Intersection( </code><var>list</var><code> ) F</code>
<a name = "SSEC004.2"></a>
<li><code>Intersection2( </code><var>C1</var><code>, </code><var>C2</var><code> ) O</code>
<p>
In the first form <code>Intersection</code> returns the intersection of the
collections <var>C1</var>, <var>C2</var>, etc.
In the second form <var>list</var> must be a <strong>nonempty</strong> list of collections
and <code>Intersection</code> returns the intersection of those collections.
Each argument or element of <var>list</var> respectively may also be a
homogeneous list that is not a proper set,
in which case <code>Intersection</code> silently applies <code>Set</code> (see <a href="CHAP028.htm#SSEC002.6">Set</a>) to it
first.
<p>
The result of <code>Intersection</code> is the set of elements that lie in every of
the collections <var>C1</var>, <var>C2</var>, etc.
If the result is a list then it is mutable and new, i.e., not identical
to any of <var>C1</var>, <var>C2</var>, etc.
<p>
Methods can be installed for the operation <code>Intersection2</code> that takes
only two arguments.
<code>Intersection</code> calls <code>Intersection2</code>.
<p>
Methods for <code>Intersection2</code> should try to maintain as much structure as
possible, for example the intersection of two permutation groups is
again a permutation group.
<p>
<a name = "I7"></a>
<pre>
gap> Intersection( CyclotomicField(9), CyclotomicField(12) )
> # this is one of the rare cases where the intersection of two infinite
> ; # domains works (`CF' is a shorthand for `CyclotomicField')
CF(3)
gap> D12 := Group( (2,6)(3,5), (1,2)(3,6)(4,5) );;
gap> Intersection( D12, Group( (1,2), (1,2,3,4,5) ) );
Group([ (1,5)(2,4) ])
gap> Intersection( D12, [ (1,3)(4,6), (1,2)(3,4) ] )
> ; # note that the second argument is not a proper set
[ (1,3)(4,6) ]
gap> Intersection( D12, [ (), (1,2)(3,4), (1,3)(4,6), (1,4)(5,6) ] )
> # although the result is mathematically a group it is returned as a
> ; # proper set because the second argument is not regarded as a group
[ (), (1,3)(4,6) ]
gap> Intersection( Group( () ), [1,2,3] );
[ ]
gap> Intersection( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] )
> ; # two or more lists or collections as arguments are legal
[ ]
gap> Intersection( [ [1,2,4], [2,3,4], [1,3,4] ] )
> ; # or one list of lists or collections
[ 4 ]
</pre>
<p>
<a name = "SSEC004.3"></a>
<li><code>Union( </code><var>C1</var><code>, </code><var>C2</var><code> ... ) F</code>
<li><code>Union( </code><var>list</var><code> ) F</code>
<a name = "SSEC004.3"></a>
<li><code>Union2( </code><var>C1</var><code>, </code><var>C2</var><code> ) O</code>
<p>
In the first form <code>Union</code> returns the union of the
collections <var>C1</var>, <var>C2</var>, etc.
In the second form <var>list</var> must be a list of collections
and <code>Union</code> returns the union of those collections.
Each argument or element of <var>list</var> respectively may also be a
homogeneous list that is not a proper set,
in which case <code>Union</code> silently applies <code>Set</code> (see <a href="CHAP028.htm#SSEC002.6">Set</a>) to it first.
<p>
The result of <code>Union</code> is the set of elements that lie in any of the
collections <var>C1</var>, <var>C2</var>, etc.
If the result is a list then it is mutable and new, i.e., not identical
to any of <var>C1</var>, <var>C2</var>, etc.
<p>
Methods can be installed for the operation <code>Union2</code> that takes only two
arguments.
<code>Union</code> calls <code>Union2</code>.
<p>
<a name = "I8"></a>
<pre>
gap> Union( [ (1,2,3), (1,2,3,4) ], Group( (1,2,3), (1,2) ) );
[ (), (2,3), (1,2), (1,2,3), (1,2,3,4), (1,3,2), (1,3) ]
gap> Union( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] )
> ; # two or more lists or collections as arguments are legal
[ 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20, 25 ]
gap> Union( [ [1,2,4], [2,3,4], [1,3,4] ] )
> ; # or one list of lists or collections
[ 1, 2, 3, 4 ]
gap> Union( [ ] );
[ ]
</pre>
<p>
<a name = "SSEC004.4"></a>
<li><code>Difference( </code><var>C1</var><code>, </code><var>C2</var><code> ) O</code>
<p>
<code>Difference</code> returns the set difference of the collections <var>C1</var> and <var>C2</var>.
Either argument may also be a homogeneous list that is not a proper set,
in which case <code>Difference</code> silently applies <code>Set</code> (see <a href="CHAP028.htm#SSEC002.6">Set</a>) to it
first.
<p>
The result of <code>Difference</code> is the set of elements that lie in <var>C1</var> but
not in <var>C2</var>.
Note that <var>C2</var> need not be a subset of <var>C1</var>.
The elements of <var>C2</var>, however, that are not elements of <var>C1</var> play no role
for the result.
If the result is a list then it is mutable and new, i.e., not identical
to <var>C1</var> or <var>C2</var>.
<p>
<a name = "I9"></a>
<pre>
gap> Difference( [ (1,2,3), (1,2,3,4) ], Group( (1,2,3), (1,2) ) );
[ (1,2,3,4) ]
</pre>
<p>
<p>
<h2><a name="SECT005">28.5 Membership Test for Collections</a></h2>
<p><p>
<a name = "I10"></a>
<a name = "SSEC005.1"></a>
<li><code></code><var>obj</var><code> in </code><var>C</var><code></code>
<a name = "SSEC005.1"></a>
<li><code>\in( </code><var>obj</var><code>, </code><var>C</var><code> ) O</code>
<p>
returns <code>true</code> if the object <var>obj</var> lies in the collection <var>C</var>,
and <code>false</code> otherwise.
<p>
The infix version of the command calls the operation <code>\in</code>,
for which methods can be installed.
<p>
<pre>
gap> 13 in Integers; [ 1, 2 ] in Integers;
true
false
gap> g:= Group( (1,2) );; (1,2) in g; (1,2,3) in g;
true
false
</pre>
<p>
<p>
<h2><a name="SECT006">28.6 Random Elements</a></h2>
<p><p>
<a name = "I11"></a>
<a name = "SSEC006.1"></a>
<li><code>Random( </code><var>C</var><code> ) O</code>
<li><code>Random( </code><var>list</var><code> ) O</code>
<p>
<code>Random</code> returns a (pseudo-)random element of the collection <var>C</var>
respectively the list <var>list</var>.
<p>
The distribution of elements returned by <code>Random</code> depends on the
argument. For a list <var>list</var>, all elements are equally likely. The same
holds usually for finite collections <var>C</var> that are not lists. For
infinite collections <var>C</var> some reasonable distribution is used.
<p>
See the chapters of the various collections to find out
which distribution is being used.
<p>
For some collections ensuring a reasonable distribution can be
difficult and require substantial runtime.
If speed at the cost of equal distribution is desired,
the operation <code>PseudoRandom</code> should be used instead.
<p>
Note that <code>Random</code> is of course <strong>not</strong> an attribute.
<p>
<pre>
gap> Random(Rationals);
4
gap> g:= Group( (1,2,3) );; Random( g ); Random( g );
(1,3,2)
()
</pre>
<p>
<a name = "SSEC006.2"></a>
<li><code>StateRandom( ) F</code>
<a name = "SSEC006.2"></a>
<li><code>RestoreStateRandom( </code><var>obj</var><code> ) F</code>
<p>
[This interface to the global random generator is kept for compatibility
with older versions of <font face="Gill Sans,Helvetica,Arial">GAP</font>. Use now <code>State(GlobalRandomSource)</code>
and <code>Reset(GlobalRandomSource, </code><var>obj</var><code>)</code> instead.]
<p>
For debugging purposes, it can be desirable to reset the random number
generator to a state it had before. <code>StateRandom</code> returns a <font face="Gill Sans,Helvetica,Arial">GAP</font>
object that represents the current state of the random number generator
used by <code>RandomList</code>.
<p>
By calling <code>RestoreStateRandom</code> with this object as argument, the
random number is reset to this same state.
<p>
(The same result can be obtained by accessing the two global variables
<code>R_N</code> and <code>R_X</code>.)
<p>
(The format of the object used to represent the random generator seed
is not guaranteed to be stable between different machines or versions
of <font face="Gill Sans,Helvetica,Arial">GAP</font>.
<p>
<pre>
gap> seed:=StateRandom();;
gap> List([1..10],i->Random(Integers));
[ -2, 1, -2, -1, 0, 1, 0, 1, -1, 0 ]
gap> List([1..10],i->Random(Integers));
[ 2, 0, 4, -1, -3, 1, -4, -1, 5, -2 ]
gap> RestoreStateRandom(seed);
gap> List([1..10],i->Random(Integers));
[ -5, -2, 0, 1, -2, -1, -3, -2, 0, 0 ]
</pre>
<p>
<a name = "SSEC006.3"></a>
<li><code>PseudoRandom( </code><var>C</var><code> ) O</code>
<li><code>PseudoRandom( </code><var>list</var><code> ) O</code>
<p>
<code>PseudoRandom</code> returns a pseudo random element of the collection <var>C</var>
respectively the list <var>list</var>, which can be roughly described as follows.
For a list <var>list</var>, <code>PseudoRandom</code> returns the same as <code>Random</code>.
For collections <var>C</var> that are not lists,
the elements returned by <code>PseudoRandom</code> are <strong>not</strong> necessarily equally
distributed, even for finite collections <var>C</var>;
the idea is that <code>Random</code> (see <a href="CHAP014.htm#SSEC005.2">Random</a>) returns elements according to
a reasonable distribution, <code>PseudoRandom</code> returns elements that are
cheap to compute but need not satisfy this strong condition, and
<code>Representative</code> (see <a href="CHAP028.htm#SSEC003.7">Representative</a>) returns arbitrary elements,
probably the same element for each call.
<p>
<p>
The method used by <font face="Gill Sans,Helvetica,Arial">GAP</font> to obtain random elements may depend on the
type object.
<p>
Many random methods in the library are eventually based on the function
<code>RandomList</code>. As <code>RandomList</code> is restricted to lists of up to 2<sup>28</sup>
elements, this may create problems for very large collections. Also note
that the method used by <code>RandomList</code> is intended to provide a fast
algorithm rather than to produce high quality randomness for
statistical purposes.
<p>
If you implement your own <code>Random</code> methods we recommend
that they initialize their seed to a defined value when they are loaded
to permit to reproduce calculations even if they involved random
elements.
<p>
<a name = "SSEC006.4"></a>
<li><code>RandomList( </code><var>list</var><code> ) F</code>
<p>
<a name = "I12"></a>
For a dense list <var>list</var> of up to 2<sup>28</sup> elements,
<code>RandomList</code> returns a (pseudo-)random element with equal distribution.
<p>
The algorithm used is an additive number generator (Algorithm A in
section 3.2.2 of <a href="biblio.htm#TACP2"><cite>TACP2</cite></a> with lag 30)
<p>
This random number generator is (deliberately) initialized to the same
values when <font face="Gill Sans,Helvetica,Arial">GAP</font> is started, so different runs of <font face="Gill Sans,Helvetica,Arial">GAP</font> with the same
input will always produce the same result, even if random calculations
are involved.
<p>
See <code>StateRandom</code> for a description on how to reset the random number
generator to a previous state.
<p>
<p>
<h2><a name="SECT007">28.7 Iterators</a></h2>
<p><p>
<a name = "SSEC007.1"></a>
<li><code>Iterator( </code><var>C</var><code> ) O</code>
<li><code>Iterator( </code><var>list</var><code> ) O</code>
<p>
Iterators provide a possibility to loop over the elements of a
(countable) collection <var>C</var> or a list <var>list</var>, without repetition.
For many collections <var>C</var>,
an iterator of <var>C</var> need not store all elements of <var>C</var>,
for example it is possible to construct an iterator of some infinite
domains, such as the field of rational numbers.
<p>
<code>Iterator</code> returns a mutable <strong>iterator</strong> <var>iter</var> for its argument.
If this is a list <var>list</var> (which may contain holes),
then <var>iter</var> iterates over the elements (but not the holes) of <var>list</var> in
the same order (see <a href="CHAP028.htm#SSEC007.6">IteratorList</a> for details).
If this is a collection <var>C</var> but not a list then <var>iter</var> iterates over the
elements of <var>C</var> in an unspecified order,
which may change for repeated calls of <code>Iterator</code>.
Because iterators returned by <code>Iterator</code> are mutable
(see <a href="CHAP012.htm#SECT006">Mutability and Copyability</a>),
each call of <code>Iterator</code> for the same argument returns a <strong>new</strong> iterator.
Therefore <code>Iterator</code> is not an attribute (see <a href="CHAP013.htm#SECT005">Attributes</a>).
<p>
The only operations for iterators are <code>IsDoneIterator</code>,
<code>NextIterator</code>, and <code>ShallowCopy</code>.
In particular, it is only possible to access the next element of the
iterator with <code>NextIterator</code> if there is one, and this can be checked
with <code>IsDoneIterator</code> (see <a href="CHAP028.htm#SSEC007.5">NextIterator</a>).
For an iterator <var>iter</var>, <code>ShallowCopy( </code><var>iter</var><code> )</code> is a mutable iterator
<var>new</var> that iterates over the remaining elements independent of <var>iter</var>;
the results of <code>IsDoneIterator</code> for <var>iter</var> and <var>new</var> are equal,
and if <var>iter</var> is mutable then also the results of <code>NextIterator</code> for
<var>iter</var> and <var>new</var> are equal;
note that <code>=</code> is not defined for iterators,
so the equality of two iterators cannot be checked with <code>=</code>.
<p>
When <code>Iterator</code> is called for a <strong>mutable</strong> collection <var>C</var> then it is not
defined whether <var>iter</var> respects changes to <var>C</var> occurring after the
construction of <var>iter</var>, except if the documentation explicitly promises
a certain behaviour. The latter is the case if the argument is a mutable
list <var>list</var> (see <a href="CHAP028.htm#SSEC007.6">IteratorList</a> for subtleties in this case).
<p>
It is possible to have <code>for</code>-loops run over mutable iterators instead of
lists.
<p>
In some situations, one can construct iterators with a special
succession of elements,
see <a href="CHAP059.htm#SSEC005.6">IteratorByBasis</a> for the possibility to loop over the elements
of a vector space w.r.t. a given basis.
<p>
For lists, <code>Iterator</code> is implemented by <code>IteratorList( </code><var>list</var><code> )</code>.
For collections that are not lists, the default method is
<code>IteratorList( Enumerator( </code><var>C</var><code> ) )</code>.
Better methods depending on <var>C</var> should be provided if possible.
<p>
For random access to the elements of a (possibly infinite) collection,
<strong>enumerators</strong> are used.
See <a href="CHAP021.htm#SECT023">Enumerators</a> for the facility to compute a list from <var>C</var>,
which provides a (partial) mapping from <var>C</var> to the positive integers.
<p>
<pre>
gap> iter:= Iterator( GF(5) );
<iterator>
gap> l:= [];;
gap> for i in iter do Add( l, i ); od; l;
[ 0*Z(5), Z(5)^0, Z(5), Z(5)^2, Z(5)^3 ]
gap> iter:= Iterator( [ 1, 2, 3, 4 ] );; l:= [];;
gap> for i in iter do
> new:= ShallowCopy( iter );
> for j in new do Add( l, j ); od;
> od; l;
[ 2, 3, 4, 3, 4, 4 ]
</pre>
<p>
<a name = "SSEC007.2"></a>
<li><code>IteratorSorted( </code><var>C</var><code> ) O</code>
<li><code>IteratorSorted( </code><var>list</var><code> ) O</code>
<p>
<code>IteratorSorted</code> returns a mutable iterator.
The argument must be a collection <var>C</var> or a list <var>list</var> that is not
necessarily dense but whose elements lie in the same family
(see <a href="CHAP013.htm#SECT001">Families</a>).
It loops over the different elements in sorted order.
<p>
For collections <var>C</var> that are not lists, the generic method is
<code>IteratorList( EnumeratorSorted( </code><var>C</var><code> ) )</code>.
<p>
<a name = "SSEC007.3"></a>
<li><code>IsIterator( </code><var>obj</var><code> ) C</code>
<p>
Every iterator lies in the category <code>IsIterator</code>.
<p>
<a name = "SSEC007.4"></a>
<li><code>IsDoneIterator( </code><var>iter</var><code> ) O</code>
<p>
If <var>iter</var> is an iterator for the list or collection <i>C</i> then
<code>IsDoneIterator( </code><var>iter</var><code> )</code> is <code>true</code> if all elements of <i>C</i> have been
returned already by <code>NextIterator( </code><var>iter</var><code> )</code>, and <code>false</code> otherwise.
<p>
<a name = "SSEC007.5"></a>
<li><code>NextIterator( </code><var>iter</var><code> ) O</code>
<p>
Let <var>iter</var> be a mutable iterator for the list or collection <i>C</i>.
If <code>IsDoneIterator( </code><var>iter</var><code> )</code> is <code>false</code> then <code>NextIterator</code> is
applicable to <var>iter</var>, and the result is the next element of <i>C</i>,
according to the succession defined by <var>iter</var>.
<p>
If <code>IsDoneIterator( </code><var>iter</var><code> )</code> is <code>true</code> then it is not defined what
happens if <code>NextIterator</code> is called for <var>iter</var>;
that is, it may happen that an error is signalled or that something
meaningless is returned, or even that <font face="Gill Sans,Helvetica,Arial">GAP</font> crashes.
<p>
<a name = "SSEC007.6"></a>
<li><code>IteratorList( </code><var>list</var><code> ) F</code>
<p>
<code>IteratorList</code> returns a new iterator that allows iteration over the
elements of the list <var>list</var> (which may have holes) in the same order.
<p>
If <var>list</var> is mutable then it is in principle possible to change <var>list</var>
after the call of <code>IteratorList</code>.
In this case all changes concerning positions that have not yet been
reached in the iteration will also affect the iterator.
For example, if <var>list</var> is enlarged then the iterator will iterate also
over the new elements at the end of the changed list.
<p>
<strong>Note</strong> that changes of <var>list</var> will also affect all shallow copies of
<var>list</var>.
<p>
<a name = "SSEC007.7"></a>
<li><code>TrivialIterator( </code><var>elm</var><code> ) F</code>
<p>
is a mutable iterator for the collection <code>[ </code><var>elm</var><code> ]</code> that consists of
exactly one element <var>elm</var> (see <a href="CHAP028.htm#SSEC003.3">IsTrivial</a>).
<p>
<pre>
gap> iter:= Iterator( [ 1, 2, 3, 4 ] );
<iterator>
gap> sum:= 0;;
gap> while not IsDoneIterator( iter ) do
> sum:= sum + NextIterator( iter );
> od;
gap> IsDoneIterator( iter ); sum;
true
10
gap> ir:= Iterator( Rationals );;
gap> l:= [];; for i in [1..20] do Add( l, NextIterator( ir ) ); od; l;
[ 0, 1, -1, 1/2, 2, -1/2, -2, 1/3, 2/3, 3/2, 3, -1/3, -2/3, -3/2, -3, 1/4,
3/4, 4/3, 4, -1/4 ]
gap> for i in ir do
> if DenominatorRat( i ) > 10 then break; fi;
> od;
gap> i;
1/11
</pre>
<p>
<a name = "SSEC007.8"></a>
<li><code>IteratorByFunctions( </code><var>record</var><code> ) F</code>
<p>
<code>IteratorByFunctions</code> returns a (mutable) iterator <var>iter</var> for which
<code>NextIterator</code>, <code>IsDoneIterator</code>, and <code>ShallowCopy</code>
are computed via prescribed functions.
<p>
Let <var>record</var> be a record with at least the following components.
<p>
<dl compact>
<dt><code>NextIterator</code> <dd>
a function taking one argument <var>iter</var>,
which returns the next element of <var>iter</var> (see <a href="CHAP028.htm#SSEC007.5">NextIterator</a>);
for that, the components of <var>iter</var> are changed,
<p>
<dt><code>IsDoneIterator</code> <dd>
a function taking one argument <var>iter</var>,
which returns <code>IsDoneIterator( </code><var>iter</var><code> )</code> (see <a href="CHAP028.htm#SSEC007.4">IsDoneIterator</a>);
<p>
<dt><code>ShallowCopy</code> <dd>
a function taking one argument <var>iter</var>,
which returns a record for which <code>IteratorByFunctions</code> can be called
in order to create a new iterator that is independent of <var>iter</var> but
behaves like <var>iter</var> w.r.t. the operations <code>NextIterator</code> and
<code>IsDoneIterator</code>.
</dl>
Further (data) components may be contained in <var>record</var> which can be used
by these function.
<p>
<code>IteratorByFunctions</code> does <strong>not</strong> make a shallow copy of <var>record</var>,
this record is changed in place
(see <a href="../prg/CHAP003.htm#SECT008">Creating Objects</a> in ``Programming in <font face="Gill Sans,Helvetica,Arial">GAP</font>'').
<p>
<p>
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP027.htm">Previous</a>] [<a href ="CHAP029.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008
</font></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
170
