% This file was created automatically from lists.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  lists.msk                   GAP documentation            Martin Schoenert
%A                                                           Alexander Hulpke
%%
%A  @(#)$Id: lists.msk,v 1.52.2.7 2007/08/31 10:54:17 gap Exp $
%%
%Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Lists}

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~"Mutability and Copyability" for the concept of mutability,
and~"Duplication of Lists" for the case of lists.

This chapter deals mainly with the aspect of lists in {\GAP}
as *data structures*.
Chapter~"Collections" tells more about the *collection* aspect of certain
lists,
and more about lists as *arithmetic objects* can be found in the chapters
"Row Vectors" and "Matrices".

Lists are used to implement ranges (see~"Ranges"),
sets (see~"Sorted Lists and Sets"),\index{Sets}
strings (see~"Strings and Characters"),
row vectors (see~"Row Vectors"), and matrices (see~"Matrices");
Boolean lists (see~"Boolean Lists") are a further special kind of lists.

Several operations for lists, such as `Intersection' and `Random',
will be described in Chapter~"Collections",
in particular see~"Lists and Collections".


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{List Categories}

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 `[]'.

\beginexample
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 ] ]
\endexample

Each list constructed this way is mutable (see~"Mutability and Copyability").

\>IsList( <obj> ) C

tests whether <obj> is a list.


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

\>IsDenseList( <obj> ) C

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.

%notest
\beginexample
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> 
\endexample

Observe that requesting the value of `l[4]', which was not
assigned, caused the entry of a `break'-loop (see Section~"Break Loops").
After assigning a value and typing `return;', {\GAP} is finally
able to comply with our request (by responding with `16').

\>IsHomogeneousList( <obj> ) C

returns `true' if <obj> is a list  and  it  is  homogeneous,  or  `false'
otherwise.

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


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

\>IsTable( <obj> ) C

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


\beginexample
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
\endexample

\>IsConstantTimeAccessList( <list> ) C

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~"Enumerators") can lie in this category
if they guarantee constant time access to their elements.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Basic Operations for Lists}

The basic operations for lists are element access (see~"List Elements"),
assignment of elements to a list (see~"List Assignment"),
fetching the length of a list (see~"Length"),
the test for a hole at a given position, and unbinding an element at a given
position (see~"IsBound and Unbind for Lists").

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

Any {\GAP} object <list> in the category `IsList' (see~"IsList") 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.
For other lists, 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~"Enumerators");
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").

\>`\\[\\]( <list>, <pos> )'{list element!operation} O
\>`IsBound\\[\\]( <list>, <pos> )'{list boundedness test!operation} O
\>`\\[\\]\\:\\=( <list>, <pos>, <val> )'{list assignment!operation} O
\>`Unbind\\[\\]( <list>, <pos> )'{list unbind!operation} O

These operations implement element access, test for element boundedness,
list element assignment, and removal of the element at position <pos>.
In all cases, the index <pos> must be a positive integer.

Note that the special characters `[', `]', `:', and `=' must be escaped with
a backslash `\\' (see~"Symbols");
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.)

`\\[\\]( <list>, <pos> )' is equivalent to `<list>[ <pos> ]',
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.

Similarly, `IsBound\\[\\]' is used explicitly mainly in method installations.
In other situations, one can simply call `IsBound', which then delegates to
`IsBound\\[\\]' if the first argument is a list, and to `IsBound\\.' if the
first argument is a record.

Analogous statements hold for `\\[\\]\\:\\=' and `Unbind\\[\\]'.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{List Elements}

\index{accessing!list elements}
\>`<list>[ <pos> ]'{list element!access}

The above construct evaluates to the <pos>-th element of the list <list>.
<pos> must be a positive integer. List indexing is done with origin 1,
i.e., the first element of the list is the element at position 1.
\beginexample
gap> l := [ 2, 3, 5, 7, 11, 13 ];;  l[1];  l[2];  l[6];
2
3
13
\endexample
If <list> is not a list, or <pos> does not evaluate to a
positive integer, or `<list>[<pos>]' is unbound an error is signalled.

\>`<list>\{ <poss> \}'{sublist!access}

\index{sublist}
The above construct evaluates to a new list <new> whose first element is
`<list>[<poss>[1]]', whose second element is `<list>[<poss>[2]]', and so
on. <poss> must be a dense list of positive integers. However, it does not
need to be sorted and may contain duplicate elements. If for any <i>,
`<list>[ <poss>[<i>] ]' is unbound, an error is signalled.

\beginexample
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 ]
\endexample

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~"Identical Lists").

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

\beginexample
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 ] ]
\endexample

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 `[<pos>]' or `\{<poss>\}' we associate
a *level* that is defined as the number of selectors of the form
`\{<poss>\}' to its left in the same expression. For example

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

Then  a selector `<list>[<pos>]' of level <level> is computed as
`ListElement(<list>,<pos>,<level>)', where `ListElement' is defined as
follows.
(Note that `ListElement' is *not* a {\GAP} function.)

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

and a selector `<list>\{<poss>\}' of level <level> is computed as
`ListElements(<list>,<poss>,<level>)', where `ListElements' is defined as
follows.
(Note that `ListElements' is *not* a {\GAP} function.)

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


\>`\\\{\\\}( <list>, <poss> )'{sublist!operation} O

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.~"Basic Operations for Lists".)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{List Assignment}

\index{assignment!to a list}
\>`<list>[ <pos> ] := <object>;'{list element!assignment}

The list element assignment assigns the object <object>,
which can be of any type, to the list entry at the position <pos>,
which must be a positive integer,
in the mutable (see~"Mutability and Copyability") list <list>.
That means that accessing the <pos>-th element of the list <list> will
return <object> after this assignment.

\beginexample
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 ]
\endexample

If the index <pos> is larger than the length of the list <list> (see
"Length"), the list is automatically enlarged to make room for the new
element. Note that it is possible to generate lists with holes that way.

\beginexample
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 ]
\endexample

The  function `Add' (see "Add") 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~"Mutability and Copyability").
See~"Identical Lists" for subtleties of changing lists.

If <list> does not evaluate to a list, <pos> does not evaluate to a
positive integer or <object> is a call to a function which does not
return a value (for example `Print') an error is signalled.

\>`<list>\{ <poss> \} := <objects>;'{sublist!assignment}

The sublist assignment assigns the object `<objects>[1]', which can be of
any type, to the list <list> at the position `<poss>[1]', the object
`<objects>[2]' to `<list>[<poss>[2]]', and so on. <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>.

\beginexample
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 ]
\endexample

It is possible to nest such sublist assignments, as can be seen in the
following example.

\beginexample
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 ] ]
\endexample

