21.16 Operations for Lists

In the first form Concatenation returns the concatenation of the lists list1, list2, etc. The concatenation is the list that begins with the elements of list1, followed by the elements of list2, and so on. Each list may also contain holes, in which case the concatenation also contains holes at the corresponding positions.

In the second form list must be a list of lists list1, list2, etc., and Concatenation returns the concatenation of those lists.

The result is a new mutable list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of list1, list2, etc. (see Identical Lists).

Note that Concatenation creates a new list and leaves its arguments unchanged, while Append (see Append) changes its first argument. For computing the union of proper sets, Union can be used, see Union and Sorted Lists and Sets.

gap> Concatenation( [ 1, 2, 3 ], [ 4, 5 ] );
[ 1, 2, 3, 4, 5 ]
gap> Concatenation( [2,3,,5,,7], [11,,13,,,,17,,19] );
[ 2, 3,, 5,, 7, 11,, 13,,,, 17,, 19 ]
gap> Concatenation( [ [1,2,3], [2,3,4], [3,4,5] ] );
[ 1, 2, 3, 2, 3, 4, 3, 4, 5 ]

returns a new mutable list that contains the elements of list in the same order but omitting the holes.

gap> l:=[,1,,,3,,,4,[5,,,6],7];;  Compacted( l );
[ 1, 3, 4, [ 5,,, 6 ], 7 ]

returns a new list new that contains for each element elm of the list list a list of length two, the first element of this is elm itself and the second element is the number of times elm appears in list. The order of those pairs in new corresponds to the ordering of the elements elm, so that the result is sorted.

For all pairs of elements in list the comparison via < must be defined.

gap> Factors( Factorial( 10 ) );
[ 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7 ]
gap> Collected( last );
[ [ 2, 8 ], [ 3, 4 ], [ 5, 2 ], [ 7, 1 ] ]
gap> Collected( last );
[ [ [ 2, 8 ], 1 ], [ [ 3, 4 ], 1 ], [ [ 5, 2 ], 1 ], [ [ 7, 1 ], 1 ] ]

returns a new mutable list whose entries are the elements of the list list with duplicates removed. DuplicateFreeList only uses the = comparison and will not sort the result. Therefore DuplicateFreeList can be used even if the elements of list do not lie in the same family. Unique is an alias for DuplicateFreeList.

gap> l:=[1,Z(3),1,"abc",Group((1,2,3),(1,2)),Z(3),Group((1,2),(2,3))];;
gap> DuplicateFreeList( l );
[ 1, Z(3), "abc", Group( [ (1,2,3), (1,2) ] ) ]

returns the same result as DuplicateFreeList (see DuplicateFreeList), except that the result is immutable.

returns the list of all elements that are contained in the list list or its sublists. That is, Flat first makes a new empty list new. Then it loops over the elements elm of list. If elm is not a list it is added to new, otherwise Flat appends Flat( elm ) to new.

gap> Flat( [ 1, [ 2, 3 ], [ [ 1, 2 ], 3 ] ] );
[ 1, 2, 3, 1, 2, 3 ]
gap> Flat( [ ] );
[ ]

gap> l:=[9..14];;w:=2;; # w is the length of each row
gap> sub:=[1..w];;List([1..Length(l)/w],i->l{(i-1)*w+sub});
[ [ 9, 10 ], [ 11, 12 ], [ 13, 14 ] ]

returns a new mutable list, containing the elements of the dense list list in reversed order.

The argument list is unchanged. The result list is a new list, that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the argument list (see Identical Lists).

gap> Reversed( [ 1, 4, 9, 5, 6, 7 ] );
[ 7, 6, 5, 9, 4, 1 ]

Let list1 and list2 be two dense lists, but not necessarily homogeneous (see IsDenseList, IsHomogeneousList), such that for each i, the entries in both lists at position i can be compared via <. IsLexicographicallyLess returns true if list1 is smaller than list2 w.r.t. lexicographical ordering, and false otherwise.

Apply applies the function func to every element of the dense and mutable list list, and replaces each element entry by the corresponding return value.

Apply changes its argument. The nondestructive counterpart of Apply is List (see List).

gap> l:= [ 1, 2, 3 ];;  Apply( l, i -> i^2 );  l;
[ 1, 4, 9 ]

returns a permutation p of [ 1 .. Length( list1 ) ] such that list1[i^ p] = list2[i]. It returns fail if there is no such permutation.

gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
gap> list2 := [ 4, 1, 7, 5, 5, 6 ];;
gap> perm := PermListList(list1, list2);
(1,2,4)(3,5,6)
gap> Permuted( list2, perm );
[ 5, 4, 6, 1, 7, 5 ]

In the first form Maximum returns the maximum of its arguments, i.e., one argument obj for which obj >= obj1, obj >= obj2 etc. In the second form Maximum takes a homogeneous list list and returns the maximum of the elements in this list.

