A collection in GAP consists of elements in the same family (see 13.1). The most important kinds of collections are homogeneous lists (see 21) and domains (see 12.4). 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.
Basic operations for collections are Size (30.4-6) and Enumerator (30.3-2); for finite collections, Enumerator (30.3-2) admits to delegate the other operations for collections (see 30.4 and 30.5) to functions for lists (see 21). Obviously, special methods depending on the arguments are needed for the computation of e.g. the intersection of two infinite domains.
‣ IsCollection( obj ) | ( category ) |
tests whether an object is a collection.
Some of the functions for lists and collections are described in the chapter about lists, mainly in Section 21.20. In the current chapter, we describe those functions for which the collection aspect
seems to be more important than the list aspect
.
‣ CollectionsFamily( Fam ) | ( attribute ) |
For a family Fam, CollectionsFamily returns the family of all collections over Fam, that is, of all dense lists and domains that consist of objects in Fam.
The NewFamily (13.1-2) call in the standard method of CollectionsFamily is executed with second argument IsCollection (30.1-1), since every object in the collections family must be a collection, and with third argument the collections categories of the involved categories in the implied filter of Fam.
Note that families (see 13.1) are used to describe relations between objects. Important such relations are that between an element e and each collection of elements that lie in the same family as e, and that between two collections whose elements lie in the same family. Therefore, all collections of elements in the family Fam form the new family CollectionsFamily( Fam ).
‣ IsCollectionFamily( obj ) | ( category ) |
is true if Fam is a family of collections, and false otherwise.
‣ ElementsFamily( Fam ) | ( attribute ) |
If Fam is a collections family (see IsCollectionFamily (30.2-2)) then ElementsFamily returns the family from which Fam was created by CollectionsFamily (30.2-1). The way a collections family is created, it always has its elements family stored. If Fam is not a collections family then an error is signalled.
gap> fam:= FamilyObj( (1,2) );; gap> collfam:= CollectionsFamily( fam );; gap> fam = collfam; fam = ElementsFamily( collfam ); false true gap> collfam = FamilyObj( [ (1,2,3) ] ); true gap> collfam = FamilyObj( Group( () ) ); true gap> collfam = CollectionsFamily( collfam ); false
‣ CategoryCollections( filter ) | ( function ) |
Let filter be a filter that is true for all elements of a family Fam, by the construction of Fam. Then CategoryCollections returns the collections category of filter. This is a category that is true for all elements in CollectionsFamily( Fam ).
For example, the construction of PermutationsFamily (42.1-3) guarantees that each of its elements lies in the filter IsPerm (42.1-1), and each collection of permutations (permutation group or dense list of permutations) lies in the category CategoryCollections( IsPerm ). CategoryCollections( IsPerm ). Note that this works only if the collections category is created before the collections family. So it is necessary to construct interesting collections categories immediately after the underlying category has been created.
‣ DeclareCategoryCollections( name ) | ( function ) |
Calls CategoryCollections (30.2-4) on the category that is bound to the global variable with name name to obtain its collections category, and binds the latter to the global variable with name nname. This name is defined as follows: If name is of the form SomethingCollection then nname is set to SomethingCollColl, if name is of the form SomethingColl then nname is set to SomethingCollColl, otherwise we set nname to nameCollection.
The following functions take a list or collection as argument, and return a corresponding list. They differ in whether or not the result is mutable or immutable (see 12.6), guaranteed to be sorted, or guaranteed to admit list access in constant time (see IsConstantTimeAccessList (21.1-6)).
‣ IsListOrCollection( obj ) | ( category ) |
Several functions are defined for both lists and collections, for example Intersection (30.5-2), Iterator (30.8-1), and Random (30.7-1). IsListOrCollection is a supercategory of IsList (21.1-1) and IsCollection (30.1-1) (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.
‣ Enumerator( listorcoll ) | ( attribute ) |
Enumerator returns an immutable list enum. If the argument is a list (which may contain holes), then Length( enum ) is the length of this list, and enum contains the elements (and holes) of this list in the same order. If the argument is a collection that is not a list, then Length( enum ) is the number of different elements of C, and enum contains the different elements of the collection in an unspecified order, which may change for repeated calls of Enumerator. enum[pos] may not execute in constant time (see IsConstantTimeAccessList (21.1-6)), and the size of enum in memory is as small as is feasible.
For lists, the default method is Immutable (12.6-3). For collections that are not lists, there is no default method.
‣ EnumeratorSorted( listorcoll ) | ( attribute ) |
EnumeratorSorted returns an immutable list enum. The argument must be a collection or a list listorcoll which may contain holes but whose elements lie in the same family (see 13.1). Length( enum ) is the number of different elements of the argument, and enum contains the different elements in sorted order, w.r.t. <. enum[pos] may not execute in constant time (see IsConstantTimeAccessList (21.1-6)), and the size of enum in memory is as small as is feasible.
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 ]
‣ EnumeratorByFunctions( D, record ) | ( function ) |
‣ EnumeratorByFunctions( Fam, record ) | ( function ) |
EnumeratorByFunctions returns an immutable, dense, and duplicate-free list enum for which IsBound (21.5-1), element access via \[\] (21.2-1), Length (21.17-5), and Position (21.16-1) are computed via prescribed functions.
Let record be a record with at least the following components.
ElementNumbera function taking two arguments enum and pos, which returns enum[ pos ] (see 21.2); it can be assumed that the argument pos is a positive integer, but pos may be larger than the length of enum (in which case an error must be signalled); note that the result must be immutable since enum itself is immutable,
NumberElementa function taking two arguments enum and elm, which returns Position( enum, elm ) (see Position (21.16-1)); it cannot be assumed that elm is really contained in enum (and fail must be returned if not); note that for the three argument version of Position (21.16-1), the method that is available for duplicate-free lists suffices.
Further (data) components may be contained in record which can be used by these function.
If the first argument is a domain D then enum lists the elements of D (in general enum is not sorted), and methods for Length (21.17-5), IsBound (21.5-1), and PrintObj (6.3-5) may use D.
If one wants to describe the result without creating a domain then the elements are given implicitly by the functions in record, and the first argument must be a family Fam which will become the family of enum; if enum is not homogeneous then Fam must be ListsFamily, otherwise it must be the collections family of any element in enum. In this case, additionally the following component in record is needed.
Lengtha function taking the argument enum, which returns the length of enum (see Length (21.17-5)).
The following components are optional; they are used if they are present but default methods are installed for the case that they are missing.
IsBound\[\]a function taking two arguments enum and k, which returns IsBound( enum[ k ] ) (see 21.2); if this component is missing then Length (21.17-5) is used for computing the result,
Membershipa function taking two arguments elm and enum, which returns true is elm is an element of enum, and false otherwise (see 21.2); if this component is missing then NumberElement is used for computing the result,
AsLista function taking one argument enum, which returns a list with the property that the access to each of its elements will take roughly the same time (see IsConstantTimeAccessList (21.1-6)); if this component is missing then ConstantTimeAccessList (21.17-6) is used for computing the result,
ViewObj and PrintObjtwo functions that print what one wants to be printed when View( enum ) or Print( enum ) is called (see 6.3), if the ViewObj component is missing then the PrintObj method is used as a default.
If the result is known to have additional properties such as being strictly sorted (see IsSSortedList (21.17-4)) 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 EnumeratorByFunctions, and this construction is installed as a method for the operation Enumerator (30.3-2), then it should be installed also as a method for EnumeratorSorted (30.3-3).
Note that it is not checked that EnumeratorByFunctions really returns a dense and duplicate-free list. EnumeratorByFunctions does not make a shallow copy of record, this record is changed in place, see 79.1.
It would be easy to implement a slightly generalized setup for enumerators that need not be duplicate-free (where the three argument version of Position (21.16-1) is supported), but the resulting overhead for the methods seems not to be justified.
‣ List( C ) | ( function ) |
For a collection C (see 30) that is not a list, List returns a new mutable list new such that Length( new ) is the number of different elements of C, and new contains the different elements of C in an unspecified order which may change for repeated calls. new[pos] executes in constant time (see IsConstantTimeAccessList (21.1-6)), and the size of new is proportional to its length. The generic method for this case is ShallowCopy( Enumerator( C ) ).
Developers who wish to adapt this for custom list or collection types need to install suitable methods for the operation ListOp.
gap> l:= List( Group( (1,2,3) ) ); [ (), (1,3,2), (1,2,3) ] gap> IsMutable( l ); IsSortedList( l ); IsConstantTimeAccessList( l ); true false true
(See also List (21.20-18).)
‣ SortedList( listorcoll[, func] ) | ( operation ) |
SortedList returns a new mutable and dense list new. The argument must be a collection or list listorcoll which may contain holes but whose elements lie in the same family (see 13.1). Length( new ) is the number of elements of listorcoll, and new contains the elements in sorted order, w.r.t. < or func if it is specified. For details, please refer to Sort (21.18-1). new[pos] executes in constant time (see IsConstantTimeAccessList (21.1-6)), and the size of new in memory is proportional to its length.
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 ]
‣ SSortedList( listorcoll[, fun] ) | ( operation ) |
‣ Set( C[, fun] ) | ( operation ) |
SSortedList (strictly sorted list
) returns a new dense, mutable, and duplicate free list new. The argument must be a collection or list listorcoll which may contain holes.
If the optional argument fun is not given then Length( new ) is the number of different elements of listorcoll, and new contains the different elements in strictly sorted order, w.r.t. \< (31.11-1). For that, any two entries of listorcoll must be comparable via \< (31.11-1). (Typically, the entries lie in the same family, see 13.1.)
If fun is given then it must be a unary function. In this case, fun is applied to all elements of listorcoll, new contains the different return values in strictly sorted order, and Length( new ) is the number of different such values. For that, any two return values must be comparable via \< (31.11-1).
new[pos] executes in constant time (see IsConstantTimeAccessList (21.1-6)), and the size of new in memory is proportional to its length.
Set is simply a synonym for SSortedList.
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( Group( (1,2,3) ), Order ); [ 1, 3 ] gap> SSortedList( [ 1, 2, 1,, 3, 2 ] ); [ 1, 2, 3 ] gap> SSortedList( [ 1, 2, 1,, 3, 2 ], x -> x^2 ); [ 1, 4, 9 ]
‣ AsList( listorcoll ) | ( attribute ) |
AsList returns a immutable list imm. If the argument is a list (which may contain holes), then Length( imm ) is the Length (21.17-5) value of this list, and imm contains the elements (and holes) of the list in the same order. If the argument is a collection that is not a list, then Length( imm ) is the number of different elements of this collection, and imm contains the different elements of the collection in an unspecified order, which may change for repeated calls of AsList. imm[pos] executes in constant time (see IsConstantTimeAccessList (21.1-6)), and the size of imm in memory is proportional to its length.
If you expect to do many element tests in the resulting list, it might be worth to use a sorted list instead, using AsSSortedList (30.3-10).
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,3,2), (1,3), (1,2,3), (1,2) ]
‣ AsSortedList( listorcoll ) | ( attribute ) |
AsSortedList returns a dense and immutable list imm. The argument must be a collection or list listorcoll which may contain holes but whose elements lie in the same family (see 13.1). Length( imm ) is the number of elements of the argument, and imm contains the elements in sorted order, w.r.t. <=. new[pos] executes in constant time (see IsConstantTimeAccessList (21.1-6)), and the size of imm in memory is proportional to its length.
The only difference to the operation SortedList (30.3-6) is that AsSortedList returns an immutable list.
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
‣ AsSSortedList( listorcoll ) | ( attribute ) |
‣ AsSet( listorcoll ) | ( attribute ) |
AsSSortedList (as strictly sorted list
) returns a dense, immutable, and duplicate free list imm. The argument must be a collection or list listorcoll which may contain holes but whose elements lie in the same family (see 13.1). Length( imm ) is the number of different elements of listorcoll, and imm contains the different elements in strictly sorted order, w.r.t. \< (31.11-1). imm[pos] executes in constant time (see IsConstantTimeAccessList (21.1-6)), and the size of imm in memory is proportional to its length.
Because the comparisons required for sorting can be very expensive for some kinds of objects, you should use AsList (30.3-8) instead if you do not require the result to be sorted.
The only difference to the operation SSortedList (30.3-7) is that AsSSortedList returns an immutable list.
AsSet is simply a synonym for AsSSortedList.
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. AsSSortedList must of course not do this, its only purpose is to create the proper set of elements.
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) ]
‣ Elements( C ) | ( function ) |
Elements does the same as AsSSortedList (30.3-10), that is, the return value is a strictly sorted list of the elements in the list or collection C.
Elements 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 not necessarily sorted, using AsList (30.3-8). If one is really interested in the strictly sorted list of elements in C then one should use AsSet (30.3-10) or AsSSortedList (30.3-10) instead.
‣ IsEmpty( listorcoll ) | ( property ) |
IsEmpty returns true if the collection or list listorcoll is empty (that is it contains no elements), and false otherwise.
‣ IsFinite( C ) | ( property ) |
IsFinite returns true if the collection C is finite, and false otherwise.
The default method for IsFinite checks the size (see Size (30.4-6)) of C.
Methods for IsFinite may call Size (30.4-6), but methods for Size (30.4-6) must not call IsFinite.
‣ IsTrivial( C ) | ( property ) |
IsTrivial returns true if the collection C consists of exactly one element.
‣ IsNonTrivial( C ) | ( property ) |
IsNonTrivial returns true if the collection C is empty or consists of at least two elements (see IsTrivial (30.4-3)).
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
‣ IsWholeFamily( C ) | ( property ) |
IsWholeFamily returns true if the collection C contains the whole family (see 13.1) of its elements.
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
‣ Size( listorcoll ) | ( attribute ) |
Size returns the size of the list or collection listorcoll, which is either an integer or infinity (18.2-1). If the argument is a list then the result is its length (see Length (21.17-5)).
The default method for Size checks the length of an enumerator of listorcoll.
Methods for IsFinite (30.4-2) may call Size, but methods for Size must not call IsFinite (30.4-2).
gap> Size( [1,2,3] ); Size( Group( () ) ); Size( Integers ); 3 1 infinity
‣ Representative( C ) | ( attribute ) |
Representative returns a representative of the collection C.
Note that Representative is free in choosing a representative if there are several elements in C. It is not even guaranteed that Representative returns the same representative if it is called several times for one collection. The main difference between Representative and Random (30.7-1) is that Representative is free to choose a value that is cheap to compute, while Random (30.7-1) must make an effort to randomly distribute its answers.
If C is a domain then there are methods for Representative that try to fetch an element from any known generator list of C, see 31. Note that Representative does not try to compute generators of C, thus Representative may give up and signal an error if C has no generators stored at all.
‣ RepresentativeSmallest( C ) | ( attribute ) |
returns the smallest element in the collection C, w.r.t. the ordering \< (31.11-1). While the operation defaults to comparing all elements, better methods are installed for some collections.
gap> Representative( Rationals ); 0 gap> Representative( [ -1, -2 .. -100 ] ); -1 gap> RepresentativeSmallest( [ -1, -2 .. -100 ] ); -100
‣ IsSubset( C1, C2 ) | ( operation ) |
IsSubset returns true if C2, which must be a collection, is a subset of C1, which also must be a collection, and false otherwise.
C2 is considered a subset of C1 if and only if each element of C2 is also an element of C1. That is IsSubset behaves as if implemented as IsSubsetSet( AsSSortedList( C1 ), AsSSortedList( C2 ) ), 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 21.19).
gap> IsSubset( Rationals, Integers ); true gap> IsSubset( Integers, [ 1, 2, 3 ] ); true gap> IsSubset( Group( (1,2,3,4) ), [ (1,2,3) ] ); false
‣ Intersection( C1, C2, ... ) | ( function ) |
‣ Intersection( list ) | ( function ) |
‣ Intersection2( C1, C2 ) | ( operation ) |
In the first form Intersection returns the intersection of the collections C1, C2, etc. In the second form list must be a nonempty list of collections and Intersection returns the intersection of those collections. Each argument or element of list respectively may also be a homogeneous list that is not a proper set, in which case Intersection silently applies Set (30.3-7) to it first.
The result of Intersection is the set of elements that lie in every of the collections C1, C2, etc. If the result is a list then it is mutable and new, i.e., not identical to any of C1, C2, etc.
Methods can be installed for the operation Intersection2 that takes only two arguments. Intersection calls Intersection2.
Methods for Intersection2 should try to maintain as much structure as possible, for example the intersection of two permutation groups is again a permutation group.
gap> # this is one of the rare cases where the intersection of two gap> # infinite domains works ('CF' is a shorthand for 'CyclotomicField'): gap> Intersection( CyclotomicField(9), CyclotomicField(12) ); 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> # although the result is mathematically a group it is returned as a gap> # proper set because the second argument is not regarded as a group: gap> Intersection( D12, [ (), (1,2)(3,4), (1,3)(4,6), (1,4)(5,6) ] ); [ (), (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 ]
‣ Union( C1, C2, ... ) | ( function ) |
‣ Union( list ) | ( function ) |
‣ Union2( C1, C2 ) | ( operation ) |
In the first form Union returns the union of the collections C1, C2, etc. In the second form list must be a list of collections and Union returns the union of those collections. Each argument or element of list respectively may also be a homogeneous list that is not a proper set, in which case Union silently applies Set (30.3-7) to it first.
The result of Union is the set of elements that lie in any of the collections C1, C2, etc. If the result is a list then it is mutable and new, i.e., not identical to any of C1, C2, etc.
Methods can be installed for the operation Union2 that takes only two arguments. Union calls Union2.
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 .. 4 ] gap> Union( [ ] ); [ ]
When computing the Union of lists or sets of small integers and ranges, every attempt is made to return the result as a range and to avoid expanding ranges provided as input.
‣ Difference( C1, C2 ) | ( operation ) |
Difference returns the set difference of the collections C1 and C2. Either argument may also be a homogeneous list that is not a proper set, in which case Difference silently applies Set (30.3-7) to it first.
The result of Difference is the set of elements that lie in C1 but not in C2. Note that C2 need not be a subset of C1. The elements of C2, however, that are not elements of C1 play no role for the result. If the result is a list then it is mutable and new, i.e., not identical to C1 or C2.
gap> Difference( [ (1,2,3), (1,2,3,4) ], Group( (1,2,3), (1,2) ) ); [ (1,2,3,4) ]
30.6-1 \in‣ \in( obj, C ) | ( operation ) |
returns true if the object obj lies in the collection C, and false otherwise.
The infix version of the command
obj in C
calls the operation \in, for which methods can be installed.
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
The method used by GAP to obtain random elements may depend on the type object.
Most methods which produce random elements in GAP use a global random number generator (see GlobalMersenneTwister (14.7-4)). This random number generator is (deliberately) initialized to the same values when GAP is started, so different runs of GAP with the same input will always produce the same result, even if random calculations are involved.
See Reset (14.7-3) for a description of how to reset the random number generator to a previous state.
‣ Random( listorcoll ) | ( operation ) |
‣ Random( from, to ) | ( operation ) |
Random returns a (pseudo-)random element of the dense, nonempty list or nonempty collection listorcoll. The behaviour for non-dense or empty lists, and for empty collections (see IsDenseList (21.1-2), IsEmpty (30.4-1)) is undefined.
As lists or ranges are restricted in length (2^28-1 or 2^60-1 depending on your system), the second form returns a random integer in the range from to to (inclusive) for arbitrary integers from and to. The behaviour in the case that from is larger than to is undefined.
See Section 14.7 for more about computing random elements, in particular for Random (14.7-2) methods that take a random source as the first argument.
The distribution of elements returned by Random depends on the argument. For a dense, nonempty list the distribution is uniform (all elements are equally likely). The same holds usually for finite collections that are not lists. For infinite collections some reasonable distribution is used.
See the chapters of the various collections to find out which distribution is being used.
For some collections ensuring a reasonable distribution can be difficult and require substantial runtime (for example for large finite groups). If speed is more important than a guaranteed distribution, the operation PseudoRandom (30.7-2) should be used instead.
Note that Random is of course not an attribute.
gap> Random([1..6]); 6 gap> Random(1, 2^100); 866227015645295902682304086250 gap> g:= Group( (1,2,3) );; Random( g ); Random( g ); (1,3,2) () gap> Random(Rationals); -4
‣ PseudoRandom( listorcoll ) | ( operation ) |
PseudoRandom returns a pseudo random element of the list or collection listorcoll, which can be roughly described as follows. For a list, PseudoRandom returns the same as Random (30.7-1). For collections that are not lists, the elements returned by PseudoRandom are not necessarily equally distributed, even for finite collections; the idea is that Random (30.7-1) returns elements according to a reasonable distribution, PseudoRandom returns elements that are cheap to compute but need not satisfy this strong condition, and Representative (30.4-7) returns arbitrary elements, probably the same element for each call.
‣ RandomList( [rs, ]list ) | ( function ) |
For a dense list list, RandomList returns a (pseudo-)random element with equal distribution.
The random source rs (see 14.7) is used to choose a random number. If rs is absent, this function uses the GlobalMersenneTwister (14.7-4) to produce the random elements (a source of high quality random numbers).
gap> RandomList( [ 1 .. 6 ] ); 3 gap> elms:= AsList( Group( (1,2,3) ) );; gap> RandomList( elms ); RandomList( elms ); (1,3,2) (1,2,3) gap> rs:= RandomSource( IsMersenneTwister, 1 ); <RandomSource in IsMersenneTwister> gap> RandomList( rs, elms ); (1,3,2)
‣ Iterator( listorcoll ) | ( operation ) |
‣ IsStandardIterator( listorcoll ) | ( filter ) |
Iterators provide a possibility to loop over the elements of a (countable) collection or list listorcoll, without repetition. For many collections C, an iterator of C need not store all elements of C, for example it is possible to construct an iterator of some infinite domains, such as the field of rational numbers.
Iterator returns a mutable iterator iter for its argument. If this argument is a list (which may contain holes), then iter iterates over the elements (but not the holes) of this list in the same order (see IteratorList (30.8-6) for details). If this argument is a collection but not a list then iter iterates over the elements of this collection in an unspecified order, which may change for repeated calls of Iterator. Because iterators returned by Iterator are mutable (see 12.6), each call of Iterator for the same argument returns a new iterator. Therefore Iterator is not an attribute (see 13.5).
The only operations for iterators are IsDoneIterator (30.8-4), NextIterator (30.8-5), and ShallowCopy (12.7-1). In particular, it is only possible to access the next element of the iterator with NextIterator (30.8-5) if there is one, and this can be checked with IsDoneIterator (30.8-4) For an iterator iter, ShallowCopy (12.7-1) returns a mutable iterator new that iterates over the remaining elements independent of iter; the results of IsDoneIterator (30.8-4) for iter and new are equal, and if iter is mutable then also the results of NextIterator (30.8-5) for iter and new are equal; note that = is not defined for iterators, so the equality of two iterators cannot be checked with =.
When Iterator is called for a mutable collection C then it is not defined whether iter respects changes to C occurring after the construction of iter, except if the documentation explicitly promises a certain behaviour. The latter is the case if the argument is a mutable list (see IteratorList (30.8-6) for subtleties in this case).
It is possible to have for-loops run over mutable iterators instead of lists.
In some situations, one can construct iterators with a special succession of elements, see IteratorByBasis (61.6-6) for the possibility to loop over the elements of a vector space w.r.t. a given basis.
For lists, Iterator is implemented by IteratorList (30.8-6). For collections C that are not lists, the default method is IteratorList( Enumerator( C ) ). Better methods depending on C should be provided if possible.
For random access to the elements of a (possibly infinite) collection, enumerators are used. See 21.23 for the facility to compute a list from C, which provides a (partial) mapping from C to the positive integers.
The filter IsStandardIterator means that the iterator is implemented as a component object and has components IsDoneIterator and NextIterator which are bound to the methods of the operations of the same name for this iterator.
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 ]
‣ IteratorSorted( listorcoll ) | ( operation ) |
IteratorSorted returns a mutable iterator. The argument must be a collection or a list that is not necessarily dense but whose elements lie in the same family (see 13.1). It loops over the different elements in sorted order.
For a collection C that is not a list, the generic method is IteratorList( EnumeratorSorted( C ) ).
‣ IsIterator( obj ) | ( category ) |
Every iterator lies in the category IsIterator.
‣ IsDoneIterator( iter ) | ( operation ) |
If iter is an iterator for the list or collection C then IsDoneIterator( iter ) is true if all elements of C have been returned already by NextIterator( iter ), and false otherwise.
‣ NextIterator( iter ) | ( operation ) |
Let iter be a mutable iterator for the list or collection C. If IsDoneIterator( iter ) is false then NextIterator is applicable to iter, and the result is the next element of C, according to the succession defined by iter.
If IsDoneIterator( iter ) is true then it is not defined what happens when NextIterator is called for iter; that is, it may happen that an error is signalled or that something meaningless is returned, or even that GAP crashes.
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
‣ IteratorList( list ) | ( function ) |
IteratorList returns a new iterator that allows iteration over the elements of the list list (which may have holes) in the same order.
If list is mutable then it is in principle possible to change list after the call of IteratorList. In this case all changes concerning positions that have not yet been reached in the iteration will also affect the iterator. For example, if list is enlarged then the iterator will iterate also over the new elements at the end of the changed list.
Note that changes of list will also affect all shallow copies of list.
‣ TrivialIterator( elm ) | ( function ) |
is a mutable iterator for the collection [ elm ] that consists of exactly one element elm (see IsTrivial (30.4-3)).
‣ IteratorByFunctions( record ) | ( function ) |
IteratorByFunctions returns a (mutable) iterator iter for which NextIterator (30.8-5), IsDoneIterator (30.8-4), and ShallowCopy (12.7-1) are computed via prescribed functions.
Let record be a record with at least the following components.
NextIteratora function taking one argument iter, which returns the next element of iter (see NextIterator (30.8-5)); for that, the components of iter are changed,
IsDoneIteratora function taking one argument iter, which returns the IsDoneIterator (30.8-4) value of iter,
ShallowCopya function taking one argument iter, which returns a record for which IteratorByFunctions can be called in order to create a new iterator that is independent of iter but behaves like iter w.r.t. the operations NextIterator (30.8-5) and IsDoneIterator (30.8-4).
ViewObj and PrintObjtwo functions that print what one wants to be printed when View( iter ) or Print( item ) is called (see 6.3), if the ViewObj component is missing then the PrintObj method is used as a default.
Further (data) components may be contained in record which can be used by these function.
IteratorByFunctions does not make a shallow copy of record, this record is changed in place (see Section 79.1).
Iterators constructed with IteratorByFunctions are in the filter IsStandardIterator (30.8-1).
generated by GAPDoc2HTML