The exact behaviour is defined in the same way as for list extractions
(see  "List Elements").  Namely  with each  selector `[<pos>]' or
`\{<poss>\}' we associate a *level* that is defined as the number of
selectors of the form `\{<poss>\}' to its left in the same expression.
For example

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

Then a list assignment `<list>[<pos>] := <vals>;' of level <level> is
computed as `ListAssignment( <list>, <pos>, <vals>, <level> )', where
`ListAssignment' is defined as follows.
(Note that `ListAssignment' is *not* a {\GAP} function.)

\begintt
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;
\endtt

and a list assignment `<list>\{<poss>\} := <vals>' of level <level> is
computed as `ListAssignments( <list>, <poss>, <vals>, <level> )', where
`ListAssignments' is defined as follows.
(Note that `ListAssignments' is *not* a {\GAP} function.)

\begintt
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;
\endtt

\>`\\\{\\\}\\:\\=( <list>, <poss>, <val> )'{sublist assignment!operation} O

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.~"Basic Operations for Lists".)


\>Add( <list>, <obj> ) O
\>Add( <list>, <obj>, <pos> ) O

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
`<list>[ Length(<list>) + 1 ] := <obj>', see~"list element!assignment".

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> ) O
\>Remove( <list>, <pos> ) O

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.

Remove( <list> ) always returns the removed element. In this case <list>
must be non-empty. Remove( <list>, <pos> )
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.


\beginexample
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]
\endexample

These two operations are implemented with the aid of a 
more general kernel function

\>COPY_LIST_ENTRIES( <from-list>, <from-index>, <from-step>, <to-list>, <to-index>, <to-step>, <number> ) F

This function copies <number> elements from <from-list>,
starting at position <from-index> and incrementing the position by
<from-step> each time, into <to-list> starting at position <to-index>
and incrementing the position by <to-step> each time. <from-list> and
<to-list> must be plain lists.  <from-step> and/or <to-step> can be
negative. Unbound positions of <from-list> are simply copied to
<to-list>.

\>Append( <list1>, <list2> ) O

adds the elements of the list <list2> to the end of the mutable list
<list1>, see~"sublist!assignment".
<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'
(see~"Concatenation") creates a new list and leaves its arguments
unchanged.

\beginexample
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 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsBound and Unbind for Lists}

\>IsBound( <list>[<n>] )!{for lists} M

`IsBound' returns `true' if the list <list> has a
element at the position <n>, and `false' otherwise.
<list> must evaluate to a list, otherwise an error is signalled.

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

\>Unbind( <list>[<n>] )!{for lists} M

`Unbind' deletes the element at the position <n> in the mutable list <list>.
That is, after execution of `Unbind', <list> no longer
has an assigned value at the position <n>.
Thus `Unbind' can be used to produce holes in a list.
Note that it is not an error to unbind a nonexisting list element.
<list> must evaluate to a list, otherwise an error is signalled.

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

Note that `IsBound' and `Unbind' are special in that they do not evaluate
their argument, otherwise `IsBound' 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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Identical Lists}

With the list assignment (see~"List Assignment") it is
possible  to change a mutable list.
This section describes the semantic consequences of this fact.
(See also~"Identical Objects".)

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.

\begintt
i := 3;
i := i + 1;
\endtt

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 following
example

\begintt
l := [ 1, 2 ];
l := [ 1, 2, 3 ];
\endtt

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.

\begintt
l := [ 1, 2 ];
l[3] := 3;
\endtt

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 `<var>:=<list>;' means in  this
interpretation that <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.

\begintt
l1 := [ 1, 2 ];
l2 := l1;
l1 := [ 1, 2, 3 ];
\endtt

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

\begintt
l1 := [ 1, 2 ];
l2 := l1;
l1[3] := 3;
\endtt

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',
see~"Identical Objects".

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.

\begintt
l1 := [ 1, 2 ];
l2 := [ 1, 2 ];
\endtt

Also in the following example, no lists in the list `l' are identical.

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

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.

\begintt
l1 := [ 1, 2 ];
l2 := l1;
\endtt

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:

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

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.

\begintt
l1 := [ 1, 2 ];
l2 := l1;
l1[1] := 2;
\endtt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Duplication of Lists}

Here we describe the meaning of `ShallowCopy' and `StructuralCopy' for
lists.
For the general definition of these functions,
see~"Duplication of Objects".

\indextt{ShallowCopy!for lists}
The subobjects (see~"ShallowCopy") of a list are exactly its elements.

This means that for any list <list>, `ShallowCopy' returns a mutable
*new* list <new> that is *not identical* to any other list
(see~"Identical Lists"),
and whose elements are identical to the elements of <list>.

\indextt{StructuralCopy!for lists}
Analogously, for a *mutable* list <list>, `StructuralCopy' 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~"List Assignment") does not modify the original object <list>.

`ShallowCopy' basically executes the following code for lists.
\begintt
new := [];
for i in [ 1 .. Length( list ) ] do
  if IsBound( list[i] ) then
    new[i] := list[i];
  fi;
od;
\endtt

\beginexample
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 ] ]
\endexample

`StructuralCopy' basically executes the following code for lists.
\begintt
new := [];
for i in [ 1 .. Length( list ) ] do
  if IsBound( list[i] ) then
    new[i] := StructuralCopy( list[i] );
  fi;
od;
\endtt

\beginexample
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 ] ]
\endexample

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.

