Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

30 Collections

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` ( filter ) | ( 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

then `Something`Collection`nname`

is set to

, if `Something`CollColl`name` is of the form

then `Something`Coll`nname`

is set to

, otherwise we set `Something`CollColl`nname`

to

.`name`Collection

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.

`ElementNumber`

a function taking two arguments

`enum`and`pos`, which returns

(see 21.2); it can be assumed that the argument`enum`[`pos`]`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,`NumberElement`

a function taking two arguments

`enum`and`elm`, which returns`Position(`

(see`enum`,`elm`)`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.

`Length`

a 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(`

(see 21.2); if this component is missing then`enum`[`k`] )`Length`

(21.17-5) is used for computing the result,`Membership`

a 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,`AsList`

a 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`PrintObj`

two functions that print what one wants to be printed when

`View(`

or`enum`)`Print(`

is called (see 6.3), if the`enum`)`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( `

is the number of different elements of `new` )`C`, and `new` contains the different elements of `C` in an unspecified order which may change for repeated calls.

executes in constant time (see `new`[`pos`]`IsConstantTimeAccessList`

(21.1-6)), and the size of `new` is proportional to its length. The generic method for this case is `ShallowCopy( Enumerator( `

.`C` ) )

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-19).)

`‣ 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( `

is the number of elements of `new` )`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).

executes in constant time (see `new`[`pos`]`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( `

is the number of different elements of `new` )`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( `

is the number of different such values. For that, any two return values must be comparable via `new` )`\<`

(31.11-1).

executes in constant time (see `new`[`pos`]`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( `

is the `imm` )`Length`

(21.17-5) value of this list, and `imm` contains the elements (and holes) of of the list in the same order. If the argument is a collection that is not a list, then `Length( `

is the number of different elements of this collection, and `imm` )`imm` contains the different elements of the collection in an unspecified order, which may change for repeated calls of `AsList`

.

executes in constant time (see `imm`[`pos`]`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,2), (1,2,3), (1,3,2), (1,3) ]

`‣ 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( `

is the number of elements of the argument, and `imm` )`imm` contains the elements in sorted order, w.r.t. `<=`

.

executes in constant time (see `new`[`pos`]`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( `

is the number of different elements of `imm` )`listorcoll`, and `imm` contains the different elements in strictly sorted order, w.r.t. `\<`

(31.11-1).

executes in constant time (see `imm`[`pos`]`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( `

, 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).`C1` ), AsSSortedList( `C2` ) )

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 list or collection `listorcoll`.

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 distribution of elements returned by `Random`

depends on the argument. For a 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` 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).

`‣ 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( `

is `iter` )`true`

if all elements of C have been returned already by `NextIterator( `

, and `iter` )`false`

otherwise.

`‣ NextIterator` ( iter ) | ( operation ) |

Let `iter` be a mutable iterator for the list or collection C. If `IsDoneIterator( `

is `iter` )`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( `

is `iter` )`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 `[ `

that consists of exactly one element `elm` ]`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.

`NextIterator`

a 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,`IsDoneIterator`

a function taking one argument

`iter`, which returns the`IsDoneIterator`

(30.8-4) value of`iter`,`ShallowCopy`

a 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`PrintObj`

two functions that print what one wants to be printed when

`View(`

or`iter`)`Print(`

is called (see 6.3), if the`item`)`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).

Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML