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

21 Lists

21.16 Finding Positions in Lists

21.16-1 Position

21.16-2 Positions

21.16-3 PositionCanonical

21.16-4 PositionNthOccurrence

21.16-5 PositionSorted

21.16-6 PositionSortedBy

21.16-7 PositionSet

21.16-8 PositionMaximum

21.16-9 PositionProperty

21.16-10 PositionsProperty

21.16-11 PositionBound

21.16-12 PositionsBound

21.16-13 PositionNot

21.16-14 PositionNonZero

21.16-15 PositionSublist

21.16-1 Position

21.16-2 Positions

21.16-3 PositionCanonical

21.16-4 PositionNthOccurrence

21.16-5 PositionSorted

21.16-6 PositionSortedBy

21.16-7 PositionSet

21.16-8 PositionMaximum

21.16-9 PositionProperty

21.16-10 PositionsProperty

21.16-11 PositionBound

21.16-12 PositionsBound

21.16-13 PositionNot

21.16-14 PositionNonZero

21.16-15 PositionSublist

21.20 Operations for Lists

21.20-1 Concatenation

21.20-2 Compacted

21.20-3 Collected

21.20-4 DuplicateFreeList

21.20-5 AsDuplicateFreeList

21.20-6 Flat

21.20-7 Reversed

21.20-8 Shuffle

21.20-9 Apply

21.20-10 Perform

21.20-11 PermListList

21.20-12 Maximum

21.20-13 Minimum

21.20-14 MaximumList and MinimumList

21.20-15 Cartesian

21.20-16 IteratorOfCartesianProduct

21.20-17 Permuted

21.20-18 List

21.20-19 Filtered

21.20-20 Number

21.20-21 First

21.20-22 Last

21.20-23 ForAll

21.20-24 ForAny

21.20-25 Product

21.20-26 Sum

21.20-27 Iterated

21.20-28 ListN

21.20-1 Concatenation

21.20-2 Compacted

21.20-3 Collected

21.20-4 DuplicateFreeList

21.20-5 AsDuplicateFreeList

21.20-6 Flat

21.20-7 Reversed

21.20-8 Shuffle

21.20-9 Apply

21.20-10 Perform

21.20-11 PermListList

21.20-12 Maximum

21.20-13 Minimum

21.20-14 MaximumList and MinimumList

21.20-15 Cartesian

21.20-16 IteratorOfCartesianProduct

21.20-17 Permuted

21.20-18 List

21.20-19 Filtered

21.20-20 Number

21.20-21 First

21.20-22 Last

21.20-23 ForAll

21.20-24 ForAny

21.20-25 Product

21.20-26 Sum

21.20-27 Iterated

21.20-28 ListN

Lists are the most important way to treat objects together. A *list* arranges objects in a definite order. So each list implies a partial mapping from the integers to the elements of the list. I.e., there is a first element of a list, a second, a third, and so on. Lists can occur in mutable or immutable form, see 12.6 for the concept of mutability, and 21.7 for the case of lists.

This chapter deals mainly with the aspect of lists in **GAP** as *data structures*. Chapter 30 tells more about the *collection* aspect of certain lists, and more about lists as *arithmetic objects* can be found in the chapters 23 and 24.

Lists are used to implement ranges (see 21.22), sets (see 21.19), strings (see 27), row vectors and matrices (see 23 and 24, but note that **GAP** supports also linear algebra for objects which are *not* lists, see 26); boolean lists (see 22) are a further special kind of lists.

Several operations for lists, such as `Intersection`

(30.5-2) and `Random`

(30.7-1), will be described in Chapter 30, in particular see 30.3.

A list can be written by writing down the elements in order between square brackets `[`

, `]`

, and separating them with commas `,`

. An *empty list*, i.e., a list with no elements, is written as `[]`

.

gap> [ 1, 2, 3 ]; # a list with three elements [ 1, 2, 3 ] gap> [ [], [ 1 ], [ 1, 2 ] ]; # a list may contain other lists [ [ ], [ 1 ], [ 1, 2 ] ]

Each list constructed this way is mutable (see 12.6).

`‣ IsList` ( obj ) | ( category ) |

tests whether `obj` is a list.

gap> IsList( [ 1, 3, 5, 7 ] ); IsList( 1 ); true false

`‣ IsDenseList` ( obj ) | ( category ) |

A list is *dense* if it has no holes, i.e., contains an element at every position up to the length. It is absolutely legal to have lists with holes. They are created by leaving the entry between the commas empty. Holes at the end of a list are ignored. Lists with holes are sometimes convenient when the list represents a mapping from a finite, but not consecutive, subset of the positive integers.

gap> IsDenseList( [ 1, 2, 3 ] ); true gap> l := [ , 4, 9,, 25,, 49,,,, 121 ];; IsDenseList( l ); false gap> l[3]; 9 gap> l[4]; List Element: <list>[4] must have an assigned value not in any function Entering break read-eval-print loop ... you can 'quit;' to quit to outer loop, or you can 'return;' after assigning a value to continue brk> l[4] := 16;; # assigning a value brk> return; # to escape the break-loop 16 gap>

Observe that requesting the value of `l[4]`

, which was not assigned, caused the entry of a `break`

-loop (see Section 6.4). After assigning a value and typing `return;`

, **GAP** is finally able to comply with our request (by responding with `16`

).

`‣ IsHomogeneousList` ( obj ) | ( category ) |

returns `true`

if `obj` is a list and it is homogeneous, and `false`

otherwise.

A *homogeneous* list is a dense list whose elements lie in the same family (see 13.1). The empty list is homogeneous but not a collection (see 30), a nonempty homogeneous list is also a collection.

gap> IsHomogeneousList( [ 1, 2, 3 ] ); IsHomogeneousList( [] ); true true gap> IsHomogeneousList( [ 1, false, () ] ); false

`‣ IsTable` ( obj ) | ( category ) |

A *table* is a nonempty list of homogeneous lists which lie in the same family. Typical examples of tables are matrices (see 24).

gap> IsTable( [ [ 1, 2 ], [ 3, 4 ] ] ); # in fact a matrix true gap> IsTable( [ [ 1 ], [ 2, 3 ] ] ); # not rectangular but a table true gap> IsTable( [ [ 1, 2 ], [ () , (1,2) ] ] ); # not homogeneous false

`‣ IsRectangularTable` ( list ) | ( property ) |

A list lies in `IsRectangularTable`

when it is nonempty and its elements are all homogeneous lists of the same family and the same length.

`‣ IsConstantTimeAccessList` ( list ) | ( category ) |

This category indicates whether the access to each element of the list `list` will take roughly the same time. This is implied for example by `IsList and IsInternalRep`

, so all strings, Boolean lists, ranges, and internally represented plain lists are in this category.

But also other enumerators (see 21.23) can lie in this category if they guarantee constant time access to their elements.

The basic operations for lists are element access (see 21.3), assignment of elements to a list (see 21.4), fetching the length of a list (see `Length`

(21.17-5)), the test for a hole at a given position, and unbinding an element at a given position (see 21.5).

The term basic operation means that each other list operation can be formulated in terms of the basic operations. (But note that often a more efficient method than this one is implemented.)

Any **GAP** object `list` in the category `IsList`

(21.1-1) is regarded as a list, and if methods for the basic list operations are installed for `list` then `list` can be used also for the other list operations.

For internally represented lists, kernel methods are provided for the basic list operations with positive integer indices. For other lists or other indices, it is possible to install appropriate methods for these operations. This permits the implementation of lists that do not need to store all list elements (see also 21.23); for example, the elements might be described by an algorithm, such as the elements list of a group. For this reduction of space requirements, however, a price in access time may have to be paid (see `ConstantTimeAccessList`

(21.17-6)).

`21.2-1 \[\]`

`‣ \[\]` ( list, ix ) | ( operation ) |

`‣ IsBound\[\]` ( list, ix ) | ( operation ) |

`‣ \[\]\:\=` ( list, pos, ix ) | ( operation ) |

`‣ Unbind\[\]` ( list, ix ) | ( operation ) |

These operations implement element access, test for element boundedness, list element assignment, and removal of the element with index `ix`.

Note that the special characters `[`

, `]`

, `:`

, and `=`