\beginexample
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 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Membership Test for Lists}

\indextt{in!for lists}
\>`<obj> in <list>'{element test}!{for lists}

tests whether there is a positive integer <index> such that
`<list>[ <index> ] = <obj>'.

If the list <list> knows that it is strictly sorted (see~"IsSSortedList"),
the membership test is much quicker, because a binary search can be used
instead of the linear search used for arbitrary lists.

\beginexample
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
\endexample

For finding the position of an element in a list,
see~"Finding Positions in Lists".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Enlarging Internally Represented Lists}

Section~"List Assignment" 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
`<length>/8 + 4' 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.

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' (see~"Length"), is the logical length.

Suppose that `Length' 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', and other functions that need to know the logical length,
more efficient, the length of a list is stored along with the list.

%A note aside. In the previous version 2.4 of {\GAP} a list was indeed
%enlarged  every time an assignment beyond  the end of the list was
%performed. To deal with the above inefficiency the following hacks where
%used. Instead of creating lists in order they were usually created in
%reverse  order.  In situations  where this was not possible a dummy
%assignment to the last position was performed, for example
%
%  l := [];
%  l[1000] := "dummy";
%  l[1] := first_value();
%  for i from 2 to 1000 do l[i] := next_value(l[i-1]); od;

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

\>EmptyPlist( <len> ) F

\>ShrinkAllocationPlist( <l> ) F

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' and
`ShrinkAllocationString' for strings instead of plain lists.

\beginexample
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
\endexample



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Comparisons of Lists}

\index{comparisons!of lists}
\>`<list1> = <list2>'{list equal!comparison}
\){\fmark <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'.

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

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>'{list smaller!comparison}
\){\fmark <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'.

\beginexample
gap> [ 1, 2, 3, 4 ] < [ 1, 2, 4, 8 ]; # <list1>[3] < <list2>[3]
true
gap> [ 1, 2, 3 ] < [ 1, 2, 3, 4 ];    # <list1>[4] is unbound and therefore very small
true
gap> [ 1, , 3, 4 ] < [ 1, 2, 3 ];     # <list1>[2] is unbound and therefore very small
true
\endexample

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~"Families".
Also for the possibility to compare lists with other objects,
see~"Families".


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Arithmetic for Lists}

\index{operators!for lists}

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',
see~"IsList".)

(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~"Operators for Matrices")
and row vectors (see~"Operators for Row Vectors") 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' (see~"Length") returning the number of rows etc.

For the categories and attributes that control the arithmetic behaviour
of lists, see~"Filters Controlling the Arithmetic Behaviour of Lists".

For the definition of return values of additive and multiplicative operations
whose arguments are lists in these filters,
see~"Additive Arithmetic for Lists" and
"Multiplicative Arithmetic for Lists", 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~"Mutability Status and List Arithmetic".
(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~"Operators for Row Vectors" and in~"Operators for Matrices",
the compression status is dealt with in~"Row Vectors over Finite Fields"
and~"Matrices over Finite Fields".


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Filters Controlling the Arithmetic Behaviour of Lists}

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


For a list <list>, the value `true' for `IsGeneralizedRowVector'
indicates that the additive arithmetic behaviour of <list> is
as defined in~"Additive Arithmetic for Lists",
and that the attribute `NestingDepthA' (see~"NestingDepthA")
will return a nonzero value when called with <list>.


\>IsMultiplicativeGeneralizedRowVector( <list> ) C


For a list <list>, the value `true' for
`IsMultiplicativeGeneralizedRowVector' indicates that the multiplicative
arithmetic behaviour of <list> is as defined
in~"Multiplicative Arithmetic for Lists",
and that the attribute `NestingDepthM' (see~"NestingDepthM")
will return a nonzero value when called with <list>.



Note that these filters do *not* enable default methods for addition or
multiplication (cf.~"IsListDefault").

\beginexample
gap> IsList( "abc" ); IsGeneralizedRowVector( "abc" );
true
false
gap> liemat:= LieObject( [ [ 1, 2 ], [ 3, 4 ] ] );
LieObject( [ [ 1, 2 ], [ 3, 4 ] ] )
gap> IsGeneralizedRowVector( liemat );
true
gap> IsMultiplicativeGeneralizedRowVector( liemat );
false
gap> bas:= CanonicalBasis( FullRowSpace( Rationals, 3 ) );
CanonicalBasis( ( Rationals^3 ) )
gap> IsMultiplicativeGeneralizedRowVector( bas );
true
\endexample


\>IsListDefault( <list> ) C

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' and
`IsMultiplicativeGeneralizedRowVector'.

All internally represented lists are in this category,
and also all lists in the representations `IsGF2VectorRep',
`Is8BitVectorRep', `IsGF2MatrixRep', and `Is8BitMatrixRep'
(see~"Row Vectors over Finite Fields" and "Matrices over Finite Fields").
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'.



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


\>NestingDepthA( <obj> ) A

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',
as the integer $1$ if <obj> is an empty list in `IsGeneralizedRowVector',
and as $1$ plus the additive nesting depth of the first bound entry in
<obj> otherwise.


\>NestingDepthM( <obj> ) A

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',
as the integer $1$ if <obj> is an empty list in
`IsMultiplicativeGeneralizedRowVector',
and as $1$ plus the multiplicative nesting depth of the first bound entry
in <obj> otherwise.



\beginexample
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
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Additive Arithmetic for Lists}

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';
for binary operations (addition and subtraction),
at least one argument must be in `IsGeneralizedRowVector',
and the other either is not a list or also in `IsGeneralizedRowVector'.

(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',
it shall be left to this argument whether the result in question is defined
and what it is.)


*Zero*

The zero (see~"Zero") of a list $x$ in `IsGeneralizedRowVector'
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.

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


*AdditiveInverse*

The additive inverse (see~"AdditiveInverse") of a list $x$ in
`IsGeneralizedRowVector' 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.

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


*Addition*

\index{addition!list and non-list}

