28.2 Lists and Collections

Several functions are defined for both lists and collections, for example Intersection (see Intersection), Iterator (see Iterator), and Random (see Random). IsListOrCollection is a supercategory of IsList and IsCollection (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.

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 Mutability and Copyability), guaranteed to be sorted, or guaranteed to admit list access in constant time (see IsConstantTimeAccessList).

Enumerator returns an immutable list enum. If the argument is a list list (which may contain holes), then Length( enum ) is Length( list ), and enum contains the elements (and holes) of list in the same order. If the argument is a collection C that is not a list, then Length( enum ) is the number of different elements of C, and enum contains the different elements of C in an unspecified order, which may change for repeated calls of Enumerator. enum[pos] may not execute in constant time (see IsConstantTimeAccessList), and the size of enum in memory is as small as feasable.

For lists list, the default method is Immutable. For collections C that are not lists, there is no default method.

EnumeratorSorted returns an immutable list enum. The argument must be a collection C or a list list which may contain holes but whose elements lie in the same family (see Families). Length( enum ) is the number of different elements of C resp. list, and enum contains the different elements in sorted order, w.r.t. <. enum[pos] may not execute in constant time (see IsConstantTimeAccessList), and the size of enum in memory is as small as feasable.

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 ]

This function is described in List, 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.

gap> l:= List( Group( (1,2,3) ) );      
[ (), (1,3,2), (1,2,3) ]
gap> IsMutable( l );  IsSortedList( l );  IsConstantTimeAccessList( l );
true
false
true

SortedList returns a new mutable and dense list new. The argument must be a collection C or a list list which may contain holes but whose elements lie in the same family (see Families). Length( new ) is the number of elements of C resp. list, and new contains the elements in sorted order, w.r.t. <=. new[pos] executes in constant time (see IsConstantTimeAccessList), 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 (``strictly sorted list'') returns a new dense, mutable, and duplicate free list new. The argument must be a collection C or a list list which may contain holes but whose elements lie in the same family (see Families). Length( new ) is the number of different elements of C resp. list, and new contains the different elements in strictly sorted order, w.r.t. <. new[pos] executes in constant time (see IsConstantTimeAccessList), 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( [ 1, 2, 1,, 3, 2 ] );
[ 1, 2, 3 ]

AsList returns a immutable list imm. If the argument is a list list (which may contain holes), then Length( imm ) is Length( list ), and imm contains the elements (and holes) of list in the same order. If the argument is a collection C that is not a list, then Length( imm ) is the number of different elements of C, and imm contains the different elements of C in an unspecified order, which may change for repeated calls of AsList. imm[pos] executes in constant time (see IsConstantTimeAccessList), 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.

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 returns a dense and immutable list imm. The argument must be a collection C or a list list which may contain holes but whose elements lie in the same family (see Families). Length( imm ) is the number of elements of C resp. list, and imm contains the elements in sorted order, w.r.t. <=. new[pos] executes in constant time (see IsConstantTimeAccessList), and the size of imm in memory is proportional to its length.

The only difference to the operation SortedList (see SortedList) 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 (``as strictly sorted list'') returns a dense, immutable, and duplicate free list imm. The argument must be a collection C or a list list which may contain holes but whose elements lie in the same family (see Families). Length( imm ) is the number of different elements of C resp. list, and imm contains the different elements in strictly sorted order, w.r.t. <. imm[pos] executes in constant time (see IsConstantTimeAccessList), 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 instead if you do not require the result to be sorted.

The only difference to the operation SSortedList (see SSortedList) 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 does the same as AsSSortedList (see AsSSortedList), 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 (see AsList). If one is really interested in the strictly sorted list of elements in C then one should use AsSet or AsSSortedList instead.

[Top] [Previous] [Up] [Next] [Index]