gap> Maximum( -123, 700, 123, 0, -1000 );
700
gap> Maximum( [ -123, 700, 123, 0, -1000 ] );
700
gap> Maximum( [ 1, 2 ], [ 0, 15 ], [ 1, 5 ], [ 2, -11 ] );
[ 2, -11 ]        # lists are compared elementwise

In the first form Minimum returns the minimum of its arguments, i.e., one argument obj for which obj <= obj1, obj <= obj2 etc. In the second form Minimum takes a homogeneous list list and returns the minimum of the elements in this list.

Note that for both Maximum and Minimum the comparison of the objects obj1, obj2 etc. must be defined; for that, usually they must lie in the same family (see Families).

gap> Minimum( -123, 700, 123, 0, -1000 );
-1000
gap> Minimum( [ -123, 700, 123, 0, -1000 ] );
-1000
gap> Minimum( [ 1, 2 ], [ 0, 15 ], [ 1, 5 ], [ 2, -11 ] );
[ 0, 15 ]

return the maximum resp. the minimum of the elements in the list list. They are the operations called by Maximum resp. Minimum. Methods can be installed for special kinds of lists. For example, there are special methods to compute the maximum resp. the minimum of a range (see Ranges).

In the first form Cartesian returns the cartesian product of the lists list1, list2, etc.

In the second form list must be a list of lists list1, list2, etc., and Cartesian returns the cartesian product of those lists.

The cartesian product is a list cart of lists tup, such that the first element of tup is an element of list1, the second element of tup is an element of list2, and so on. The total number of elements in cart is the product of the lengths of the argument lists. In particular cart is empty if and only if at least one of the argument lists is empty. Also cart contains duplicates if and only if no argument list is empty and at least one contains duplicates.

The last index runs fastest. That means that the first element tup1 of cart contains the first element from list1, from list2 and so on. The second element tup2 of cart contains the first element from list1, the first from list2, an so on, but the last element of tup2 is the second element of the last argument list. This implies that cart is a proper set if and only if all argument lists are proper sets (see Sorted Lists and Sets).

The function Tuples (see Tuples) computes the k-fold cartesian product of a list.

gap> Cartesian( [1,2], [3,4], [5,6] );
[ [ 1, 3, 5 ], [ 1, 3, 6 ], [ 1, 4, 5 ], [ 1, 4, 6 ], [ 2, 3, 5 ],
 [ 2, 3, 6 ], [ 2, 4, 5 ], [ 2, 4, 6 ] ]
gap> Cartesian( [1,2,2], [1,1,2] );
[ [ 1, 1 ], [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 1 ], [ 2, 2 ], 
 [ 2, 1 ], [ 2, 1 ], [ 2, 2 ] ]

returns a new list new that contains the elements of the list list permuted according to the permutation perm. That is new[i ^ perm] = list[i].

Sortex (see Sortex) allows you to compute a permutation that must be applied to a list in order to get the sorted list.

gap> Permuted( [ 5, 4, 6, 1, 7, 5 ], (1,3,5,6,4) );
[ 1, 4, 5, 5, 6, 7 ]

In the first form, where list is a list (not necessarily dense or homogeneous), List returns a new mutable list new that contains the elements (and the holes) of list in the same order; thus List does the same as ShallowCopy (see ShallowCopy) in this case.

In the second form, where C is a collection (see Collections) 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), and the size of new is proportional to its length. The generic method for this case is ShallowCopy( Enumerator( C ) ).

In the third form, for a dense list list and a function func, which must take exactly one argument, List returns a new mutable list new given by new [i] = func ( list [i] ).

gap> List( [1,2,3], i -> i^2 );
[ 1, 4, 9 ]
gap> List( [1..10], IsPrime );
[ false, true, true, false, true, false, true, false, false, false ]

returns a new list that contains those elements of the list list or collection C (see Collections), respectively, for which the unary function func returns true.

If the first argument is a list, the order of the elements in the result is the same as the order of the corresponding elements of list. If an element for which func returns true appears several times in list it will also appear the same number of times in the result. list may contain holes, they are ignored by Filtered.

For each element of list resp. C, func must return either true or false, otherwise an error is signalled.

The result is a new list that is not identical to any other list. The elements of that list however are identical to the corresponding elements of the argument list (see Identical Lists).

List assignment using the operator (see List Assignment) can be used to extract elements of a list according to indices given in another list.

gap> Filtered( [1..20], IsPrime );
[ 2, 3, 5, 7, 11, 13, 17, 19 ]
gap> Filtered( [ 1, 3, 4, -4, 4, 7, 10, 6 ], IsPrimePowerInt );
[ 3, 4, 4, 7 ]
gap> Filtered( [ 1, 3, 4, -4, 4, 7, 10, 6 ],
>              n -> IsPrimePowerInt(n) and n mod 2 <> 0 );
[ 3, 7 ]
gap> Filtered( Group( (1,2), (1,2,3) ), x -> Order( x ) = 2 );
[ (2,3), (1,2), (1,3) ]