If $x$ and $y$ are in `IsGeneralizedRowVector' and have the same
additive nesting depth (see~"NestingDepthA"),
% By definition, this depth is nonzero.
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") 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' and $y$ is
in `IsGeneralizedRowVector' 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.

\beginexample
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 ]
\endexample


*Subtraction*

\index{list and non-list!difference}

For two {\GAP} objects $x$ and $y$ of which one is in
`IsGeneralizedRowVector' and the other is also in `IsGeneralizedRowVector'
or is neither a list nor a domain, $x - y$ is defined as $x + (-y)$.

\beginexample
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 ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Multiplicative Arithmetic for Lists}

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';
for binary operations (multiplication and division),
at least one argument must be in `IsMultiplicativeGeneralizedRowVector',
and the other either not a list or also in
`Is\-Multiplicative\-Generalized\-Row\-Vector'.

(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',
it shall be left to this argument whether the result in question is defined
and what it is.)


*One*

The one (see~"One") of a dense list $x$ in
`IsMultiplicativeGeneralizedRowVector' 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'( x[1][1] )$ and off-diagonal entries $`Zero'( x[1][1] )$.

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


*Inverse*

The inverse (see~"Inverse") of an invertible square table $x$ in
`IsMultiplicativeGeneralizedRowVector' 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 $x y$ and $y x$ is equal to
$`One'( x )$.

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


*Multiplication*

\index{list and non-list!product}

There are three possible computations that might be triggered by a
multiplication involving a list in `IsMultiplicativeGeneralizedRowVector'.
Namely, $x * y$ might be
\beginlist
\item{(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
\item{(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
\item{(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.
\endlist

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

\begintt
    | scl   vec   mat
---------------------
scl |       (L)   (L)
vec | (R)   (I)   (I)
mat | (R)   (R)   (R)
\endtt

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'
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', 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.
% By definition, this depth is nonzero.
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.

\beginexample
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
\endexample


*Division*

\index{list and non-list!quotient}

For two {\GAP} objects $x$ and $y$ of which one is in
`IsMultiplicativeGeneralizedRowVector' and the other is also in
`IsMultiplicativeGeneralizedRowVector' or is neither a list nor a domain,
$x / y$ is defined as $x * y^{-1}$.

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


*mod*

\index{list and non-list!mod}
\index{mod!lists}

If $x$ and $y$ are in `IsMultiplicativeGeneralizedRowVector' and have the
same multiplicative nesting depth (see~"NestingDepthM"),
% By definition, this depth is nonzero.
$x `mod'  y$ is defined *pointwise*, in the sense that the result is a
list whose entry at position $i$ is $x[i] `mod' y[i]$ if these entries are
bound,
is a shallow copy (see~"ShallowCopy") 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' and $y$ is in
`Is\-Multiplicative\-Generalized\-Row\-Vector' and has lower multiplicative
nesting depth or is neither a list nor a domain,
$x `mod' y$ is defined as a list whose entry at position $i$ is
$x[i] `mod' 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 arguments is kept.

\beginexample
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 ]
\endexample


*Left Quotient*

\index{list and non-list!left quotient}

For two {\GAP} objects $x$ and $y$ of which one is in
`IsMultiplicativeGeneralizedRowVector' and the other is also in
`IsMultiplicativeGeneralizedRowVector' or is neither a list nor a domain,
$`LeftQuotient'( x, y )$ is defined as $x^{-1} * y$.

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Mutability Status and List Arithmetic}

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~"Mutability and Copyability").

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',
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'.
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}.
% Note that this means to call `ShallowCopy' more often than necessary!
% Would it be possible to promise the mutability status for all entries only
% if the arguments are homogeneously mutable,
% as a refinement of the general mutability rule?

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.

% Note that there are situations where this rule (and in fact already the
% general rule mentioned above) leads to counter-intuitive results.

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', `AdditiveInverse', `One', `Inverse'),
an operation that returns a result that is mutable
% at least on the outer level, or shall more be guaranteed?
(`ZeroOp', `AdditiveInverseOp', `OneOp', `InverseOp'),
and an operation whose result has the same immutability level as the argument
(`ZeroSM', `AdditiveInverseSM', `OneSM', `InverseSM').
The last kind of operations is equivalent to the corresponding infix
operations `0 * <list>', `- <list>', `<list>^0', and `<list>^-1'.
(This holds not only for lists, see~"Mutability and Copyability".)

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

An example motivating the mutability rule is the use of syntactic constructs
such as `<obj> \* <list>' and `- <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 `0 \* [ 1 .. <n> ]'.
The latter can be done also using `ListWithIdenticalEntries'.

\>ListWithIdenticalEntries( <n>, <obj> ) F

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~"Identical Lists".


\beginexample
gap> ListWithIdenticalEntries( 10, 0 );
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Finding Positions in Lists}

\>Position( <list>, <obj>[, <from>] ) O

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


\beginexample
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
\endexample

\>Positions( <list>, <obj> ) F
\>PositionsOp( <list>, <obj> ) O

returns the positions of *all* occurrences of <obj> in <list>.


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

\>PositionCanonical( <list>, <obj> ) O

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', see~"Position"),
but for example for certain enumerators (see~"Enumerators") other
canonical associates can be defined.

For example `RightTransversal' defines the canonical associate to be the
element in the transversal defining the same coset of a subgroup in a
group.


\beginexample
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
\endexample


\>PositionNthOccurrence( <list>, <obj>, <n> ) O

returns the position of the <n>-th occurrence of <obj> in <list> and
returns `fail' if <obj> does not occur <n> times.


\beginexample
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
\endexample

\>PositionSorted( <list>, <elm> ) F
\>PositionSorted( <list>, <elm>, <func> ) F

In the first form `PositionSorted' returns the position of the element
<elm> in the sorted list <list>.

In the second form `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 $<list>[<pos>-1] \< <elm>$ and
$<elm> \le <list>[<pos>]$.
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' can in general
use only linear search, see the remark at the beginning
of~"Sorted Lists and Sets".
For sorting lists, see~"Sorting Lists",
for testing whether a list is sorted, see~"IsSortedList" and
"IsSSortedList".