must be escaped with a backslash `\`

(see 4.3); so `\[\]`

denotes the operation for element access in a list, whereas `[]`

denotes an empty list. (Maybe the variable names involving special characters look strange, but nevertheless they are quite suggestive.)

`\[\]( `

is equivalent to `list`, `ix` )

, which clearly will usually be preferred; the former is useful mainly if one wants to access the operation itself, for example if one wants to install a method for element access in a special kind of lists.`list`[ `ix` ]

Similarly, `IsBound\[\]`

is used explicitly mainly in method installations. In other situations, one can simply call `IsBound`

(21.5-1), which then delegates to `IsBound\[\]`

if the first argument is a list, and to `IsBound\.`

(29.7-3) if the first argument is a record.

Analogous statements hold for `\[\]\:\=`

and `Unbind\[\]`

.

`list`[ `ix` ]

The above construct evaluates to the element of the list `list` with index `ix`. For built-in list types and collections, indexing is done with origin 1, i.e., the first element of the list is the element with index 1.

gap> l := [ 2, 3, 5, 7, 11, 13 ];; l[1]; l[2]; l[6]; 2 3 13

If `list` is not a built-in list, or `ix` does not evaluate to a positive integer, method selection is invoked to try and find a way of indexing `list` with index `ix`. If this fails, or the selected method finds that

is unbound, an error is signalled.`list`[`ix`]

`list`{ `poss` }

The above construct evaluates to a new list `new` whose first element is

, whose second element is `list`[`poss`[1]]

, and so on. However, it does not need to be sorted and may contain duplicate elements. If for any \(i\), `list`[`poss`[2]]

\(i\)`list`[ `poss`[`] ]`

is unbound, an error is signalled.

gap> l := [ 2, 3, 5, 7, 11, 13, 17, 19 ];; gap> l{[4..6]}; l{[1,7,1,8]}; [ 7, 11, 13 ] [ 2, 17, 2, 19 ]

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 left operand (see 21.6).

It is possible to nest such *sublist extractions*, as can be seen in the example below.

gap> m := [ [1,2,3], [4,5,6], [7,8,9], [10,11,12] ];; m{[1,2,3]}{[3,2]}; [ [ 3, 2 ], [ 6, 5 ], [ 9, 8 ] ] gap> l := m{[1,2,3]};; l{[3,2]}; [ [ 7, 8, 9 ], [ 4, 5, 6 ] ]

Note the difference between the two examples. The latter extracts elements 1, 2, and 3 from `m` and then extracts the elements 3 and 2 from *this list*. The former extracts elements 1, 2, and 3 from `m` and then extracts the elements 3 and 2 from *each of those element lists*.

To be precise: With each selector `[`

or `pos`]`{`

we associate a `poss`}*level* that is defined as the number of selectors of the form `{`

to its left in the same expression. For example`poss`}

l[pos1]{poss2}{poss3}[pos4]{poss5}[pos6] level 0 0 1 2 2 3

Then a selector

of level `list`[`pos`]`level` is computed as `ListElement(`

, where `list`,`pos`,`level`)`ListElement`

is defined as follows. (Note that `ListElement`

is *not* a **GAP** function.)

ListElement := function ( list, pos, level ) if level = 0 then return list[pos]; else return List( list, elm -> ListElement(elm,pos,level-1) ); fi; end;

and a selector

of level `list`{`poss`}`level` is computed as `ListElements(`

, where `list`,`poss`,`level`)`ListElements`

is defined as follows. (Note that `ListElements`

is *not* a **GAP** function.)

ListElements := function ( list, poss, level ) if level = 0 then return list{poss}; else return List( list, elm -> ListElements(elm,poss,level-1) ); fi; end;

`21.3-1 \{\}`

`‣ \{\}` ( list, poss ) | ( operation ) |

This operation implements *sublist access*. For any list, the default method is to loop over the entries in the list `poss`, and to delegate to the element access operation. (For the somewhat strange variable name, cf. 21.2.)

`list`[ `ix` ] := `object`;

The list element assignment assigns the object `object`, which can be of any type, to the list with index `ix`, in the mutable (see 12.6) list `list`. That means that accessing the `ix`-th element of the list `list` will return `object` after this assignment.

gap> l := [ 1, 2, 3 ];; gap> l[1] := 3;; l; # assign a new object [ 3, 2, 3 ] gap> l[2] := [ 4, 5, 6 ];; l; # <object> may be of any type [ 3, [ 4, 5, 6 ], 3 ] gap> l[ l[1] ] := 10;; l; # <index> may be an expression [ 3, [ 4, 5, 6 ], 10 ]

If the index `ix` is an integer larger than the length of the list `list` (see `Length`

(21.17-5)), the list is automatically enlarged to make room for the new element. Note that it is possible to generate lists with holes that way.

gap> l[4] := "another entry";; l; # <list> is enlarged [ 3, [ 4, 5, 6 ], 10, "another entry" ] gap> l[ 10 ] := 1;; l; # now <list> has a hole [ 3, [ 4, 5, 6 ], 10, "another entry",,,,,, 1 ]

The function `Add`

(21.4-2) should be used if you want to add an element to the end of the list.

Note that assigning to a list changes the list, thus this list must be mutable (see 12.6). See 21.6 for subtleties of changing lists.

If `list` does not evaluate to a list, `pos` does not evaluate to a positive integer, method selection is invoked to try and find a way of indexing `list` with index `pos`. If this fails, or the selected method finds that

is unbound, or if `list`[`pos`]`object` is a call to a function which does not return a value (for example `Print`

) an error is signalled.

`list`{ `poss` } := `objects`;

The sublist assignment assigns the object

, which can be of any type, to the list `objects`[1]`list` at the position

, the object `poss`[1]

to `objects`[2]

, and so on. `list`[`poss`[2]]`poss` must be a dense list of positive integers, it need, however, not be sorted and may contain duplicate elements. `objects` must be a dense list and must have the same length as `poss`.

gap> l := [ 2, 3, 5, 7, 11, 13, 17, 19 ];; gap> l{[1..4]} := [10..13];; l; [ 10, 11, 12, 13, 11, 13, 17, 19 ] gap> l{[1,7,1,10]} := [ 1, 2, 3, 4 ];; l; [ 3, 11, 12, 13, 11, 13, 2, 19,, 4 ]

The next example shows that it is possible to nest such sublist assignments.

gap> m := [ [1,2,3], [4,5,6], [7,8,9], [10,11,12] ];; gap> m{[1,2,3]}{[3,2]} := [ [11,12], [13,14], [15,16] ];; m; [ [ 1, 12, 11 ], [ 4, 14, 13 ], [ 7, 16, 15 ], [ 10, 11, 12 ] ]

The exact behaviour is defined in the same way as for list extractions (see 21.3). Namely, with each selector `[`

or `pos`]`{`

we associate a `poss`}*level* that is defined as the number of selectors of the form `{`

to its left in the same expression. For example`poss`}

l[pos1]{poss2}{poss3}[pos4]{poss5}[pos6] level 0 0 1 1 1 2

Then a list assignment

of level `list`[`pos`] := `vals`;`level` is computed as `ListAssignment( `

, where `list`, `pos`, `vals`, `level` )`ListAssignment`

is defined as follows. (Note that `ListAssignment`

is *not* a **GAP** function.)

ListAssignment := function ( list, pos, vals, level ) local i; if level = 0 then list[pos] := vals; else for i in [1..Length(list)] do ListAssignment( list[i], pos, vals[i], level-1 ); od; fi; end;

and a list assignment

of level `list`{`poss`} := `vals``level` is computed as `ListAssignments( `

, where `list`, `poss`, `vals`, `level` )`ListAssignments`

is defined as follows. (Note that `ListAssignments`

is *not* a **GAP** function.)

ListAssignments := function ( list, poss, vals, level ) local i; if level = 0 then list{poss} := vals; else for i in [1..Length(list)] do ListAssignments( list[i], poss, vals[i], level-1 ); od; fi; end;

`21.4-1 \{\}\:\=`

`‣ \{\}\:\=` ( list, poss, val ) | ( operation ) |

This operation implements sublist assignment. For any list, the default method is to loop over the entries in the list `poss`, and to delegate to the element assignment operation. (For the somewhat strange variable name, cf. 21.2.)

`‣ Add` ( list, obj[, pos] ) | ( operation ) |

adds the element `obj` to the mutable list `list`. The two argument version adds `obj` at the end of `list`, i.e., it is equivalent to the assignment

, see 21.4.`list`[ Length(`list`) + 1 ] := `obj`

The three argument version adds `obj` in position `pos`, moving all later elements of the list (if any) up by one position. Any holes at or after position `pos` are also moved up by one position, and new holes are created before `pos` if they are needed.

Nothing is returned by `Add`

, the function is only called for its side effect.

`‣ Remove` ( list[, pos] ) | ( operation ) |

removes an element from `list`. The one argument form removes the last element. The two argument form removes the element in position `pos`, moving all subsequent elements down one position. Any holes after position `pos` are also moved down by one position.

The one argument form always returns the removed element. In this case `list` must be non-empty.

The two argument form returns the old value of `list`[`pos`] if it was bound, and nothing if it was not. Note that accessing or assigning the return value of this form of the `Remove`

operation is only safe when you *know* that there will be a value, otherwise it will cause an error.

gap> l := [ 2, 3, 5 ];; Add( l, 7 ); l; [ 2, 3, 5, 7 ] gap> Add(l,4,2); l; [ 2, 4, 3, 5, 7 ] gap> Remove(l,2); l; 4 [ 2, 3, 5, 7 ] gap> Remove(l); l; 7 [ 2, 3, 5 ] gap> Remove(l,5); l; [ 2, 3, 5 ]

`‣ CopyListEntries` ( fromlst, fromind, fromstep, tolst, toind, tostep, n ) | ( function ) |

This function copies `n` elements from `fromlst`, starting at position `fromind` and incrementing the position by `fromstep` each time, into `tolst` starting at position `toind` and incrementing the position by `tostep` each time. `fromlst` and `tolst` must be plain lists. `fromstep` and/or `tostep` can be negative. Unbound positions of `fromlst` are simply copied to `tolst`.

`CopyListEntries`

is used in methods for the operations `Add`

(21.4-2) and `Remove`

(21.4-3).

`‣ Append` ( list1, list2 ) | ( operation ) |

adds the elements of the list `list2` to the end of the mutable list `list1`, see 21.4. `list2` may contain holes, in which case the corresponding entries in `list1` will be left unbound. `Append`

returns nothing, it is only called for its side effect.

Note that `Append`

changes its first argument, while `Concatenation`

(21.20-1) creates a new list and leaves its arguments unchanged.

gap> l := [ 2, 3, 5 ];; Append( l, [ 7, 11, 13 ] ); l; [ 2, 3, 5, 7, 11, 13 ] gap> Append( l, [ 17,, 23 ] ); l; [ 2, 3, 5, 7, 11, 13, 17,, 23 ]

`‣ IsBound` ( list[, n] ) | ( operation ) |

`IsBound`

returns `true`

if the list `list` has an element at index `n`, and `false`

otherwise. `list` must evaluate to a list, or to an object for which a suitable method for `IsBound\[\]`

has been installed, otherwise an error is signalled.

gap> l := [ , 2, 3, , 5, , 7, , , , 11 ];; gap> IsBound( l[7] ); true gap> IsBound( l[4] ); false gap> IsBound( l[101] ); false

`‣ GetWithDefault` ( list, n, default ) | ( operation ) |

`GetWithDefault`

returns the `n`th element of the list `list`, if `list` has a value at index `n`, and `default` otherwise.

While this method can be used on any list, it is particularly useful for Weak Pointer lists 86.1 where the value of the list can change.

To distinguish between the `n`th element being unbound, or `default` being in `list`, users can create a new mutable object, such as a string. `IsIdenticalObj`

(12.5-1) returns `false`

for different mutable strings, even if their contents are the same.

gap> l := [1,2,,"a"]; [ 1, 2,, "a" ] gap> newobj := "a"; "a" gap> GetWithDefault(l, 2, newobj); 2 gap> GetWithDefault(l, 3, newobj); "a" gap> GetWithDefault(l, 4, newobj); "a" gap> IsIdenticalObj(GetWithDefault(l, 3, newobj), newobj); true gap> IsIdenticalObj(GetWithDefault(l, 4, newobj), newobj); false

`‣ Unbind` ( list[, n] ) | ( operation ) |

`Unbind`

deletes the element with index `n` in the mutable list `list`. That is, after execution of `Unbind`

, `list` no longer has an assigned value with index `n`. Thus `Unbind`

can be used to produce holes in a list. Note that it is not an error to unbind a nonexistent list element. `list` must evaluate to a list, or to an object for which a suitable method for `Unbind\[\]`

has been installed, otherwise an error is signalled.

gap> l := [ , 2, 3, 5, , 7, , , , 11 ];; gap> Unbind( l[3] ); l; [ , 2,, 5,, 7,,,, 11 ] gap> Unbind( l[4] ); l; [ , 2,,,, 7,,,, 11 ]

Note that `IsBound`

(21.5-1) and `Unbind`

are special in that they do not evaluate their argument, otherwise `IsBound`

(21.5-1) would always signal an error when it is supposed to return `false`

and there would be no way to tell `Unbind`

which component to remove.

With the list assignment (see 21.4) it is possible to change a mutable list. This section describes the semantic consequences of this fact. (See also 12.5.)

First we define what it means when we say that "an object is changed". You may think that in the following example the second assignment changes the integer.

i := 3; i := i + 1;

But in this example it is not the *integer* `3`

which is changed, by adding one to it. Instead the *variable* `i`

is changed by assigning the value of `i+1`

, which happens to be `4`

, to `i`

. The same thing happens in the example below.

l := [ 1, 2 ]; l := [ 1, 2, 3 ];

The second assignment does not change the first list, instead it assigns a new list to the variable `l`

. On the other hand, in the following example the list *is* changed by the second assignment.

l := [ 1, 2 ]; l[3] := 3;

To understand the difference, think of a variable as a name for an object. The important point is that a list can have several names at the same time. An assignment

means in this interpretation that `var`:= `list`;`var` is a name for the object `list`. At the end of the following example `l2`

still has the value `[ 1, 2 ]`

as this list has not been changed and nothing else has been assigned to it.

l1 := [ 1, 2 ]; l2 := l1; l1 := [ 1, 2, 3 ];

But after the following example the list for which `l2`

is a name has been changed and thus the value of `l2`

is now `[ 1, 2, 3 ]`

.

l1 := [ 1, 2 ]; l2 := l1; l1[3] := 3;

We say that two lists are *identical* if changing one of them by a list assignment also changes the other one. This is slightly incorrect, because if *two* lists are identical, there are actually only two names for *one* list. However, the correct usage would be very awkward and would only add to the confusion. Note that two identical lists must be equal, because there is only one list with two different names. Thus identity is an equivalence relation that is a refinement of equality. Identity of objects can be detected using `IsIdenticalObj`

(12.5-1).

Let us now consider under which circumstances two lists are identical.

If you enter a list literal then the list denoted by this literal is a new list that is not identical to any other list. Thus in the following example `l1`

and `l2`

are not identical, though they are equal of course.

l1 := [ 1, 2 ]; l2 := [ 1, 2 ];

Also in the following example, no lists in the list `l`

are identical.

l := []; for i in [1..10] do l[i] := [ 1, 2 ]; od;

If you assign a list to a variable no new list is created. Thus the list value of the variable on the left hand side and the list on the right hand side of the assignment are identical. So in the following example `l1`

and `l2`

are identical lists.

l1 := [ 1, 2 ]; l2 := l1;

If you pass a list as an argument, the old list and the argument of the function are identical. Also if you return a list from a function, the old list and the value of the function call are identical. So in the following example `l1`

and `l2`

are identical lists:

l1 := [ 1, 2 ]; f := function ( l ) return l; end; l2 := f( l1 );

If you change a list it keeps its identity. Thus if two lists are identical and you change one of them, you also change the other, and they are still identical afterwards. On the other hand, two lists that are not identical will never become identical if you change one of them. So in the following example both `l1`

and `l2`

are changed, and are still identical.

l1 := [ 1, 2 ]; l2 := l1; l1[1] := 2;

Here we describe the meaning of `ShallowCopy`

(12.7-1) and `StructuralCopy`

(12.7-2) for lists. For the general definition of these functions, see 12.7.

The subobjects (see `ShallowCopy`

(12.7-1)) of a list are exactly its elements.

This means that for any list `list`, `ShallowCopy`

(12.7-1) returns a mutable *new* list `new` that is *not identical* to any other list (see 21.6), and whose elements are identical to the elements of `list`.

Analogously, for a *mutable* list `list`, `StructuralCopy`

(12.7-2) returns a mutable *new* list `scp` that is *not identical* to any other list, and whose elements are structural copies (defined recursively) of the elements of `list`; an element of `scp` is mutable (and then a *new* list) if and only if the corresponding element of `list` is mutable.

In both cases, modifying the copy `new` resp. `scp` by assignments (see 21.4) does not modify the original object `list`.

`ShallowCopy`

(12.7-1) basically executes the following code for lists.

new := []; for i in [ 1 .. Length( list ) ] do if IsBound( list[i] ) then new[i] := list[i]; fi; od;

gap> list1 := [ [ 1, 2 ], [ 3, 4 ] ];; list2 := ShallowCopy( list1 );; gap> IsIdenticalObj( list1, list2 ); false gap> IsIdenticalObj( list1[1], list2[1] ); true gap> list2[1] := 0;; list1; list2; [ [ 1, 2 ], [ 3, 4 ] ] [ 0, [ 3, 4 ] ]

`StructuralCopy`

(12.7-2) basically executes the following code for lists.

new := []; for i in [ 1 .. Length( list ) ] do if IsBound( list[i] ) then new[i] := StructuralCopy( list[i] ); fi; od;

gap> list1 := [ [ 1, 2 ], [ 3, 4 ] ];; list2 := StructuralCopy( list1 );; gap> IsIdenticalObj( list1, list2 ); false gap> IsIdenticalObj( list1[1], list2[1] ); false gap> list2[1][1] := 0;; list1; list2; [ [ 1, 2 ], [ 3, 4 ] ] [ [ 0, 2 ], [ 3, 4 ] ]

The above code is not entirely correct. If the object `list` contains a mutable object twice this object is not copied twice, as would happen with the above definition, but only once. This means that the copy `new` and the object `list` have exactly the same structure when viewed as a general graph.

gap> sub := [ 1, 2 ];; list1 := [ sub, sub ];; gap> list2 := StructuralCopy( list1 ); [ [ 1, 2 ], [ 1, 2 ] ] gap> list2[1][1] := 0;; list2; [ [ 0, 2 ], [ 0, 2 ] ] gap> list1; [ [ 1, 2 ], [ 1, 2 ] ]

`21.8-1 \in`

`‣ \in` ( obj, list ) | ( operation ) |

This function call or the infix variant `obj` `in`

`list` tests whether there is a positive integer \(i\) such that `list`\([i] =\) `obj` holds.

If the list `list` knows that it is strictly sorted (see `IsSSortedList`

(21.17-4)), the membership test is much quicker, because a binary search can be used instead of the linear search used for arbitrary lists, see `\in`

(21.19-1).

gap> 1 in [ 2, 2, 1, 3 ]; 1 in [ 4, -1, 0, 3 ]; true false gap> s := SSortedList( [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32] );; gap> 17 in s; # uses binary search and only 4 comparisons false

For finding the position of an element in a list, see 21.16.

Section 21.4 told you (among other things) that it is possible to assign beyond the logical end of a mutable list, automatically enlarging the list. This section tells you how this is done for internally represented lists.

It would be extremely wasteful to make all lists large enough so that there is room for all assignments, because some lists may have more than 100000 elements, while most lists have less than 10 elements.

On the other hand suppose every assignment beyond the end of a list would be done by allocating new space for the list and copying all entries to the new space. Then creating a list of 1000 elements by assigning them in order, would take half a million copy operations and also create a lot of garbage that the garbage collector would have to reclaim.

So the following strategy is used. If a list is created it is created with exactly the correct size. If a list is enlarged, because of an assignment beyond the end of the list, it is enlarged by at least

entries. Therefore the next assignments beyond the end of the list do not need to enlarge the list. For example creating a list of 1000 elements by assigning them in order, would now take only 32 enlargements.`length`/8 + 4

The result of this is of course that the *physical length* of a list may be larger than the *logical length*, which is usually called simply the length of the list. Aside from the implications for the performance you need not be aware of the physical length. In fact all you can ever observe, for example by calling `Length`

(21.17-5), is the logical length.

Suppose that `Length`

(21.17-5) would have to take the physical length and then test how many entries at the end of a list are unassigned, to compute the logical length of the list. That would take too much time. In order to make `Length`

(21.17-5), and other functions that need to know the logical length, more efficient, the length of a list is stored along with the list.

For fine tuning code dealing with plain lists we provide the following two functions.

`‣ EmptyPlist` ( len ) | ( function ) |

Returns: a plain list

`‣ ShrinkAllocationPlist` ( l ) | ( function ) |

Returns: nothing

The function `EmptyPlist`

returns an empty plain list which has enough memory allocated for `len` entries. This can be useful for creating and filling a plain list with a known number of entries.

The function `ShrinkAllocationPlist`

gives back to **GAP**'s memory manager the physical memory which is allocated for the plain list `l` but not needed by the current number of entries.

Note that there are similar functions `EmptyString`

(27.4-5) and `ShrinkAllocationString`

(27.4-5) for strings instead of plain lists.

gap> l:=[]; for i in [1..160] do Add(l, i^2); od; [ ] gap> m:=EmptyPlist(160); for i in [1..160] do Add(m, i^2); od; [ ] gap> # now l uses about 25% more memory than the equal list m gap> ShrinkAllocationPlist(l); gap> # now l and m use the same amount of memory

`list1` = `list2`

`list1` <> `list2`

Two lists `list1` and `list2` are equal if and only if for every index \(i\), either both entries `list1`\([i]\) and `list2`\([i]\) are unbound, or both are bound and are equal, i.e., `list1`\([i] =\) `list2`\([i]\) is `true`

.

gap> [ 1, 2, 3 ] = [ 1, 2, 3 ]; true gap> [ , 2, 3 ] = [ 1, 2, ]; false gap> [ 1, 2, 3 ] = [ 3, 2, 1 ]; false

This definition will cause problems with lists which are their own entries. Comparing two such lists for equality may lead to an infinite recursion in the kernel if the list comparison has to compare the list entries which are in fact the lists themselves, and then **GAP** crashes.

`list1` < `list2`

`list1` <= `list2`

Lists are ordered *lexicographically*. Unbound entries are smaller than any bound entry. That implies the following behaviour. Let \(i\) be the smallest positive integer \(i\) such that `list1` and `list2` at position \(i\) differ, i.e., either exactly one of `list1`\([i]\), `list2`\([i]\) is bound or both entries are bound and differ. Then `list1` is less than `list2` if either `list1`\([i]\) is unbound (and `list2`\([i]\) is not) or both are bound and `list1`\([i]\) < `list2`\([i]\) is `true`

.

gap> [ 1, 2, 3, 4 ] < [ 1, 2, 4, 8 ]; # <list1>[3] < <list2>[3] true gap> [ 1, 2, 3 ] < [ 1, 2, 3, 5 ]; # <list1>[4] is unbound and thus < 5 true gap> [ 1, , 3, 4 ] < [ 1, -1, 3 ]; # <list1>[2] is unbound and thus < -1 true

Note that for comparing two lists with `<`

or `<=`

, the (relevant) list elements must be comparable with `<`

, which is usually *not* the case for objects in different families, see 13.1. Also for the possibility to compare lists with other objects, see 13.1.

It is convenient to have arithmetic operations for lists, in particular because in **GAP** row vectors and matrices are special kinds of lists. However, it is the wide variety of list objects because of which we prescribe arithmetic operations *not for all* of them. (Keep in mind that "list" means just an object in the category `IsList`

(21.1-1).)

(Due to the intended generality and flexibility, the definitions given in the following sections are quite technical. But for not too complicated cases such as matrices (see 24.3) and row vectors (see 23.2) whose entries aren't lists, the resulting behaviour should be intuitive.)

For example, we want to deal with matrices which can be added and multiplied in the usual way, via the infix operators `+`

and `*`

; and we want also Lie matrices, with the same additive behaviour but with the multiplication defined by the Lie bracket. Both kinds of matrices shall be lists, with the usual access to their rows, with `Length`

(21.17-5) returning the number of rows etc.

For the categories and attributes that control the arithmetic behaviour of lists, see 21.12.

For the definition of return values of additive and multiplicative operations whose arguments are lists in these filters, see 21.13 and 21.14, respectively. It should be emphasized that these sections describe only what the return values are, and not how they are computed.

For the mutability status of the return values, see 21.15. (Note that this is not dealt with in the sections about the result values.)

Further details about the special cases of row vectors and matrices can be found in 23.2 and in 24.3, the compression status is dealt with in 23.3 and 24.14.

The arithmetic behaviour of lists is controlled by their types. The following categories and attributes are used for that.

Note that we distinguish additive and multiplicative behaviour. For example, Lie matrices have the usual additive behaviour but not the usual multiplicative behaviour.

`‣ IsGeneralizedRowVector` ( list ) | ( category ) |

For a list `list`, the value `true`

for `IsGeneralizedRowVector`

indicates that the additive arithmetic behaviour of `list` is as defined in 21.13, and that the attribute `NestingDepthA`

(21.12-4) will return a nonzero value when called with `list`.

gap> IsList( "abc" ); IsGeneralizedRowVector( "abc" ); true false gap> liemat:= LieObject( [ [ 1, 2 ], [ 3, 4 ] ] ); LieObject( [ [ 1, 2 ], [ 3, 4 ] ] ) gap> IsGeneralizedRowVector( liemat ); true

`‣ IsMultiplicativeGeneralizedRowVector` ( list ) | ( category ) |

For a list `list`, the value `true`

for `IsMultiplicativeGeneralizedRowVector`

indicates that the multiplicative arithmetic behaviour of `list` is as defined in 21.14, and that the attribute `NestingDepthM`

(21.12-5) will return a nonzero value when called with `list`.

gap> IsMultiplicativeGeneralizedRowVector( liemat ); false gap> bas:= CanonicalBasis( FullRowSpace( Rationals, 3 ) ); CanonicalBasis( ( Rationals^3 ) ) gap> IsMultiplicativeGeneralizedRowVector( bas ); true

Note that the filters `IsGeneralizedRowVector`

(21.12-1), `IsMultiplicativeGeneralizedRowVector`

do *not* enable default methods for addition or multiplication (cf. `IsListDefault`

(21.12-3)).

`‣ IsListDefault` ( list ) | ( category ) |

For a list `list`, `IsListDefault`

indicates that the default methods for arithmetic operations of lists, such as pointwise addition and multiplication as inner product or matrix product, shall be applicable to `list`.

`IsListDefault`

implies `IsGeneralizedRowVector`

(21.12-1) and `IsMultiplicativeGeneralizedRowVector`

(21.12-2).

All internally represented lists are in this category, and also all lists in the representations `IsGF2VectorRep`

, `Is8BitVectorRep`

, `IsGF2MatrixRep`

, and `Is8BitMatrixRep`

(see 23.3 and 24.14). Note that the result of an arithmetic operation with lists in `IsListDefault`

will in general be an internally represented list, so most "wrapped list objects" will not lie in `IsListDefault`

.

gap> v:= [ 1, 2 ];; m:= [ v, 2*v ];; gap> IsListDefault( v ); IsListDefault( m ); true true gap> IsListDefault( bas ); IsListDefault( liemat ); true false

`‣ NestingDepthA` ( obj ) | ( attribute ) |

For a **GAP** object `obj`, `NestingDepthA`

returns the *additive nesting depth* of `obj`. This is defined recursively as the integer \(0\) if `obj` is not in `IsGeneralizedRowVector`

(21.12-1), as the integer \(1\) if `obj` is an empty list in `IsGeneralizedRowVector`

(21.12-1), and as \(1\) plus the additive nesting depth of the first bound entry in `obj` otherwise.

`‣ NestingDepthM` ( obj ) | ( attribute ) |

For a **GAP** object `obj`, `NestingDepthM`

returns the *multiplicative nesting depth* of `obj`. This is defined recursively as the integer \(0\) if `obj` is not in `IsMultiplicativeGeneralizedRowVector`

(21.12-2), as the integer \(1\) if `obj` is an empty list in `IsMultiplicativeGeneralizedRowVector`

(21.12-2), and as \(1\) plus the multiplicative nesting depth of the first bound entry in `obj` otherwise.

gap> NestingDepthA( v ); NestingDepthM( v ); 1 1 gap> NestingDepthA( m ); NestingDepthM( m ); 2 2 gap> NestingDepthA( liemat ); NestingDepthM( liemat ); 2 0 gap> l1:= [ [ 1, 2 ], 3 ];; l2:= [ 1, [ 2, 3 ] ];; gap> NestingDepthA( l1 ); NestingDepthM( l1 ); 2 2 gap> NestingDepthA( l2 ); NestingDepthM( l2 ); 1 1

In this general context, we define the results of additive operations only in the following situations. For unary operations (zero and additive inverse), the unique argument must be in `IsGeneralizedRowVector`

(21.12-1); for binary operations (addition and subtraction), at least one argument must be in `IsGeneralizedRowVector`

(21.12-1), and the other either is not a list or also in `IsGeneralizedRowVector`

(21.12-1).

(For non-list **GAP** objects, defining the results of unary operations is not an issue here, and if at least one argument is a list not in `IsGeneralizedRowVector`

(21.12-1), it shall be left to this argument whether the result in question is defined and what it is.)

The zero (see `Zero`

(31.10-3)) of a list \(x\) in `IsGeneralizedRowVector`

(21.12-1) is defined as the list whose entry at position \(i\) is the zero of \(x[i]\) if this entry is bound, and is unbound otherwise.

gap> Zero( [ 1, 2, 3 ] ); Zero( [ [ 1, 2 ], 3 ] ); Zero( liemat ); [ 0, 0, 0 ] [ [ 0, 0 ], 0 ] LieObject( [ [ 0, 0 ], [ 0, 0 ] ] )

The additive inverse (see `AdditiveInverse`

(31.10-9)) of a list \(x\) in `IsGeneralizedRowVector`

(21.12-1) is defined as the list whose entry at position \(i\) is the additive inverse of \(x[i]\) if this entry is bound, and is unbound otherwise.

gap> AdditiveInverse( [ 1, 2, 3 ] ); AdditiveInverse( [ [ 1, 2 ], 3 ] ); [ -1, -2, -3 ] [ [ -1, -2 ], -3 ]

If \(x\) and \(y\) are in `IsGeneralizedRowVector`

(21.12-1) and have the same additive nesting depth (see `NestingDepthA`

(21.12-4)), the sum \(x + y\) is defined *pointwise*, in the sense that the result is a list whose entry at position \(i\) is \(x[i] + y[i]\) if these entries are bound, is a shallow copy (see `ShallowCopy`

(12.7-1)) of \(x[i]\) or \(y[i]\) if the other argument is not bound at position \(i\), and is unbound if both \(x\) and \(y\) are unbound at position \(i\).

If \(x\) is in `IsGeneralizedRowVector`

(21.12-1) and \(y\) is in `IsGeneralizedRowVector`

(21.12-1) and has lower additive nesting depth, or is neither a list nor a domain, the sum \(x + y\) is defined as a list whose entry at position \(i\) is \(x[i] + y\) if \(x\) is bound at position \(i\), and is unbound if not. The equivalent holds in the reversed case, where the order of the summands is kept, as addition is not always commutative.

gap> 1 + [ 1, 2, 3 ]; [ 1, 2, 3 ] + [ 0, 2, 4 ]; [ 1, 2 ] + [ Z(2) ]; [ 2, 3, 4 ] [ 1, 4, 7 ] [ 0*Z(2), 2 ] gap> l1:= [ 1, , 3, 4 ];; l2:= [ , 2, 3, 4, 5 ];; gap> l3:= [ [ 1, 2 ], , [ 5, 6 ] ];; l4:= [ , [ 3, 4 ], [ 5, 6 ] ];; gap> NestingDepthA( l1 ); NestingDepthA( l2 ); 1 1 gap> NestingDepthA( l3 ); NestingDepthA( l4 ); 2 2 gap> l1 + l2; [ 1, 2, 6, 8, 5 ] gap> l1 + l3; [ [ 2, 2, 3, 4 ],, [ 6, 6, 3, 4 ] ] gap> l2 + l4; [ , [ 3, 6, 3, 4, 5 ], [ 5, 8, 3, 4, 5 ] ] gap> l3 + l4; [ [ 1, 2 ], [ 3, 4 ], [ 10, 12 ] ] gap> l1 + []; [ 1,, 3, 4 ]

For two **GAP** objects \(x\) and \(y\) of which one is in `IsGeneralizedRowVector`

(21.12-1) and the other is also in `IsGeneralizedRowVector`

(21.12-1) or is neither a list nor a domain, \(x - y\) is defined as \(x + (-y)\).

gap> l1 - l2; [ 1, -2, 0, 0, -5 ] gap> l1 - l3; [ [ 0, -2, 3, 4 ],, [ -4, -6, 3, 4 ] ] gap> l2 - l4; [ , [ -3, -2, 3, 4, 5 ], [ -5, -4, 3, 4, 5 ] ] gap> l3 - l4; [ [ 1, 2 ], [ -3, -4 ], [ 0, 0 ] ] gap> l1 - []; [ 1,, 3, 4 ]

In this general context, we define the results of multiplicative operations only in the following situations. For unary operations (one and inverse), the unique argument must be in `IsMultiplicativeGeneralizedRowVector`

(21.12-2); for binary operations (multiplication and division), at least one argument must be in `IsMultiplicativeGeneralizedRowVector`

(21.12-2), and the other either not a list or also in `IsMultiplicativeGeneralizedRowVector`

(21.12-2).

(For non-list **GAP** objects, defining the results of unary operations is not an issue here, and if at least one argument is a list not in `IsMultiplicativeGeneralizedRowVector`

(21.12-2), it shall be left to this argument whether the result in question is defined and what it is.)

The one (see `One`

(31.10-2)) of a dense list `x` in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) such that `x` has even multiplicative nesting depth and has the same length as each of its rows is defined as the usual identity matrix on the outer two levels, that is, an identity matrix of the same dimensions, with diagonal entries `One( `

and off-diagonal entries `x`[1][1] )`Zero( `

.`x`[1][1] )

gap> One( [ [ 1, 2 ], [ 3, 4 ] ] ); [ [ 1, 0 ], [ 0, 1 ] ] gap> One( [ [ [ [ 1 ] ], [ [ 2 ] ] ], [ [ [ 3 ] ], [ [ 4 ] ] ] ] ); [ [ [ [ 1 ] ], [ [ 0 ] ] ], [ [ [ 0 ] ], [ [ 1 ] ] ] ]

The inverse (see `Inverse`

(31.10-8)) of an invertible square table `x` in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) whose entries lie in a common field is defined as the usual inverse \(y\), i.e., a square matrix over the same field such that \(\textit{x} y\) and \(y \textit{x}\) is equal to `One( `

.`x` )

gap> Inverse( [ [ 1, 2 ], [ 3, 4 ] ] ); [ [ -2, 1 ], [ 3/2, -1/2 ] ]

There are three possible computations that might be triggered by a multiplication involving a list in `IsMultiplicativeGeneralizedRowVector`

(21.12-2). Namely, \(x * y\) might be

**(I)**the inner product \(x[1] * y[1] + x[2] * y[2] + \cdots + x[n] * y[n]\), where summands are omitted for which the entry in \(x\) or \(y\) is unbound (if this leaves no summand then the multiplication is an error), or

**(L)**the left scalar multiple, i.e., a list whose entry at position \(i\) is \(x * y[i]\) if \(y\) is bound at position \(i\), and is unbound if not, or

**(R)**the right scalar multiple, i.e., a list whose entry at position \(i\) is \(x[i] * y\) if \(x\) is bound at position \(i\), and is unbound if not.

Our aim is to generalize the basic arithmetic of simple row vectors and matrices, so we first summarize the situations that shall be covered.

scl | vec | mat | |

scl | (L) | (L) | |

vec | (R) | (I) | (I) |

mat | (R) | (R) | (R) |

This means for example that the product of a scalar (scl) with a vector (vec) or a matrix (mat) is computed according to (L). Note that this is asymmetric.

Now we can state the general multiplication rules.

If exactly one argument is in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) then we regard the other argument (which is then neither a list nor a domain) as a scalar, and specify result (L) or (R), depending on ordering.

In the remaining cases, both \(x\) and \(y\) are in `IsMultiplicativeGeneralizedRowVector`

(21.12-2), and we distinguish the possibilities by their multiplicative nesting depths. An argument with *odd* multiplicative nesting depth is regarded as a vector, and an argument with *even* multiplicative nesting depth is regarded as a scalar or a matrix.

So if both arguments have odd multiplicative nesting depth, we specify result (I).

If exactly one argument has odd nesting depth, the other is treated as a scalar if it has lower multiplicative nesting depth, and as a matrix otherwise. In the former case, we specify result (L) or (R), depending on ordering; in the latter case, we specify result (L) or (I), depending on ordering.

We are left with the case that each argument has even multiplicative nesting depth. If the two depths are equal, we treat the computation as a matrix product, and specify result (R). Otherwise, we treat the less deeply nested argument as a scalar and the other as a matrix, and specify result (L) or (R), depending on ordering.

gap> [ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ] * (1,4); [ (1,4), (1,4)(2,3), (1,2,4), (1,2,3,4), (1,3,2,4), (1,3,4) ] gap> [ 1, 2, , 4 ] * 2; [ 2, 4,, 8 ] gap> [ 1, 2, 3 ] * [ 1, 3, 5, 7 ]; 22 gap> m:= [ [ 1, 2 ], 3 ];; m * m; [ [ 7, 8 ], [ [ 3, 6 ], 9 ] ] gap> m * m = [ m[1] * m, m[2] * m ]; true gap> n:= [ 1, [ 2, 3 ] ];; n * n; 14 gap> n * n = n[1] * n[1] + n[2] * n[2]; true

For two **GAP** objects \(x\) and \(y\) of which one is in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) and the other is also in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) or is neither a list nor a domain, \(x / y\) is defined as \(x * y^{{-1}}\).

gap> [ 1, 2, 3 ] / 2; [ 1, 2 ] / [ [ 1, 2 ], [ 3, 4 ] ]; [ 1/2, 1, 3/2 ] [ 1, 0 ]

If `x` and `y` are in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) and have the same multiplicative nesting depth (see `NestingDepthM`

(21.12-5)),

is defined `x` mod `y`*pointwise*, in the sense that the result is a list whose entry at position \(i\) is

if these entries are bound, is a shallow copy (see `x`[i] mod `y`[i]`ShallowCopy`

(12.7-1)) of \(x[i]\) or \(y[i]\) if the other argument is not bound at position \(i\), and is unbound if both \(x\) and \(y\) are unbound at position \(i\).

If \(x\) is in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) and \(y\) is in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) and has lower multiplicative nesting depth or is neither a list nor a domain,

is defined as a list whose entry at position \(i\) is `x` mod `y`

if `x`[i] mod `y``x` is bound at position \(i\), and is unbound if not. The equivalent holds in the reversed case, where the order of the arguments is kept.

gap> 4711 mod [ 2, 3,, 5, 7 ]; [ 1, 1,, 1, 0 ] gap> [ 2, 3, 4, 5, 6 ] mod 3; [ 2, 0, 1, 2, 0 ] gap> [ 10, 12, 14, 16 ] mod [ 3, 5, 7 ]; [ 1, 2, 0, 16 ]

For two **GAP** objects \(x\) and \(y\) of which one is in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) and the other is also in `IsMultiplicativeGeneralizedRowVector`

(21.12-2) or is neither a list nor a domain, `LeftQuotient( `

is defined as \(x^{{-1}} * y\).`x`, `y` )

gap> LeftQuotient( [ [ 1, 2 ], [ 3, 4 ] ], [ 1, 2 ] ); [ 0, 1/2 ]

Many results of arithmetic operations, when applied to lists, are again lists, and it is of interest whether their entries are mutable or not (if applicable). Note that the mutability status of the result itself is already defined by the general rule for any result of an arithmetic operation, not only for lists (see 12.6).

However, we do *not* define exactly the mutability status for each element on each level of a nested list returned by an arithmetic operation. (Of course it would be possible to define this recursively, but since the methods used are in general not recursive, in particular for efficient multiplication of compressed matrices, such a general definition would be a burden in these cases.) Instead we consider, for a list \(x\) in `IsGeneralizedRowVector`

(21.12-1), the sequence \(x = x_1, x_2, \ldots x_n\) where \(x_{{i+1}}\) is the first bound entry in \(x_i\) if exists (that is, if \(x_i\) is a nonempty list), and \(n\) is the largest \(i\) such that \(x_i\) lies in `IsGeneralizedRowVector`

(21.12-1). The *immutability level* of \(x\) is defined as infinity if \(x\) is immutable, and otherwise the number of \(x_i\) which are immutable. (So the immutability level of a mutable empty list is \(0\).)

Thus a fully mutable matrix has immutability level \(0\), and a mutable matrix with immutable first row has immutability level \(1\) (independent of the mutability of other rows).

The immutability level of the result of any of the binary operations discussed here is the minimum of the immutability levels of the arguments, provided that objects of the required mutability status exist in **GAP**.

Moreover, the results have a "homogeneous" mutability status, that is, if the first bound entry at nesting depth \(i\) is immutable (mutable) then all entries at nesting depth \(i\) are immutable (mutable, provided that a mutable version of this entry exists in **GAP**).

Thus the sum of two mutable matrices whose first rows are mutable is a matrix all of whose rows are mutable, and the product of two matrices whose first rows are immutable is a matrix all of whose rows are immutable, independent of the mutability status of the other rows of the arguments.

For example, the sum of a matrix (mutable or immutable, i.e., of immutability level one of \(0\), \(1\), or \(2\)) and a mutable row vector (i.e., immutability level \(0\)) is a fully mutable matrix. The product of two mutable row vectors of integers is an integer, and since **GAP** does not support mutable integers, the result is immutable.

For unary arithmetic operations, there are three operations available, an attribute that returns an immutable result (`Zero`

(31.10-3), `AdditiveInverse`

(31.10-9), `One`

(31.10-2), `Inverse`

(31.10-8)), an operation that returns a result that is mutable (`ZeroOp`

(31.10-3), `AdditiveInverseOp`

(31.10-9), `OneOp`

(31.10-2), `InverseOp`

(31.10-8)), and an operation whose result has the same immutability level as the argument (`ZeroSM`

(31.10-3), `AdditiveInverseSM`

(31.10-9), `OneSM`

(31.10-2), `InverseSM`

(31.10-8)). The last kind of operations is equivalent to the corresponding infix operations `0 * `

, `list``- `

, `list`

, and `list`^0

. (This holds not only for lists, see 12.6.)`list`^-1

gap> IsMutable( l1 ); IsMutable( 2 * Immutable( [ 1, 2, 3 ] ) ); true false gap> IsMutable( l2 ); IsMutable( l3 ); true true

An example motivating the mutability rule is the use of syntactic constructs such as

and `obj` * `list``- `

as an elegant and efficient way to create mutable lists needed for further manipulations from mutable lists. In particular one can construct a mutable zero vector of length \(n\) by `list``0 * [ 1 .. `

\(n\)` ]`

. The latter can be done also using `ListWithIdenticalEntries`

(21.15-1).

`‣ ListWithIdenticalEntries` ( n, obj ) | ( function ) |

is a list `list` of length `n` that has the object `obj` stored at each of the positions from `1`

to `n`. Note that all elements of `lists` are identical, see 21.6.

gap> ListWithIdenticalEntries( 10, 0 ); [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

`‣ Position` ( list, obj[, from] ) | ( operation ) |

returns the position of the first occurrence `obj` in `list`, or `fail`

if `obj` is not contained in `list`. If a starting index `from` is given, it returns the position of the first occurrence starting the search *after* position `from`.

Each call to the two argument version is translated into a call of the three argument version, with third argument the integer zero `0`

. (Methods for the two argument version must be installed as methods for the version with three arguments, the third being described by `IsZeroCyc`

.)

gap> Position( [ 2, 2, 1, 3 ], 1 ); 3 gap> Position( [ 2, 1, 1, 3 ], 1 ); 2 gap> Position( [ 2, 1, 1, 3 ], 1, 2 ); 3 gap> Position( [ 2, 1, 1, 3 ], 1, 3 ); fail

`‣ Positions` ( list, obj ) | ( function ) |

returns the set of positions of *all* occurrences of `obj` in `list`.

Developers who wish to adapt this for custom list types need to install suitable methods for the operation `PositionsOp`

.

gap> Positions([1,2,1,2,3,2,2],2); [ 2, 4, 6, 7 ] gap> Positions([1,2,1,2,3,2,2],4); [ ]

`‣ PositionCanonical` ( list, obj ) | ( operation ) |

returns the position of the canonical associate of `obj` in `list`. The definition of this associate depends on `list`. For internally represented lists it is defined as the element itself (and `PositionCanonical`

thus defaults to `Position`

(21.16-1), but for example for certain enumerators (see 21.23) other canonical associates can be defined.

For example `RightTransversal`

(39.8-1) defines the canonical associate to be the element in the transversal defining the same coset of a subgroup in a group.

gap> g:=Group((1,2,3,4),(1,2));;u:=Subgroup(g,[(1,2)(3,4),(1,3)(2,4)]);; gap> rt:=RightTransversal(g,u);;AsList(rt); [ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4) ] gap> Position(rt,(1,2)); fail gap> PositionCanonical(rt,(1,2)); 2

`‣ PositionNthOccurrence` ( list, obj, n ) | ( operation ) |

returns the position of the `n`-th occurrence of `obj` in `list` and returns `fail`

if `obj` does not occur `n` times.

gap> PositionNthOccurrence([1,2,3,2,4,2,1],1,1); 1 gap> PositionNthOccurrence([1,2,3,2,4,2,1],1,2); 7 gap> PositionNthOccurrence([1,2,3,2,4,2,1],2,3); 6 gap> PositionNthOccurrence([1,2,3,2,4,2,1],2,4); fail

`‣ PositionSorted` ( list, elm[, func] ) | ( function ) |

Called with two arguments, `PositionSorted`

returns the position of the element `elm` in the sorted list `list`.

Called with three arguments, `PositionSorted`

returns the position of the element `elm` in the list `list`, which must be sorted with respect to `func`. `func` must be a function of two arguments that returns `true`

if the first argument is less than the second argument, and `false`

otherwise.

`PositionSorted`

returns `pos` such that \(\textit{list}[\textit{pos}-1] < \textit{elm} \leq \textit{list}[\textit{pos}]\) holds. That means, if `elm` appears once in `list`, its position is returned. If `elm` appears several times in `list`, the position of the first occurrence is returned. If `elm` is not an element of `list`, the index where `elm` must be inserted to keep the list sorted is returned.

`PositionSorted`

uses binary search, whereas `Position`

(21.16-1) can in general use only linear search, see the remark at the beginning of 21.19. For sorting lists, see 21.18, for testing whether a list is sorted, see `IsSortedList`

(21.17-3) and `IsSSortedList`

(21.17-4).

Developers who wish to adapt this for custom list types need to install suitable methods for the operation `PositionSortedOp`

.

gap> PositionSorted( [1,4,5,5,6,7], 0 ); 1 gap> PositionSorted( [1,4,5,5,6,7], 2 ); 2 gap> PositionSorted( [1,4,5,5,6,7], 4 ); 2 gap> PositionSorted( [1,4,5,5,6,7], 5 ); 3 gap> PositionSorted( [1,4,5,5,6,7], 8 ); 7

`‣ PositionSortedBy` ( list, val, func ) | ( function ) |

This function returns the same value that would be returned by `PositionSorted(List(list, func), val)`

, but computes it in a more efficient way.

To be more precise, `func` must be a function on one argument which returns values that can be compared to `val`, and `list` must be a list for which `func(list[i]) <= func(list[i+1])`

holds for all relevant `i`. This property is not verified, and if the input violates it, then the result is undefined.

`PositionSortedBy`

returns `pos` such that \(\textit{func}(\textit{list}[\textit{pos}-1]) < \textit{val} \leq \textit{func}(\textit{list}[\textit{pos}])\) holds. That means, if there are elements `elm`

in `list` for which \(\textit{func}(elm) = \textit{val}\) holds, then the position of the first such element is returned. If no element of `list` satisfies this condition, then the lowest index where an element `elm` satisfying \(\textit{func}(elm) = \textit{val}\) must be inserted to preserve the property `func(list[i]) <= func(list[i+1])`

is returned.

`PositionSortedBy`

uses binary search. Each `func(list[i])`

is computed at most once.

Developers who wish to adapt this for custom list types need to install suitable methods for the operation `PositionSortedByOp`

.

gap> PositionSortedBy( [ "", "ab", ], -1, Length ); 1 gap> PositionSortedBy( [ "", "ab", ], 0, Length ); 1 gap> PositionSortedBy( [ "", "ab", ], 1, Length ); 2 gap> PositionSortedBy( [ "", "ab", ], 2, Length ); 2 gap> PositionSortedBy( [ "", "ab", ], 3, Length ); 3

`‣ PositionSet` ( list, obj[, func] ) | ( function ) |

`PositionSet`

is a slight variation of `PositionSorted`

(21.16-5). The only difference to `PositionSorted`

(21.16-5) is that `PositionSet`

returns `fail`

if `obj` is not in `list`.

gap> PositionSet( [1,4,5,5,6,7], 0 ); fail gap> PositionSet( [1,4,5,5,6,7], 2 ); fail gap> PositionSet( [1,4,5,5,6,7], 4 ); 2 gap> PositionSet( [1,4,5,5,6,7], 5 ); 3 gap> PositionSet( [1,4,5,5,6,7], 8 ); fail

`‣ PositionMaximum` ( list[, func] ) | ( function ) |

`‣ PositionMinimum` ( list[, func] ) | ( function ) |

returns the position of maximum (with `PositionMaximum`

) or minimum (with `PositionMinimum`

) entry in the list `list`. If a second argument `func` is passed, then return instead the position of the largest/smallest entry in `List( `

. If several entries of the list are equal to the maximum/minimum, the first such position is returned.`list` , `func` )

gap> PositionMaximum( [2,4,-6,2,4] ); 2 gap> PositionMaximum( [2,4,-6,2,4], x -> -x); 3 gap> PositionMinimum( [2,4,-6,2,4] ); 3 gap> PositionMinimum( [2,4,-6,2,4], x -> -x); 2

`Maximum`

(21.20-12) and `Minimum`

(21.20-13) allow you to find the maximum or minimum element of a list directly.

`‣ PositionProperty` ( list, func[, from] ) | ( operation ) |

returns the position of the first entry in the list `list` for which the property tester function `func` returns `true`

, or `fail`

if no such entry exists. If a starting index `from` is given, it returns the position of the first entry satisfying `func`, starting the search *after* position `from`.

gap> PositionProperty( [10^7..10^8], IsPrime ); 20 gap> PositionProperty( [10^5..10^6], > n -> not IsPrime(n) and IsPrimePowerInt(n) ); 490

`First`

(21.20-21) allows you to extract the first element of a list that satisfies a certain property.

`‣ PositionsProperty` ( list, func ) | ( operation ) |

returns the set of all those positions in the list `list` which are bound and for which the property tester function `func` returns `true`

.

gap> l:= [ -5 .. 5 ];; gap> PositionsProperty( l, IsPosInt ); [ 7, 8, 9, 10, 11 ] gap> PositionsProperty( l, IsPrimeInt ); [ 1, 3, 4, 8, 9, 11 ]

`PositionProperty`

(21.16-9) allows you to extract the position of the first element in a list that satisfies a certain property.

`‣ PositionBound` ( list ) | ( operation ) |

returns the first bound position of the list `list`. For the empty list it returns `fail`

.

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

`‣ PositionsBound` ( list ) | ( function ) |

returns the set of all bound positions in the list `list`.

gap> PositionsBound([1,2,3]); [ 1 .. 3 ] gap> PositionsBound([,1,,3]); [ 2, 4 ] gap> PositionsBound([]); []

`‣ PositionNot` ( list, val[, from] ) | ( operation ) |

For a list `list` and an object `val`, `PositionNot`

returns the smallest nonnegative integer \(n\) such that \(\textit{list}[n]\) is either unbound or not equal to `val`. If a starting index `from` is given, it returns the first position with this property starting the search *after* position `from`.

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

`‣ PositionNonZero` ( vec[, from] ) | ( operation ) |

For a row vector `vec`, `PositionNonZero`

returns the position of the first non-zero element of `vec`, or `Length(`

`vec` `)+1`

if all entries of `vec` are zero.

If a starting index `from` is given, it returns the position of the first occurrence starting the search *after* position `from`.

`PositionNonZero`

implements a special case of `PositionNot`

(21.16-13). Namely, the element to be avoided is the zero element, and the list must be (at least) homogeneous because otherwise the zero element cannot be specified implicitly.

gap> PositionNonZero( [ 1, 1, 2, 3, 2 ] ); 1 gap> PositionNonZero( [ 2, 3, 4, 5 ] * Z(2) ); 2

`‣ PositionSublist` ( list, sub[, from] ) | ( operation ) |

returns the smallest index in the list `list` at which a sublist equal to `sub` starts. If `sub` does not occur the operation returns `fail`

. The version with given `from` starts searching *after* position `from`.

To determine whether `sub` matches `list` at a particular position, use `IsMatchingSublist`

(21.17-1) instead.

A list that contains mutable objects (like lists or records) *cannot* store attribute values that depend on the values of its entries, such as whether it is homogeneous, sorted, or strictly sorted, as changes in any of its entries could change such property values, like the following example shows.

gap> l:=[[1],[2]]; [ [ 1 ], [ 2 ] ] gap> IsSSortedList(l); true gap> l[1][1]:=3; 3 gap> IsSSortedList(l); false

For such lists these property values must be computed anew each time the property is asked for. For example, if `list` is a list of mutable row vectors then the call of `Position`

(21.16-1) with `list` as first argument cannot take advantage of the fact that `list` is in fact sorted. One solution is to call explicitly `PositionSorted`

(21.16-5) in such a situation, another solution is to replace `list` by an immutable copy using `Immutable`

(12.6-3).

`‣ IsMatchingSublist` ( list, sub[, at] ) | ( operation ) |

returns `true`

if `sub` matches a sublist of `list` from position `1`

(or position `at`, in the case of three arguments), or `false`

, otherwise. If `sub` is empty `true`

is returned. If `list` is empty but `sub` is non-empty `false`

is returned.

If you actually want to know whether there is an `at` for which `IsMatchingSublist( `

is true, use a construction like `list`, `sub`, `at` )`PositionSublist( `

instead (see `list`, `sub` ) <> fail`PositionSublist`

(21.16-15)); it's more efficient.

`‣ IsDuplicateFree` ( obj ) | ( property ) |

`‣ IsDuplicateFreeList` ( obj ) | ( filter ) |

`IsDuplicateFree`

returns `true`

if `obj` is both a list or collection, and it is duplicate free; otherwise it returns `false`

. `IsDuplicateFreeList`

is a synonym for `IsDuplicateFree and IsList`

.

A list is *duplicate free* if it is dense and does not contain equal entries in different positions. Every domain (see 12.4) is duplicate free.

Note that **GAP** cannot compare arbitrary objects (by equality). This can cause that `IsDuplicateFree`

runs into an error, if `obj` is a list with some non-comparable entries.

`‣ IsSortedList` ( obj ) | ( property ) |

returns `true`

if `obj` is a list and it is sorted, and `false`

otherwise.

A list `list` is *sorted* if it is dense (see `IsDenseList`

(21.1-2)) and satisfies the relation \(\textit{list}[i] \leq \textit{list}[j]\) whenever \(i < j\). Note that a sorted list is not necessarily duplicate free (see `IsDuplicateFree`

(21.17-2) and `IsSSortedList`

(21.17-4)).

Many sorted lists are in fact homogeneous (see `IsHomogeneousList`

(21.1-3)), but also non-homogeneous lists may be sorted (see 31.11).

In sorted lists, membership test and computing of positions can be done by binary search, see 21.19.

Note that **GAP** cannot compare (by less than) arbitrary objects. This can cause that `IsSortedList`

runs into an error, if `obj` is a list with some non-comparable entries.

`‣ IsSSortedList` ( obj ) | ( property ) |

`‣ IsSet` ( obj ) | ( property ) |

returns `true`

if `obj` is a list and it is strictly sorted, and `false`

otherwise. `IsSSortedList`

is short for "is strictly sorted list"; `IsSet`

is just a synonym for `IsSSortedList`

.

A list `list` is *strictly sorted* if it is sorted (see `IsSortedList`

(21.17-3)) and satisfies the relation \(\textit{list}[i] < \textit{list}[j]\) whenever \(i < j\). In particular, such lists are duplicate free (see `IsDuplicateFree`

(21.17-2)).

(Currently there is little special treatment of lists that are sorted but not strictly sorted. In particular, internally represented lists will *not* store that they are sorted but not strictly sorted.)

Note that **GAP** cannot compare (by less than) arbitrary objects. This can cause that `IsSSortedList`

runs into an error, if `obj` is a list with some non-comparable entries.

`‣ Length` ( list ) | ( attribute ) |

returns the *length* of the list `list`, which is defined to be the index of the last bound entry in `list`.

`‣ ConstantTimeAccessList` ( list ) | ( attribute ) |

`ConstantTimeAccessList`

returns an immutable list containing the same elements as the list `list` (which may have holes) in the same order. If `list` is already a constant time access list, `ConstantTimeAccessList`

returns an immutable copy of `list` directly. Otherwise it puts all elements and holes of `list` into a new list and makes that list immutable.

GAP implements three different families of sorting algorithms. The default algorithm is pattern-defeating quicksort, a variant of quicksort which performs better on partially sorted lists and has good worst-case behaviour. The functions which begin `Stable`

are stable (equal elements keep the same relative order in the sorted list) and use merge sort. Finally, the functions which begin `Shell`

use the shell sort which was GAP's default search algorithm before 4.9. `Sortex`

(21.18-3) and `SortingPerm`

(21.18-4) are also stable.

`‣ Sort` ( list[, func] ) | ( operation ) |

`‣ SortBy` ( list, func ) | ( operation ) |

`‣ StableSort` ( list[, func] ) | ( operation ) |

`‣ StableSortBy` ( list[, func] ) | ( operation ) |

`Sort`

sorts the list `list` in increasing order. In the one argument form `Sort`

uses the operator `<`

to compare the elements. (If the list is not homogeneous it is the user's responsibility to ensure that `<`

is defined for all element pairs, see 31.11) In the two argument form `Sort`

uses the function `func` to compare elements. `func` must be a function taking two arguments that returns `true`

if the first is regarded as strictly smaller than the second, and `false`

otherwise.

`StableSort`

behaves identically to `Sort`

, except that `StableSort`

will keep elements which compare equal in the same relative order, while `Sort`

may change their relative order.

`Sort`

does not return anything, it just changes the argument `list`. Use `ShallowCopy`

(12.7-1) if you want to keep `list`. Use `Reversed`

(21.20-7) if you want to get a new list that is sorted in decreasing order.

`SortBy`

sorts the list `list` into an order such that `func(list[i]) <= func(list[i+1])`

for all relevant `i`. `func` must thus be a function on one argument which returns values that can be compared. Each `func(list[i])`

is computed just once and stored, making this more efficient than using the two-argument version of `Sort`

in many cases.

`StableSortBy`

behaves the same as `SortBy`

except that, like `StableSort`

, it keeps pairs of values which compare equal when `func`

is applied to them in the same relative order.

gap> list := [ 5, 4, 6, 1, 7, 5 ];; Sort( list ); list; [ 1, 4, 5, 5, 6, 7 ] gap> SortBy(list, x -> x mod 3); gap> list; # Sorted by mod 3 [ 6, 1, 4, 7, 5, 5] gap> list := [ [0,6], [1,2], [1,3], [1,5], [0,4], [3,4] ];; gap> Sort( list, function(v,w) return v*v < w*w; end ); gap> list; # sorted according to the Euclidean distance from [0,0] [ [ 1, 2 ], [ 1, 3 ], [ 0, 4 ], [ 3, 4 ], [ 1, 5 ], [ 0, 6 ] ] gap> SortBy( list, function(v) return v[1] + v[2]; end ); gap> list; # sorted according to Manhattan distance from [0,0] [ [ 1, 2 ], [ 1, 3 ], [ 0, 4 ], [ 1, 5 ], [ 0, 6 ], [ 3, 4 ] ] gap> list := [ [0,6], [1,3], [3,4], [1,5], [1,2], [0,4], ];; gap> Sort( list, function(v,w) return v[1] < w[1]; end ); gap> # note the random order of the elements with equal first component: gap> list; [ [ 0, 6 ], [ 0, 4 ], [ 1, 3 ], [ 1, 5 ], [ 1, 2 ], [ 3, 4 ] ]

`‣ SortParallel` ( list1, list2[, func] ) | ( operation ) |

`‣ StableSortParallel` ( list1, list2[, func] ) | ( operation ) |

`SortParallel`

sorts the list `list1` in increasing order just as `Sort`

(21.18-1) does. In parallel it applies the same exchanges that are necessary to sort `list1` to the list `list2`, which must of course have at least as many elements as `list1` does.

`StableSortParallel`

behaves identically to `SortParallel`

, except it keeps elements in `list1` which compare equal in the same relative order.

gap> list1 := [ 5, 4, 6, 1, 7, 5 ];; gap> list2 := [ 2, 3, 5, 7, 8, 9 ];; gap> SortParallel( list1, list2 ); gap> list1; [ 1, 4, 5, 5, 6, 7 ] gap> list2; [ 7, 3, 2, 9, 5, 8 ]

Note that `[ 7, 3, 2, 9, 5, 8 ]`

or `[ 7, 3, 9, 2, 5, 8 ]`

are possible results. `StableSortParallel`

will always return `[ 7, 3, 2, 9, 5, 8]`

.

`‣ Sortex` ( list[, func] ) | ( operation ) |

sorts the list `list` and returns a permutation that can be applied to `list` to obtain the sorted list. The one argument form sorts via the operator `<`

, the two argument form sorts w.r.t. the function `func`. The permutation returned by `Sortex`

will keep elements which compare equal in the same relative order. (If the list is not homogeneous it is the user's responsibility to ensure that `<`

is defined for all element pairs, see 31.11)

`Permuted`

(21.20-17) allows you to rearrange a list according to a given permutation.

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

`‣ SortingPerm` ( list ) | ( attribute ) |

`SortingPerm`

returns the same as `Sortex`

(21.18-3) but does *not* change the argument.

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

Searching objects in a list works much quicker if the list is known to be sorted. Currently **GAP** exploits the sortedness of a list automatically only if the list is *strictly sorted*, which is indicated by the property `IsSSortedList`

(21.17-4).

Remember that a list of *mutable* objects cannot store that it is strictly sorted but has to test it anew whenever it is asked whether it is sorted, see the remark in 21.17. Therefore **GAP** cannot take advantage of the sortedness of a list if this list has mutable entries. Moreover, if a sorted list `list` with mutable elements is used as an argument of a function that *expects* this argument to be sorted, for example `UniteSet`

(21.19-6) or `RemoveSet`

(21.19-5), then it is checked whether `list` is in fact sorted; this check can have the effect actually to slow down the computations, compared to computations with sorted lists of immutable elements or computations that do not involve functions that do automatically check sortedness.

Strictly sorted lists are used to represent *sets* in **GAP**. More precisely, a strictly sorted list is called a *proper set* in the following, in order to avoid confusion with domains (see 12.4) which also represent sets.

In short proper sets are represented by sorted lists without holes and duplicates in **GAP**. Note that we guarantee this representation, so you may make use of the fact that a set is represented by a sorted list in your functions.

In some contexts (for example see 16), we also want to talk about multisets. A *multiset* is like a set, except that an element may appear several times in a multiset. Such multisets are represented by sorted lists without holes that may have duplicates.

This section lists only those functions that are defined exclusively for proper sets. Set theoretic functions for general collections, such as `Intersection`

(30.5-2) and `Union`

(30.5-3), are described in Chapter 30. In particular, for the construction of proper sets, see `SSortedList`

(30.3-7) and `AsSSortedList`

(30.3-10). For finding positions in sorted lists, see `PositionSorted`

(21.16-5).

There are nondestructive counterparts of the functions `UniteSet`

(21.19-6), `IntersectSet`

(21.19-7), and `SubtractSet`

(21.19-8) available for proper sets. These are `UnionSet`

, `IntersectionSet`

, and `Difference`

(30.5-4). The former two are methods for the more general operations `Union`

(30.5-3) and `Intersection`

(30.5-2), the latter is itself an operation (see `Difference`

(30.5-4)).

The result of `IntersectionSet`

and `UnionSet`

is always 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 first argument `set`. If `set` is not a proper set it is not specified to which of a number of equal elements in `set` the element in the result is identical (see 21.6). The following functions, if not explicitly stated differently, take two arguments, `set` and `obj`, where `set` must be a proper set, otherwise an error is signalled; If the second argument `obj` is a list that is not a proper set then `Set`

(30.3-7) is silently applied to it first.

`21.19-1 \in`

`‣ \in` ( obj, list ) | ( method ) |

For a list `list` that stores that it is strictly sorted, the test with `\in`

whether the object `obj` is an entry of `list` uses binary search. This test can be entered also with the infix notation `obj` `in`

`list`.

`‣ IsEqualSet` ( list1, list2 ) | ( operation ) |

tests whether `list1` and `list2` are equal *when viewed as sets*, that is if every element of `list1` is an element of `list2` and vice versa. Either argument of `IsEqualSet`

may also be a list that is not a proper set, in which case `Set`

(30.3-7) is applied to it first.

If both lists are proper sets then they are of course equal if and only if they are also equal as lists. Thus `IsEqualSet( `

is equivalent to `list1`, `list2` )`Set( `

(see `list1` ) = Set( `list2` )`Set`

(30.3-7)), but the former is more efficient.

gap> IsEqualSet( [2,3,5,7,11], [11,7,5,3,2] ); true gap> IsEqualSet( [2,3,5,7,11], [2,3,5,7,11,13] ); false

`‣ IsSubsetSet` ( list1, list2 ) | ( operation ) |

tests whether every element of `list2` is contained in `list1`. Either argument of `IsSubsetSet`

may also be a list that is not a proper set, in which case `Set`

(30.3-7) is applied to it first.

`‣ AddSet` ( set, obj ) | ( operation ) |

adds the element `obj` to the proper set `set`. If `obj` is already contained in `set` then `set` is not changed. Otherwise `obj` is inserted at the correct position such that `set` is again a proper set afterwards.

Note that `obj` must be in the same family as each element of `set`.

gap> s := [2,3,7,11];; gap> AddSet( s, 5 ); s; [ 2, 3, 5, 7, 11 ] gap> AddSet( s, 13 ); s; [ 2, 3, 5, 7, 11, 13 ] gap> AddSet( s, 3 ); s; [ 2, 3, 5, 7, 11, 13 ]

`‣ RemoveSet` ( set, obj ) | ( operation ) |

removes the element `obj` from the proper set `set`. If `obj` is not contained in `set` then `set` is not changed. If `obj` is an element of `set` it is removed and all the following elements in the list are moved one position forward.

gap> s := [ 2, 3, 4, 5, 6, 7 ];; gap> RemoveSet( s, 6 ); s; [ 2, 3, 4, 5, 7 ] gap> RemoveSet( s, 10 ); s; [ 2, 3, 4, 5, 7 ]

`‣ UniteSet` ( set, list ) | ( operation ) |

unites the proper set `set` with `list`. This is equivalent to adding all elements of `list` to `set` (see `AddSet`

(21.19-4)).

gap> set := [ 2, 3, 5, 7, 11 ];; gap> UniteSet( set, [ 4, 8, 9 ] ); set; [ 2, 3, 4, 5, 7, 8, 9, 11 ] gap> UniteSet( set, [ 16, 9, 25, 13, 16 ] ); set; [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 25 ]

`‣ IntersectSet` ( set, list ) | ( operation ) |

intersects the proper set `set` with `list`. This is equivalent to removing from `set` all elements of `set` that are not contained in `list`.

gap> set := [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16 ];; gap> IntersectSet( set, [ 3, 5, 7, 9, 11, 13, 15, 17 ] ); set; [ 3, 5, 7, 9, 11, 13 ] gap> IntersectSet( set, [ 9, 4, 6, 8 ] ); set; [ 9 ]

`‣ SubtractSet` ( set, list ) | ( operation ) |

subtracts `list` from the proper set `set`. This is equivalent to removing from `set` all elements of `list`.

gap> set := [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ];; gap> SubtractSet( set, [ 6, 10 ] ); set; [ 2, 3, 4, 5, 7, 8, 9, 11 ] gap> SubtractSet( set, [ 9, 4, 6, 8 ] ); set; [ 2, 3, 5, 7, 11 ]

Several of the following functions expect the first argument to be either a list or a collection (see 30), with possibly slightly different meaning for lists and non-list collections.

`‣ Concatenation` ( list1, list2, ... ) | ( function ) |

`‣ Concatenation` ( list ) | ( function ) |

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 dense 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 21.6).

Note that `Concatenation`

creates a new list and leaves its arguments unchanged, while `Append`

(21.4-5) changes its first argument. For computing the union of proper sets, `Union`

(30.5-3) can be used, see also 21.19.

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 ]

`‣ Compacted` ( list ) | ( operation ) |

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 ]

`‣ Collected` ( list ) | ( operation ) |

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 ] ]

`‣ DuplicateFreeList` ( list ) | ( operation ) |

`‣ Unique` ( list ) | ( operation ) |

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. Otherwise, if `list` contains objects that can be compared with `\<`

(31.11-1) then it is much more efficient to use `Set`

(30.3-7) instead of `DuplicateFreeList`

.

`Unique`

is a synonym 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) ]) ]

`‣ AsDuplicateFreeList` ( list ) | ( attribute ) |

returns the same result as `DuplicateFreeList`

(21.20-4), except that the result is immutable.

`‣ Flat` ( list ) | ( operation ) |

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

to `elm` )`new`.

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

To reconstruct a matrix from the list obtained by applying `Flat`

to the matrix, the sublist operator can be used, as follows.

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 ] ]

`‣ Reversed` ( list ) | ( function ) |

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

`Reversed`

implements a special case of list assignment, which can also be formulated in terms of the `{}`

operator (see 21.4).

Developers who wish to adapt this for custom list types need to install suitable methods for the operation `ReversedOp`

.

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

`‣ Shuffle` ( list ) | ( operation ) |

The argument `list` must be a dense mutable list. This operation permutes the entries of `list` randomly (in place), and returns `list`.

gap> Reset(GlobalMersenneTwister, 12345);; # make manual tester happy gap> l := [1..20]; [ 1 .. 20 ] gap> m := Shuffle(ShallowCopy(l)); [ 8, 13, 1, 3, 20, 15, 4, 7, 5, 18, 6, 12, 16, 11, 2, 10, 19, 17, 9, 14 ] gap> l; [ 1 .. 20 ] gap> Shuffle(l);; gap> l; [ 19, 5, 7, 20, 16, 1, 10, 15, 12, 11, 13, 2, 14, 3, 4, 17, 6, 8, 9, 18 ]

`‣ Apply` ( list, func ) | ( function ) |

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

(30.3-5).

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

`‣ Perform` ( list, func ) | ( function ) |

`Perform`

applies the function `func` to every element of the list `list`, discarding any return values. It does not return a value.

gap> l := [1, 2, 3];; Perform(l, > function(x) if IsPrimeInt(x) then Print(x,"\n"); fi; end); 2 3

`‣ PermListList` ( list1, list2 ) | ( function ) |

returns a permutation \(p\) of `[ 1 .. Length( `

such that `list1` ) ]`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 ]

`‣ Maximum` ( obj1, obj2, ... ) | ( function ) |

`‣ Maximum` ( list ) | ( function ) |

In the first form `Maximum`

returns the *maximum* of its arguments, i.e., one argument `obj` for which \(\textit{obj} \geq \textit{obj1}\), \(\textit{obj} \geq \textit{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> # lists are compared elementwise: gap> Maximum( [1,2], [0,15], [1,5], [2,-11] ); [ 2, -11 ]

To get the index of the maximum element use `PositionMaximum`

(21.16-8)

`‣ Minimum` ( obj1, obj2, ... ) | ( function ) |

`‣ Minimum` ( list ) | ( function ) |

In the first form `Minimum`

returns the *minimum* of its arguments, i.e., one argument `obj` for which \(\textit{obj} \leq \textit{obj1}\), \(\textit{obj} \leq \textit{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`

(21.20-12) and `Minimum`

the comparison of the objects `obj1`, `obj2` etc. must be defined; for that, usually they must lie in the same family (see 13.1).

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 ]

To get the index of the minimum element use `PositionMinimum`

(21.16-8)

`‣ MaximumList` ( list[, seed] ) | ( operation ) |

`‣ MinimumList` ( list[, seed] ) | ( operation ) |

return the maximum resp. the minimum of the elements in the list `list`. They are the operations called by `Maximum`

(21.20-12) resp. `Minimum`

(21.20-13). 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 21.22).

If a second argument `seed` is supplied, then the result is the maximum resp. minimum of the union of `list` and `seed`. In this manner, the operations may be applied to empty lists.

`‣ Cartesian` ( list1, list2, ... ) | ( function ) |

`‣ Cartesian` ( list ) | ( function ) |

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`, and 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 21.19).

The function `Tuples`

(16.2-8) 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 ] ]

`‣ IteratorOfCartesianProduct` ( list1, list2, ... ) | ( function ) |

`‣ IteratorOfCartesianProduct` ( list ) | ( function ) |

In the first form `IteratorOfCartesianProduct`

returns an iterator (see 30.8) of all elements of the cartesian product (see `Cartesian`

(21.20-15)) of the lists `list1`, `list2`, etc.

In the second form `list` must be a list of lists `list1`, `list2`, etc., and `IteratorOfCartesianProduct`

returns an iterator of the cartesian product of those lists.

Resulting tuples will be returned in the lexicographic order. Usage of iterators of cartesian products is recommended in the case when the resulting cartesian product is big enough, so its generating and storage will require essential amount of runtime and memory. For smaller cartesian products it is faster to generate the full set of tuples using `Cartesian`

(21.20-15) and then loop over its elements (with some minor overhead of needing more memory).

`‣ Permuted` ( list, perm ) | ( operation ) |

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`

(21.18-3) 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 ]

`‣ List` ( list[, func] ) | ( function ) |

This function returns a new mutable list `new`

of the same length as the list `list` (which may have holes). The entry `new[i]`

is unbound if

is unbound. Otherwise `list`[i]`new[i] = `

. If the argument `func`(`list`[i])`func` is omitted, its default is `IdFunc`

(5.4-6), so this function does the same as `ShallowCopy`

(12.7-1) (see also 21.7).

Developers who wish to adapt this for custom list or collection types need to install suitable methods for the operation `ListOp`

.

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 ] gap> List([,1,,3,4], x-> x > 2); [ , false,, true, true ]

(See also `List`

(30.3-5).)

`‣ Filtered` ( listorcoll, func ) | ( function ) |

returns a new list that contains those elements of the list or collection `listorcoll` (see 30), 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 this list. If an element for which `func` returns `true`

appears several times in the list it will also appear the same number of times in the result. The argument list may contain holes, they are ignored by `Filtered`

.

For each element of `listorcoll`, `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 21.6).

List assignment using the operator `\{\}`

(21.3-1) (see 21.4) can be used to extract elements of a list according to indices given in another list.

Developers who wish to adapt this for custom list or collection types need to install suitable methods for the operation `FilteredOp`

.

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) ]

`‣ Number` ( listorcoll[, func] ) | ( function ) |

Called with a list `listorcoll`, `Number`

returns the number of bound entries in this list. For dense lists `Number`

, `Length`

(21.17-5), and `Size`

(30.4-6) return the same value; for lists with holes `Number`

returns the number of bound entries, `Length`

(21.17-5) returns the largest index of a bound entry, and `Size`

(30.4-6) signals an error.

Called with two arguments, a list or collection `listorcoll` and a unary function `func`, `Number`

returns the number of elements of `listorcoll` for which `func` returns `true`

. If an element for which `func` returns `true`

appears several times in `listorcoll` it will also be counted the same number of times.

For each element of `listorcoll`, `func` must return either `true`

or `false`

, otherwise an error is signalled.

`Filtered`

(21.20-19) allows you to extract the elements of a list that have a certain property.

Developers who wish to adapt this for custom list or collection types need to install suitable methods for the operation `NumberOp`

.

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` ( list[, func] ) | ( operation ) |

`First`

returns the first element of the list `list` for which the unary function `func` returns `true`

; if `func` is not given, the first element is returned. `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`

(21.16-9) allows you to find the position of the first element in a list that satisfies a certain property.

Before **GAP** 4.12, developers who wished to adapt this for custom list types needed to install suitable methods for the operation `FirstOp`

. This is still possible for backwards compatibility, but `FirstOp`

now is just a synonym for `First`

.

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

`‣ Last` ( list[, func] ) | ( function ) |

`Last`

returns the last element of the list `list` for which the unary function `func` returns `true`

; if `func` is not given, the last element is returned. `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 `Last`

returns `fail`

.

Developers who wish to adapt this for custom list types need to install suitable methods for the operation `LastOp`

.

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

`‣ ForAll` ( listorcoll, func ) | ( function ) |

tests whether the unary function `func` returns `true`

for all elements in the list or collection `listorcoll`.

Developers who wish to adapt this for custom list or collection types need to install suitable methods for the operation `ForAllOp`

.

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

`‣ ForAny` ( listorcoll, func ) | ( function ) |

tests whether the unary function `func` returns `true`

for at least one element in the list or collection `listorcoll`.

Developers who wish to adapt this for custom list or collection types need to install suitable methods for the operation `ForAnyOp`

.

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

`‣ Product` ( listorcoll[, func][, init] ) | ( function ) |

Called with one argument, a dense list or collection `listorcoll`, `Product`

returns the product of the elements of `listorcoll` (see 30).

Called with a dense list or collection `listorcoll` and a function `func`, which must be a function taking one argument, `Product`

applies the function `func` to the elements of `listorcoll`, and returns the product of the results. In either case `Product`

returns `1`

if the first argument is empty.

The general rules for arithmetic operations apply (see 21.15), so the result is immutable if and only if all summands are immutable.

If `listorcoll` contains exactly one element then this element (or its image under `func` if applicable) itself is returned, not a shallow copy of this element.

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.

Developers who wish to adapt this for custom list or collection types need to install suitable methods for the operation `ProductOp`

.

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)

`‣ Sum` ( listorcoll[, func][, init] ) | ( function ) |

Called with one argument, a dense list or collection `listorcoll`, `Sum`

returns the sum of the elements of `listorcoll` (see 30).

Called with a dense list or collection `listorcoll` and a function `func`, which must be a function taking one argument, `Sum`

applies the function `func` to the elements of `listorcoll`, and returns the sum of the results. In either case `Sum`

returns `0`

if the first argument is empty.

The general rules for arithmetic operations apply (see 21.15), so the result is immutable if and only if all summands are immutable.

If `listorcoll` contains exactly one element then this element (or its image under `func` if applicable) itself is returned, not a shallow copy of this element.

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.

Developers who wish to adapt this for custom list or collection types need to install suitable methods for the operation `SumOp`

.

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)

`‣ Iterated` ( list, f ) | ( operation ) |

returns the result of the iterated application of the function `f`, which must take two arguments, to the elements of the list `list`. More precisely, if `list` has length \(n\) then `Iterated`

returns the result of the following application, \(\textit{f}( \ldots \textit{f}( \textit{f}( \textit{list}[1], \textit{list}[2] ), \textit{list}[3] ), \ldots, \textit{list}[n] )\).

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

`‣ ListN` ( list1, list2, ..., listn, f ) | ( function ) |

applies the \(n\)-argument function `f` to the lists. That is, `ListN`

returns the list whose \(i\)-th entry is \(\textit{f}(\textit{list1}[i], \textit{list2}[i], \ldots, \textit{listn}[i])\).

gap> ListN( [1,2], [3,4], \+ ); [ 4, 6 ]

The following functions are generalizations of `List`

(30.3-5), `Set`

(30.3-7), `Sum`

(21.20-26), and `Product`

(21.20-25).

`‣ ListX` ( arg1, arg2, ..., argn, func ) | ( function ) |

`ListX`

returns a new list constructed from the arguments.

Each of the arguments `arg1`, `arg2`, \(\ldots\) `argn` must be one of the following:

**a list or collection**this introduces a new for-loop in the sequence of nested for-loops and if-statements;

**a function returning a list or collection**this introduces a new for-loop in the sequence of nested for-loops and if-statements, where the loop-range depends on the values of the outer loop-variables; or

**a function returning**`true`

or`false`

this introduces a new if-statement in the sequence of nested for-loops and if-statements.

The last argument `func` must be a function, it is applied to the values of the loop-variables and the results are collected.

Thus `ListX( `

is the same as `list`, `func` )`List( `

, and `list`, `func` )`ListX( `

is the same as `list`, `func`, x -> x )`Filtered( `

.`list`, `func` )

As a more elaborate example, assume `arg1` is a list or collection, `arg2` is a function returning `true`

or `false`

, `arg3` is a function returning a list or collection, and `arg4` is another function returning `true`

or `false`

, then

`result` := ListX( `arg1`, `arg2`, `arg3`, `arg4`, `func` );

is equivalent to

result := []; for v1 in arg1 do if arg2( v1 ) then for v2 in arg3( v1 ) do if arg4( v1, v2 ) then Add( result, func( v1, v2 ) ); fi; od; fi; od;

The following example shows how `ListX`

can be used to compute all pairs and all strictly sorted pairs of elements in a list.

gap> l:= [ 1, 2, 3, 4 ];; gap> pair:= function( x, y ) return [ x, y ]; end;; gap> ListX( l, l, pair ); [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 2, 4 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ], [ 3, 4 ], [ 4, 1 ], [ 4, 2 ], [ 4, 3 ], [ 4, 4 ] ]

In the following example, `\<`

(31.11-1) is the comparison operation:

gap> ListX( l, l, \<, pair ); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]

`‣ SetX` ( arg1, arg2, ..., func ) | ( function ) |

The only difference between `SetX`

and `ListX`

(21.21-1) is that the result list of `SetX`

is strictly sorted.

`‣ SumX` ( arg1, arg2, ..., func ) | ( function ) |

`SumX`

returns the sum of the elements in the list obtained by `ListX`

(21.21-1) when this is called with the same arguments.

`‣ ProductX` ( arg1, arg2, ..., func ) | ( function ) |

`ProductX`

returns the product of the elements in the list obtained by `ListX`

(21.21-1) when this is called with the same arguments.

A *range* is a dense list of integers in arithmetic progression (or degression). This is a list of integers such that the difference between consecutive elements is a nonzero constant. Ranges can be abbreviated with the syntactic construct

`[ `

`first`, `second` .. `last` ]

or, if the difference between consecutive elements is 1, as

`[ `

.`first` .. `last` ]

If

, `first` > `last``[ `

is the empty list, which by definition is also a range; also, if `first` .. `last` ]

or `second` > `first` > `last`

, then `second` < `first` < `last``[ `

is the empty list. If `first`, `second` .. `last` ]

, `first` = `last``[ `

is a singleton list, which is a range, too. Note that `first`, `second` .. `last` ]

must be divisible by the increment `last` - `first`

, otherwise an error is signalled.`second` - `first`

Currently, the integers `first`, `second` and `last` and the length of a range must be *small integers* as defined in chapter 14.

Note also that a range is just a special case of a list. Thus you can access elements in a range (see 21.3), test for membership etc. You can even assign to such a range if it is mutable (see 21.4). Of course, unless you assign

to the entry `last` + `second` - `first`

, the resulting list will no longer be a range. Note that assigning to an entry of `range`[ Length( `range` ) + 1 ]`range` will convert it back into a plain list.

gap> r := [10..20]; [ 10 .. 20 ] gap> Length( r ); 11 gap> r[3]; 12 gap> 17 in r; true gap> # r still is a range but is now represented as a plain list gap> r[1] := 10;; r; [ 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ] gap> IsRange(r); true gap> # r is no longer a range gap> r[12] := 25;; gap> IsRange(r); false gap> r := [1,3..17]; [ 1, 3 .. 17 ] gap> Length( r ); 9 gap> r[4]; 7 gap> r := [0,-1..-9]; [ 0, -1 .. -9 ] gap> r[5]; -4 gap> r := [ 1, 4 .. 32 ]; Error, Range: <last>-<first> (31) must be divisible by <inc> (3)

Most often ranges are used in connection with the `for`

-loop see 4.15-6). Here the construct

`for `

`var` in [ `first` .. `last` ] do `statements` od

replaces the

`for `

`var` from `first` to `last` do `statements` od

which is more usual in other programming languages.

gap> s := [];; for i in [10..20] do Add( s, i^2 ); od; s; [ 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400 ]

Note that a range with

is at the same time also a proper set (see 21.19), because it contains no holes or duplicates and is sorted, and also a row vector (see 23), because it contains no holes and all elements are integers.`last` >= `first`

`‣ IsRange` ( obj ) | ( category ) |

tests if the object `obj` is a range, i.e. is a dense list of integers that is also a range (see 21.22 for a definition of "range").

gap> IsRange( [1,2,3] ); IsRange( [7,5,3,1] ); true true gap> IsRange( [1 .. 3] ); true gap> IsRange( [1,2,4,5] ); IsRange( [1,,3,,5,,7] ); false false gap> IsRange( [] ); IsRange( [1] ); true true

`‣ IsRangeRep` ( obj ) | ( representation ) |

Tests whether `obj` is represented as a range, that is by internally storing only the first value, the in- or decrement, and the last value of the range.

To test whether a list is a range in the mathematical sense see `IsRange`

(21.22-1).

Lists created by the syntactic construct `[ `

, see 21.22, are in `first`, `second` .. `last` ]`IsRangeRep`

.

Note that if you modify an `IsRangeRep`

object by assigning to one of its entries, or by using `Add`

(21.4-2) or `Append`

(21.4-5), then the range may be converted into a plain list, even though the resulting list may still be a range, mathematically.

gap> IsRangeRep( [1 .. 3] ); true gap> IsRangeRep( [1, 2, 3] ); false gap> l := [1..3];; gap> l[1] := 1;; gap> l; [ 1, 2, 3 ]

`‣ ConvertToRangeRep` ( list ) | ( function ) |

For some lists the **GAP** kernel knows that they are in fact ranges. Those lists are represented internally in a compact way, namely in `IsRangeRep`

(21.22-2), instead of as plain lists. A list that is represented as a plain list might still be a range but **GAP** may not know this.

If `list` is a range then `ConvertToRangeRep`

changes the representation of `list` to `IsRangeRep`

(21.22-2). A call of `ConvertToRangeRep`

for a list that is not a range is ignored.

gap> r:= [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] gap> ConvertToRangeRep( r ); r; [ 1 .. 10 ] gap> l:= [ 1, 2, 4, 5 ];; ConvertToRangeRep( l ); l; [ 1, 2, 4, 5 ]

An *enumerator* is an immutable list that need not store its elements explicitly but knows, from a set of basic data, how to determine the \(i\)-th element and the position of a given object. A typical example of this is a vector space over a finite field with \(q\) elements for which it is very easy to enumerate all elements using \(q\)-adic expansions of integers.

Using this enumeration can be even quicker than a binary search in a sorted list of vectors, see `IsQuickPositionList`

(21.23-1).

On the one hand, element access to an enumerator may take more time than element access to an internally represented list containing the same elements. On the other hand, an enumerator may save a vast amount of memory. Take for example a permutation group of size a few millions. Even for moderate degree it is unlikely that a list of all its elements will fit into memory whereas it is no problem to construct an enumerator from a stabilizer chain (see 43.6).

There are situations where one only wants to loop over the elements of a domain, without using the special facilities of an enumerator, namely the particular order of elements and the possibility to find the position of elements. For such cases, **GAP** provides iterators (see 30.8).

The functions `Enumerator`

(30.3-2) and `EnumeratorSorted`

(30.3-3) return enumerators of domains. Most of the special implementations of enumerators in the **GAP** library are based on the general interface that is provided by `EnumeratorByFunctions`

(30.3-4); one generic example is `EnumeratorByBasis`

(61.6-5), which can be used to get an enumerator of a finite dimensional free module.

Also enumerators for non-domains can be implemented via `EnumeratorByFunctions`

(30.3-4); for a discussion, see 79.5.

`‣ IsQuickPositionList` ( list ) | ( filter ) |

This filter indicates that a position test in `list` is quicker than about 5 or 6 element comparisons for "smaller". If this is the case it can be beneficial to use `Position`

(21.16-1) in `list` and a bit list than ordered lists to represent subsets of `list`.

Plain lists are the default kind of lists in **GAP**, in the sense that **GAP** stores the list entries and does not know how to do better (as opposed to ranges or strings, which are also lists). Often it is not necessary to know how a given list is represented internally, the operations defined for lists apply to all lists.

Typical situations where the representation matters are when one wants to make sure that the given list is *not* a plain list and thus will be handled more efficiently, for example when one installs a method for a particular operation, where an argument is required to be a list in a particular representation.

`‣ PlainListCopy` ( list ) | ( function ) |

This function returns a list equal to its argument, in a plain list representation (see `IsPlistRep`

(21.24-2)). This is intended for use in certain rare situations, such as before objectifying, or calling some kernel functions.

`‣ IsPlistRep` ( obj ) | ( representation ) |

**GAP** lists created by entering comma separated values in square brackets are usually represented internally as so-called *plain lists*. Other representations of lists are `IsBlistRep`

(22.5-1), `IsRangeRep`

(21.22-2), `IsStringRep`

(27.4-1), or the ones that are chosen for implementing enumerators, see Section 21.23.

gap> IsPlistRep( [ 1, 2, 3 ] ); true gap> IsPlistRep( "abc" ); false gap> IsPlistRep( [ 1 .. 5 ] ); false gap> IsPlistRep( BlistList( [ 1 .. 5 ], [ 1 ] ) ); false gap> IsPlistRep( 0 ); false

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