In the first form, Number returns the number of bound entries in the list list. For dense lists Number, Length (see Length), and Size (see Size) return the same value; for lists with holes Number returns the number of bound entries, Length returns the largest index of a bound entry, and Size signals an error.

In the last two forms, Number returns the number of elements of the list list resp. the collection C for which the unary function func returns true. If an element for which func returns true appears several times in list it will also be counted the same number of times.

For each element of list resp. C, func must return either true or false, otherwise an error is signalled.

Filtered (see Filtered) allows you to extract the elements of a list that have a certain property.

gap> Number( [ 2, 3, 5, 7 ] );
4
gap> Number( [, 2, 3,, 5,, 7,,,, 11 ] );
5
gap> Number( [1..20], IsPrime );
8
gap> Number( [ 1, 3, 4, -4, 4, 7, 10, 6 ], IsPrimePowerInt );
4
gap> Number( [ 1, 3, 4, -4, 4, 7, 10, 6 ],
>            n -> IsPrimePowerInt(n) and n mod 2 <> 0 );
2
gap> Number( Group( (1,2), (1,2,3) ), x -> Order( x ) = 2 );
3

First returns the first element of the list list for which the unary function func returns true. list may contain holes. func must return either true or false for each element of list, otherwise an error is signalled. If func returns false for all elements of list then First returns fail.

PositionProperty (see PositionProperty) allows you to find the position of the first element in a list that satisfies a certain property.

gap> First( [10^7..10^8], IsPrime );
10000019
gap> First( [10^5..10^6],
>      n -> not IsPrime(n) and IsPrimePowerInt(n) );
100489
gap> First( [ 1 .. 20 ], x -> x < 0 );
fail
gap> First( [ fail ], x -> x = fail );
fail

tests whether the unary function func returns true for all elements in the list list resp. the collection C.

gap> ForAll( [1..20], IsPrime );
false
gap> ForAll( [2,3,4,5,8,9], IsPrimePowerInt );
true
gap> ForAll( [2..14], n -> IsPrimePowerInt(n) or n mod 2 = 0 );
true
gap> ForAll( Group( (1,2), (1,2,3) ), i -> SignPerm(i) = 1 );
false

tests whether the unary function func returns true for at least one element in the list list resp. the collection C.

gap> ForAny( [1..20], IsPrime );
true
gap> ForAny( [2,3,4,5,8,9], IsPrimePowerInt );
true
gap> ForAny( [2..14],
>    n -> IsPrimePowerInt(n) and n mod 5 = 0 and not IsPrime(n) );
false
gap> ForAny( Integers, i ->     i > 0
>                           and ForAll( [0,2..4], j -> IsPrime(i+j) ) );
true

In the first two forms Product returns the product of the elements of the dense list list resp. the collection C (see Collections). In the last two forms Product applies the function func, which must be a function taking one argument, to the elements of the dense list list resp. the collection C, and returns the product of the results. In either case Product returns 1 if the first argument is empty.

If an additional initial value init is given, Product returns the product of init and the elements of the first argument resp. of their images under the function func. This is useful for example if the first argument is empty and a different identity than 1 is desired, in which case init is returned.

gap> Product( [ 2, 3, 5, 7, 11, 13, 17, 19 ] );
9699690
gap> Product( [1..10], x->x^2 );
13168189440000
gap> Product( [ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) ] );
(1,4)(2,3)
gap> Product( GF(8) );
0*Z(2)

In the first two forms Sum returns the sum of the elements of the dense list list resp. the collection C (see Collections). In the last two forms Sum applies the function func, which must be a function taking one argument, to the elements of the dense list list resp. the collection C, and returns the sum of the results. In either case Sum returns 0 if the first argument is empty.

If an additional initial value init is given, Sum returns the sum of init and the elements of the first argument resp. of their images under the function func. This is useful for example if the first argument is empty and a different zero than 0 is desired, in which case init is returned.

gap> Sum( [ 2, 3, 5, 7, 11, 13, 17, 19 ] );
77
gap> Sum( [1..10], x->x^2 );
385
gap> Sum( [ [1,2], [3,4], [5,6] ] );
[ 9, 12 ]
gap> Sum( GF(8) );
0*Z(2)

returns the result of the iterated application of the function func, which must take two arguments, to the elements of the list list. More precisely Iterated returns the result of the following application, f(..f( f( list[1], list[2] ), list[3] ),..,list[n] ).

gap> Iterated( [ 126, 66, 105 ], Gcd );
3

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