Specialized functions for certain kinds of lists must be installed 
as methods for the operation `PositionSortedOp'.

we catch plain lists by a function to avoid method selection

\beginexample
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
\endexample

\>PositionSet( <list>, <obj> ) F
\>PositionSet( <list>, <obj>, <func> ) F

`PositionSet' is a slight variation of `PositionSorted'.
The only difference to `PositionSorted' is that `PositionSet' returns
`fail' if <obj> is not in <list>.


\beginexample
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
\endexample

\>PositionProperty( <list>, <func> ) O

returns the first position of an element in the list <list> for which the
property tester function <func> returns `true'.


\beginexample
gap> PositionProperty( [10^7..10^8], IsPrime );
20
gap> PositionProperty( [10^5..10^6],
>        n -> not IsPrime(n) and IsPrimePowerInt(n) );
490
\endexample
`First' (see~"First") allows you to extract the first element of a list
that satisfies a certain property.

\>PositionBound( <list> ) O

returns the first index for which an element is bound in the list <list>.
For the empty list it returns `fail'.


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

\>PositionNot( <list>, <val>[, <from-minus-one>] ) O

For a list <list> and an object <val>, `PositionNot' returns the smallest
nonnegative integer $n$ such that $<list>[n]$ is either unbound or
not equal to <val>.
If a nonnegative integer is given as optional argument <from-minus-one>
then the first position larger than <from-minus-one> with this property
is returned.


\>PositionNonZero( <vec> ) O

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.

`PositionNonZero' implements a special case of `PositionNot'
(see~"PositionNot").
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.


\beginexample
gap> l:= [ 1, 1, 2, 3, 2 ];;  PositionNot( l, 1 );
3
gap> PositionNot( l, 1, 4 );  PositionNot( l, 2, 5 );
5
6
gap> PositionNonZero( l );  PositionNonZero( [ 2, 3, 4, 5 ] * Z(2) );
1
2
\endexample

\>PositionSublist( <list>, <sub> ) O
\>PositionSublist( <list>, <sub>, <from> ) O

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 second version starts searching *after* position <from>.

To determine whether <sub> matches <list> at a  particular position, use 
`IsMatchingSublist' instead (see "IsMatchingSublist").



\>PositionFirstComponent( <list>, <obj> ) O

returns the index <i> in <list> such that $<list>[<i>][1]=<obj>$ or the 
place where such an entry should be added (cf PositionSorted).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Properties and Attributes for Lists}

\>IsMatchingSublist( <list>, <sub> ) O
\>IsMatchingSublist( <list>, <sub>, <at> ) O

returns `true' if <sub> matches a sublist of <list> from position 1 (or
position <at>, in the case of the second version), 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( <list>, <sub>, <at> )' is true, use a construction
like `PositionSublist( <list>, <sub> ) <> fail' instead 
(see "PositionSublist"); it's more efficient.



*Note:* 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.
\beginexample
gap> l:=[[1],[2]];
[ [ 1 ], [ 2 ] ]
gap> IsSSortedList(l);
true
gap> l[1][1]:=3;
3
gap> IsSSortedList(l);
false
\endexample
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' (see~"Position") with <list> as first argument
cannot take advantage of the fact that <list> is in fact sorted.
One solution is to call explicitly `PositionSorted' (see~"PositionSorted")
in such a situation, another solution is to replace <list> by an immutable
copy using `Immutable' (see~"Mutability and Copyability").

\>IsDuplicateFree( <obj> ) P
\>IsDuplicateFreeList( <obj> ) P

`IsDuplicateFree(<obj>);' 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'.

\index{duplicate free}
A list is *duplicate free* if it is dense and does not contain equal
entries in different positions.
Every domain (see~"Domains") is duplicate free.


\>IsSortedList( <obj> ) P

returns `true' if <obj> is a list and it is sorted, or `false' otherwise.

\index{sorted list}
A list <list> is *sorted* if it is dense (see~"IsDenseList")
and satisfies the relation $<list>[i] \leq <list>[j]$ whenever $i \< j$.
Note that a sorted list is not necessarily duplicate free
(see~"IsDuplicateFree" and "IsSSortedList").

Many sorted lists are in fact homogeneous (see~"IsHomogeneousList"),
but also non-homogeneous lists may be sorted
(see~"Comparison Operations for Elements").


\>IsSSortedList( <obj> ) P
\>IsSet( <obj> ) P

returns `true' if <obj> is a list and it is strictly sorted,  or  `false'
otherwise. `IsSSortedList' is short  for  ``is  strictly  sorted  list'';
`IsSet' is just a synonym for `IsSSortedList'.

\index{strictly sorted list}
A list <list> is *strictly sorted* if it is sorted (see~"IsSortedList")
and satisfies the relation $<list>[i] \lneqq <list>[j]$ whenever $i\< j$.
In particular, such lists are duplicate free (see~"IsDuplicateFree").

In sorted lists, membership test and computing of positions can be done
by binary search, see~"Sorted Lists and Sets".

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


\>Length( <list> ) A

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


\>ConstantTimeAccessList( <list> ) A

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




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Sorting Lists}

\>Sort( <list> ) O
\>Sort( <list>, <func> ) O

sorts the list <list> in increasing order.
In the first form `Sort' uses the operator `\<' to compare the elements.
(If the list is not homogeneous it is the users responsibility to ensure
that `\<' is defined for all element pairs, see~"Comparison Operations
for Elements")
In the second 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.

`Sort' does not return anything, it just changes the argument <list>.
Use  `ShallowCopy' (see "ShallowCopy") if you  want to keep  <list>.  Use
`Reversed'  (see  "Reversed") if you  want to  get a  new  list sorted in
decreasing order.

It is possible to sort lists that contain multiple elements which compare
equal.    It is not  guaranteed  that those  elements keep their relative
order, i.e., `Sort' is not stable.


\beginexample
gap> list := [ 5, 4, 6, 1, 7, 5 ];; Sort( list ); list;
[ 1, 4, 5, 5, 6, 7 ]
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 Euclidian distance from [0,0]
[ [ 1, 2 ], [ 1, 3 ], [ 0, 4 ], [ 3, 4 ], [ 1, 5 ], [ 0, 6 ] ]
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> list;  # note the random order of the elements with equal first component
[ [ 0, 6 ], [ 0, 4 ], [ 1, 3 ], [ 1, 5 ], [ 1, 2 ], [ 3, 4 ] ]
\endexample

\>SortParallel( <list>, <list2> ) O
\>SortParallel( <list>, <list2>, <func> ) O

sorts the list <list1> in increasing order just as `Sort' (see~"Sort")
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.


\beginexample
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;  # note: [ 7, 3, 2, 9, 5, 8 ] or [ 7, 3, 9, 2, 5, 8 ] are possible results
[ 7, 3, 2, 9, 5, 8 ]
\endexample

\>Sortex( <list> ) O

sorts the list <list> via the operator`\<' and returns a permutation
that can be applied to <list> to obtain the sorted list.
(If the list is not homogeneous it is the user's responsibility to ensure
that `\<' is defined for all element pairs,
see~"Comparison Operations for Elements")

`Permuted' (see~"Permuted") allows you to rearrange a list according to
a given permutation.


\beginexample
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 ]
\endexample

\>SortingPerm( <list> ) A

`SortingPerm' returns the same as `Sortex( <list> )' (see~"Sortex")
but does *not* change the argument.


\beginexample
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 ]
\endexample

Currently {\GAP} uses shellsort.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Sorted Lists and Sets}

\index{sets}
\index{multisets}

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', see~"IsSSortedList".

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~"Properties and Attributes for Lists".
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' or `RemoveSet' (see~"UniteSet", "RemoveSet"),
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~"Domains")
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~"Combinatorics"), 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'
and `Union', are described in Chapter~"Collections".
In particular, for the construction of proper sets, see~"SSortedList"
and "AsSSortedList".
For finding positions in sorted lists, see~"PositionSorted".


\>`<obj> in <list>'{in!for strictly sorted lists}@{`in'!for strictly sorted lists}

The element test for strictly sorted lists uses binary search.


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' (see~"Set") is silently applied to it first (see~"Set").



\>IsEqualSet( <list1>, <list2> ) O

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' (see~"Set") 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( <list1>, <list2> )' is equivalent to
`Set( <list1>  ) = Set( <list2> )' (see~"Set"),
but the former is more efficient.


\index{test!for set equality}
\beginexample
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
\endexample

\>IsSubsetSet( <list1>, <list2> ) O

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' (see~"Set") is applied to it first.



\>AddSet( <set>, <obj> ) O

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


\index{add!an element to a set}
\beginexample
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 ]
\endexample

\>RemoveSet( <set>, <obj> ) O

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.


\index{remove!an element from a set}
\beginexample
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 ]
\endexample

\>UniteSet( <set>, <list> ) O

unites the proper set <set> with <list>.
This is equivalent to adding all elements of <list> to <set>
(see~"AddSet").


\index{union!of sets}
\beginexample
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 ]
\endexample

\>IntersectSet( <set>, <list> ) O

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


\index{intersection!of sets}
\beginexample
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 ]
\endexample

\>SubtractSet( <set>, <list> ) O

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


\index{subtract!a set from another}
\beginexample
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 ]
\endexample

There are nondestructive counterparts of the functions `UniteSet',
`IntersectSet', and `SubtractSet' available for proper sets.
These are `UnionSet', `IntersectionSet', and `Difference'.
The former two are methods for the more general operations `Union'
and `Intersection' (see~"Union", "Intersection"),
the latter is itself an operation (see~"Difference").

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~"Identical Lists").

% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% % (from the GAP 3.4 manual)
% \Section{More about Sets}
% 
% In the previous section we defined a proper  set as a sorted list without
% holes or duplicates.  This representation is not  only nice to use, it is
% also a good internal representation supporting efficient algorithms.  For
% example the `in' operator can use binary instead of a linear search since
% a set is sorted.  For another example `Union' only has to merge the sets.
% 
% However, all  those set functions  also allow lists that are  not  proper
% sets,  silently making  a copy  of it and  converting this copy to a set.
% Suppose all the functions would have to test  their arguments every time,
% comparing  each element  with its  successor, to see if  they  are proper
% sets.  This would chew up most  of  the performance advantage again.  For
% example suppose `in' would have to run  over the whole list, to see if it
% is  a  proper set, so  it could  use the  binary search.   That  would be
% ridiculous.
% 
% To avoid this a  list that is  a proper set  may, but need  not, have  an
% internal flag set that tells  those functions that  this list is indeed a
% proper set.  Those functions do not have to check this argument then, and
% can use the more  efficient algorithms.  This  section tells  you  when a
% proper set obtains this flag,  so you can write your  functions in such a
% way that you make best use of the algorithms.
% 
% The results of `Set', `Difference', `Intersection'  and `Union' are known
% to be sets by construction, and thus have the flag set upon creation.
% 
% If an argument to `IsSet', `IsEqualSet', `IsSubset', `Set', `Difference',
% `Intersection' or  `Union' is a proper  set, that does  not  yet have the
% flag set, those functions will notice that and set the flag for this set.
% Note that `in' will use linear search if the  right operand does not have
% the flag set, will therefore not detect  if it is  a proper set and will,
% unlike the functions above, never set the flag.
% 
% If you change a proper set, that does have this  flag set, by assignment,
% `Add'   or `Append' the  set  will generally lose  it  flag,  even if the
% change is such that the resulting list is still a proper set.  However if
% the set has more than 100 elements and the value assigned or added is not
% a list and not a record and the resulting list is still a proper set than
% it will keep  the flag.  Note that  changing a list  that is not a proper
% set will never set the flag, even if the resulting list  is a proper set.
% Such a set will obtain the flag only if it is passed to a set function.
% 
% Suppose you have built a proper set  in such a way that  it does not have
% the flag set, and that you now want  to perform lots of membership tests.
% Then you  should call `IsSet'  with that set   as an argument.   If it is
% indeed  a proper set  `IsSet' will set the flag,  and the subsequent `in'
% operations will use  the more efficient binary  search.  You can think of
% the call to `IsSet' as a hint to {\GAP} that this list is a proper set.
% 
% There is no way you can set the flag for an ordinary  list  without going
% through the checking in `IsSet'.  The  internal  functions depend so much
% on the fact that a list with  this flag set  is indeed sorted and without
% holes and duplicates that the risk would be too high to allow setting the
% flag without such a check.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operations for Lists}

Several of the following functions expect the first argument to be either a
list or a collection (see~"Collections"), with possibly slightly different
meaning for lists and non-list collections.
For these functions, the list case is indicated by an argument named <list>,
and the collection case by one named <C>.

\>Concatenation( <list1>, <list2>, ... ) F
\>Concatenation( <list> ) F

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~"Identical Lists").

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


\index{concatenation!of lists}
\beginexample
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 ]
\endexample

\>Compacted( <list> ) O

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


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

\>Collected( <list> ) O

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.


\beginexample
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 ] ]
\endexample

\>DuplicateFreeList( <list> ) O
\>Unique( <list> ) O

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


\beginexample
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) ]) ]
\endexample

\>AsDuplicateFreeList( <list> ) A

returns the same result as `DuplicateFreeList' (see~"DuplicateFreeList"),
except that the result is immutable.



\>Flat( <list> ) O

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


\beginexample
gap> Flat( [ 1, [ 2, 3 ], [ [ 1, 2 ], 3 ] ] );
[ 1, 2, 3, 1, 2, 3 ]
gap> Flat( [ ] );
[  ]
\endexample
(To reconstruct a matrix from a `Flat'tened list, the sublist operator can
be used:
\beginexample
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 ] ]
\endexample
)

\>Reversed( <list> ) F

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

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

`Reversed' implements a special case of list assignment, which can also
be formulated in terms of the `{}' operator (see~"List Assignment").


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

\>IsLexicographicallyLess( <list1>, <list2> ) F

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



\>Apply( <list>, <func> ) F

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

`Apply' changes its argument.
The nondestructive counterpart of `Apply' is `List' (see~"List").


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

\>Perform( <list>, <func> ) O

`Perform( <list>, <func> )' applies func to every element of
<list>, discarding any return values. It does not return a value.


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

\>PermListList( <list1>, <list2> ) F

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


\beginexample
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 ]
\endexample

\>Maximum( <obj1>, <obj2> ... ) F
\>Maximum( <list> ) F

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


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

\>Minimum( <obj1>, <obj2> ... ) F
\>Minimum( <list> ) F

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

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


\beginexample
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 ]
\endexample

\>MaximumList( <list> ) O
\>MinimumList( <list> ) O

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



\>Cartesian( <list1>, <list2> ... ) F
\>Cartesian( <list> ) F

In the first form `Cartesian' returns the cartesian product of the lists
<list1>, <list2>, etc.

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

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

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

The function `Tuples' (see~"Tuples") computes the  <k>-fold cartesian
product of a list.


\beginexample
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 ] ]
\endexample

\>Permuted( <list>, <perm> ) O

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

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


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

\>List( <list> ) F
\>List( <C> ) F
\>List( <list>, <func> ) F

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

In the second form, where <C> is a collection (see~"Collections")
that is not a list,
`List' returns a new mutable list <new> such that `Length( <new> )'
is the number of different elements of <C>, and <new> contains the
different elements of <C> in an unspecified order which may change
for repeated calls.
`<new>[<pos>]' executes in constant time
(see~"IsConstantTimeAccessList"),
and the size of <new> is proportional to its length.
The generic method for this case is `ShallowCopy( Enumerator( <C> ) )'.

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


\beginexample
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 ]
\endexample

\>Filtered( <list>, <func> ) F
\>Filtered( <C>, <func> ) F

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

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

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

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

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


\beginexample
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) ]
\endexample

\>Number( <list> ) F
\>Number( <list>, <func> ) F
\>Number( <C>, <func> ) F

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

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

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

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


\beginexample
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
\endexample

\>First( <list>, <func> ) F

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

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


\beginexample
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
\endexample

\>ForAll( <list>, <func> ) F
\>ForAll( <C>, <func> ) F

tests whether the unary function <func> returns `true' for all elements
in the list <list> resp.~the collection <C>.


\beginexample
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
\endexample

\>ForAny( <list>, <func> ) F
\>ForAny( <C>, <func> ) F

tests whether the unary function <func> returns `true' for at least one
element in the list <list> resp.~the collection <C>.


\beginexample
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
\endexample

\>Product( <list>[, <init>] ) F
\>Product( <C>[, <init>] ) F
\>Product( <list>, <func>[, <init>] ) F
\>Product( <C>, <func>[, <init>] ) F

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

The general rules for arithmetic operations apply
(see~"Mutability Status and List Arithmetic"),
so the result is immutable if and only if all summands are immutable.

If <list> or <C> 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.


\beginexample
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)
\endexample

\>Sum( <list>[, <init>] ) F
\>Sum( <C>[, <init>] ) F
\>Sum( <list>, <func>[, <init>] ) F
\>Sum( <C>, <func>[, <init>] ) F

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

The general rules for arithmetic operations apply
(see~"Mutability Status and List Arithmetic"),
so the result is immutable if and only if all summands are immutable.

If <list> or <C> 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.


\beginexample
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)
\endexample

\>Iterated( <list>, <func> ) O

returns the result of the iterated application of the function <func>,
which must take two arguments, to the elements of the list <list>.
More precisely `Iterated' returns the result of the following
application,
$<f>(\cdots <f>( <f>( <list>[1], <list>[2] ), <list>[3] ), \ldots,
<list>[<n>] )$.


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

\>ListN( <list1>, <list2>, ..., <listn>, <f> ) F

Applies the <n>-argument function <func> to the lists.
That is, `ListN' returns the list whose <i>th entry is
$<f>(<list1>[<i>], <list2>[<i>], \ldots, <listn>[<i>])$.


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




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Advanced List Manipulations}

The following functions are generalizations of `List' (see~"List"),
`Set' (see~"Set"), `Sum' (see~"Sum"), and `Product' (see~"Product").

\>ListX( <arg1>, <arg2>, ... <argn>, <func> ) O

`ListX' returns a new list constructed from the arguments.

Each of the arguments `<arg1>, <arg2>, ... <argn>' must be one of the
following:
\beginitems
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.
\enditems

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( <list>, <func> )' is the same as `List( <list>, <func> )',
and `ListX( <list>, <func>, x -> x )' is the same as
`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

\)\kernttindent<result> := ListX( <arg1>, <arg2>, <arg3>, <arg4>, <func> );

is equivalent to

\){\kernttindent}<result> := [];
\){\kernttindent}for v1 in <arg1> do
\){\kernttindent\quad}if <arg2>( v1 ) then
\){\kernttindent\quad\quad}for v2 in <arg3>( v1 ) do
\){\kernttindent\quad\quad\quad}if <arg4>( v1, v2 ) then
\){\kernttindent\quad\quad\quad\quad}Add( <result>, <func>( v1, v2 ) );
\){\kernttindent\quad\quad\quad}fi;
\){\kernttindent\quad\quad}od;
\){\kernttindent\quad}fi;
\){\kernttindent}od;

\goodbreak%
The following example shows how `ListX' can be used to compute all pairs
and all strictly sorted pairs of elements in a list.
\beginexample
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 ] ]
\endexample
In the following example, `\<' is the comparison operation:
\beginexample
gap> ListX( l, l, \<, pair );
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
\endexample


\>SetX( <arg1>, <arg2>, ... <func> ) O

The only difference between `SetX' and `ListX' is that the result list of
`SetX' is strictly sorted.


\>SumX( <arg1>, <arg2>, ... <func> ) O

`SumX' returns the sum of the elements in the list obtained by
`ListX' when this is called with the same arguments.


\>ProductX( <arg1>, <arg2>, ... <func> ) O

`ProductX' returns the product of the elements in the list obtained by
`ListX' when this is called with the same arguments.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Ranges}

\index{range}
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>', `[<first>..<last>]' is the empty  list,  which  by
definition is also a range; also, if `<second> >  <first>  >  <last>'  or
`<second> \< <first> \< <last>', then `[<first>,<second>..<last>]' is the
empty list. If `<first>  =  <last>',  `[<first>,<second>..<last>]'  is  a
singleton list, which is a range, too. Note that `<last> - <first>'  must
be divisible by the increment `<second> - <first>', otherwise an error is
signalled.

Currently, the integers <first>, <second> and <last> and the length of a
range must be small integers, that is at least $-2^d$ and at most $2^d-1$ 
with $d=28$ on 32-bit architectures and $d=60$ on 64-bit architectures.

Note also that a range is just a special case of a list.
Thus you can access elements in a range (see "List Elements"), test for
membership etc.
You can even assign to such a range if it is mutable (see~"List Assignment").
Of course, unless you assign `<last> + <second>-<first>' to the entry
`<range>[Length(<range>)+1]', the resulting list will no longer be a range.

\beginexample
gap> r := [10..20];
[ 10 .. 20 ]
gap> Length( r );
11
gap> r[3];
12
gap> 17 in r;
true
gap> r[12] := 25;; r;  # r is no longer a range
[ 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 25 ]
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 ];
Range: <last>-<first> (31) must be divisible by <inc> (3)
\endexample

Most often ranges are used in connection with the `for'-loop (see~"For").
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.

\beginexample
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 ]
\endexample

Note that a range with `<last> >= <first>' is at the same time also a
proper set (see~"Sorted Lists and Sets"),
because it contains no holes or duplicates and is sorted,
and also a row vector (see~"Row Vectors"),
because it contains no holes and all elements are integers.

\>IsRange( <obj> ) C

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


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

\>ConvertToRangeRep( <list> ) F

For some lists the {\GAP} kernel knows that they are in fact ranges.
Those lists are represented internally in a compact way instead of the
ordinary way.

If <list> is a range then `ConvertToRangeRep' changes the representation
of <list> to this compact representation.

This is important since this representation needs only 12 bytes for
the entire range while the ordinary representation needs $4 length$
bytes.

Note that a list that is represented in the ordinary way might still be a
range.
It is just that {\GAP} does not know this.
The following rules tell you under which circumstances a range is
represented  in the compact way,
so you can write your program in such a way that you make best use of
this compact representation for ranges.

Lists created by the syntactic construct
`[ <first>, <second>  .. <last> ]' are of course known to be ranges and
are represented in the compact way.

If you call `ConvertToRangeRep' for a list represented the ordinary way
that is indeed a range, the representation is changed from the ordinary
to the compact representation.
A call of `ConvertToRangeRep' for a list that is not a range is
ignored.

If you change a mutable range that is represented in the compact way,
by assignment, `Add' or `Append', the range will be converted to the
ordinary representation, even if the change is such that the resulting
list is still a proper range.

Suppose you have built a proper range in such a way that it is
represented in the ordinary way and that you now want to convert it to
the compact representation to save space.
Then you should call `ConvertToRangeRep' with that list as an argument.
You can think of the call to `ConvertToRangeRep' as a hint to {\GAP}
that this list is a proper range.


\beginexample
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 ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Enumerators}

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, say, 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:

\>IsQuickPositionList( <list> ) F

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' in <list> and a bit list than
ordered lists to represent subsets  of <list>.



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~"Stabilizer Chains").

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~"Iterators").

The functions `Enumerator' and `EnumeratorSorted' (see~"Enumerator" and
"EnumeratorSorted") 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' (see~"EnumeratorByFunctions");
one generic example is `EnumeratorByBasis' (see~"EnumeratorByBasis"),
which can be used to get an enumerator of a finite dimensional free module.

Also enumerators for non-domains can be implemented via
`EnumeratorByFunctions'; for a discussion,
see~"prg:Example -- Constructing Enumerators" in ``Programming in {\GAP}''.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E