27 Lists

Lists are the most important way to collect objects and treat them together. A list is a collection of elements. A list also implies a partial mapping from the integers to the elements. I.e., there is a first element of a list, a second, a third, and so on.

List constants are written by writing down the elements in order between square brackets [, ], and separating them with commas ,. An empty list, i.e., a list with no elements, is written as [].

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

Usually a list has no holes, i.e., contain an element at every position. However, it is absolutely legal to have lists with holes. They are created by leaving the entry between the commas empty. Lists with holes are sometimes convenient when the list represents a mapping from a finite, but not consecutive, subset of the positive integers. We say that a list that has no holes is dense.

    gap> l := [ , 4, 9,, 25,, 49,,,, 121 ];;
    gap> l[3];
    9
    gap> l[4];
    Error, List Element: <list>[4] must have a value 

It is most common that a list contains only elements of one type. This is not a must though. It is absolutely possible to have lists whose elements are of different types. We say that a list whose elements are all of the same type is homogeneous.

    gap> l := [ 1, E(2), Z(3), (1,2,3), [1,2,3], "What a mess" ];;
    gap> l[1];  l[3];  l[5][2];
    1
    Z(3)
    2 

The first sections describe the functions that test if an object is a list and convert an object to a list (see IsList and List).

The next section describes how one can access elements of a list (see List Elements and Length).

List Assignment, Add, Append, Identical Lists, Enlarging Lists).

The next sections describe the operations applicable to lists (see Comparisons of Lists and Operations for Lists).

The next sections describe how one can find elements in a list (see In, Position, PositionSorted, PositionProperty).

The next sections describe the functions that construct new lists, e.g., sublists (see Concatenation, Flat, Reversed, Sublist, Cartesian).

The next sections describe the functions deal with the subset of elements of a list that have a certain property (see Number, Collected, Filtered, ForAll, ForAny, First).

The next sections describe the functions that sort lists (see Sort, SortParallel, Sortex, Permuted).

The next sections describe the functions to compute the product, sum, maximum, and minimum of the elements in a list (see Product, Sum, Maximum, Minimum, Iterated).

The final section describes the function that takes a random element from a list (see RandomList).

Lists are also used to represent sets, subsets, vectors, and ranges (see Sets, Boolean Lists, Vectors, and Ranges).

Subsections

  1. IsList
  2. List
  3. ApplyFunc
  4. List Elements
  5. Length
  6. List Assignment
  7. Add
  8. Append
  9. Identical Lists
  10. IsIdentical
  11. Enlarging Lists
  12. Comparisons of Lists
  13. Operations for Lists
  14. In
  15. Position
  16. PositionSorted
  17. PositionSet
  18. PositionProperty
  19. Concatenation
  20. Flat
  21. Reversed
  22. Sublist
  23. Cartesian
  24. Number
  25. Collected
  26. Filtered
  27. ForAll
  28. ForAny
  29. First
  30. Sort
  31. SortParallel
  32. Sortex
  33. SortingPerm
  34. PermListList
  35. Permuted
  36. Product
  37. Sum
  38. Maximum
  39. Minimum
  40. Iterated
  41. RandomList

27.1 IsList

IsList( obj )

IsList returns true if the argument obj, which can be an arbitrary object, is a list and false otherwise. Will signal an error if obj is an unbound variable.

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

27.2 List

List( obj )
List( list, func )

In its first form List returns the argument obj, which must be a list, a permutation, a string or a word, converted into a list. If obj is a list, it is simply returned. If obj is a permutation, List returns a list where the i-th element is the image of i under the permutation obj. If obj is a word, List returns a list where the i-th element is the i-th generator of the word, as a word of length 1.

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

In its second form List returns a new list, where each element is the result of applying the function func, which must take exactly one argument and handle the elements of list, to the corresponding element of the list list. The list list must not contain holes.

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

Note that this function is called map in Lisp and many other similar programming languages. This name violates the GAP rule that verbs are used for functions that change their arguments. According to this rule map would change list, replacing every element with the result of the application func to this argument.

27.3 ApplyFunc

ApplyFunc( func, arglist )

ApplyFunc invokes the function func as if it had been called with the elements of arglist as its arguments and returns the value, if any, returned by that invocation.

    gap> foo := function(arg1, arg2) 
    > Print("first ",arg1," second ",arg2,"\n"); end;
    function ( arg1, arg2 ) ... end
    gap> foo(1,2);
    first 1 second 2
    gap> ApplyFunc(foo,[1,2]);
    first 1 second 2
    gap> ApplyFunc(Position,[[1,2,3],2]);
    2 

27.4 List Elements

list[ pos ]

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.

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

If list does not evaluate to a list, or pos does not evaluate to a positive integer, or list[pos] is unbound an error is signalled. As usual you can leave the break loop (see Break Loops) with quit;. On the other hand you can return a result to be used in place of the list element by return expr;.

list{ poss }

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, it need, however, not be sorted and may contain duplicate elements. If for any i, list[ poss[i] ] is unbound, an error is signalled.

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

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

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

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

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

To be precise. With each selector [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

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

Then a selector list[pos] of level level is computed as ListElement(list,pos,level), where ListElement is defined as follows

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

and a selector list{poss} of level level is computed as ListElements(list,poss,level), where ListElements is defined as follows

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

27.5 Length

Length( list )

Length returns the length of the list list. The length is defined as 0 for the empty list, and as the largest positive integer index such that list[index] has an assigned value for nonempty lists. Note that the length of a list may change if new elements are added to it or assigned to previously unassigned positions.

    gap> Length( [] );
    0
    gap> Length( [ 2, 3, 5, 7, 11, 13, 17, 19 ] );
    8
    gap> Length( [ 1, 2,,, 5 ] );
    5 

For lists that contain no holes Length, Number (see Number), and Size (see Size) return the same value. For lists with holes Length returns the largest index of a bound entry, Number returns the number of bound entries, and Size signals an error.

27.6 List Assignment

list[ pos ] := object;

The list 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 list list. That means that accessing the pos-th element of the list list will return object after this assignment.

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

If the index 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.

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

The function Add (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. The ability to change an object is only available for lists and records (see Identical 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 (see Print), an error is signalled As usual you can leave the break loop (see Break Loops) with quit;. On the other hand you can continue the assignment by returning a list, an index or an object using return expr;.

list{ poss } := objects;

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

    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 ] 

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

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

The exact behaviour is defined in the same way as for list extractions (see 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

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

Then a list assignment list[pos] := vals; of level level is computed as ListAssignment( list, pos, vals, level ), where ListAssignment is defined as follows

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

and a list assignment list{poss} := vals of level level is computed as ListAssignments( list, poss, vals, level ), where ListAssignments is defined as follows

    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; 

27.7 Add

Add( list, elm )

Add adds the element elm to the end of the list list, i.e., it is equivalent to the assignment list[ Length(list) + 1 ] := elm. The list is automatically enlarged to make room for the new element. Add returns nothing, it is called only for its side effect.

Note that adding to a list changes the list. The ability to change an object is only available for lists and records (see Identical Lists).

To add more than one element to a list use Append (see Append).

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

27.8 Append

Append( list1, list2 )

Append adds (see Add) the elements of the list list2 to the end of the list list1. list2 may contain holes, in which case the corresponding entries in list1 will be left unbound. Append returns nothing, it is called only for its side effect.

    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 ] 

Note that appending to a list changes the list. The ability to change an object is only available for lists and records (see Identical Lists).

Note that Append changes the first argument, while Concatenation (see Concatenation) creates a new list and leaves its arguments unchanged. As usual the name of the function that work destructively is a verb, but the name of the function that creates a new object is a substantive.

27.9 Identical Lists

With the list assignment (see List Assignment, Add, Append) it is possible to change a list. The ability to change an object is only available for lists and records. This section describes the semantic consequences of this fact.

You may think that in the following example the second assignment changes the integer, and that therefore the above sentence, which claimed that only lists and records can be changed is wrong

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

But in this example not the integer 3 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

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

The second assignment does not change the first list, instead it assigns a new list to the variable l. On the other hand, in the following example the list is changed by the second assignment.

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

To understand the difference first 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.

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

But after the following example the list for which l2 is a name has been changed and thus the value of l2 is now [ 1, 2, 3 ].

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

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

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

If you enter a list literal than the list denoted by this literal is a new list that is not identical to any other list. Thus in the following example l1 and l2 are not identical, though they are equal of course.

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

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

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

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

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

If you pass a list as 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 list

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

The functions Copy and ShallowCopy (see Copy and ShallowCopy) accept a list and return a new list that is equal to the old list but that is not identical to the old list. The difference between Copy and ShallowCopy is that in the case of ShallowCopy the corresponding elements of the new and the old lists will be identical, whereas in the case of Copy they will only be equal. So in the following example l1 and l2 are not identical lists.

    l1 := [ 1, 2 ];
    l2 := Copy( l1 );

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

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

27.10 IsIdentical

IsIdentical( l, r )

IsIdentical returns true if the objects l and r are identical. Unchangeable objects are considered identical if the are equal. Changeable objects, i.e., lists and records, are identical if changing one of them by an assignment also changes the other one, as described in Identical Lists.

    gap> IsIdentical( 1, 1 );
    true
    gap> IsIdentical( 1, () );
    false
    gap> l := [ 'h', 'a', 'l', 'l', 'o' ];;
    gap> l = "hallo";
    true
    gap> IsIdentical( l, "hallo" );
    false 

27.11 Enlarging Lists

The previous section (see List Assignment) told you (among other things), that it is possible to assign beyond the logical end of a list, automatically enlarging the list. This section tells you how this is done.

It would be extremly 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, which is also called the size, of a list may be different from 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 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; 

27.12 Comparisons of Lists

list1 = list2
list1 < list2

The equality operator = evaluates to true if the two lists list1 and list2 are equal and false otherwise. The inequality operator < evaluates to true if the two lists are not equal and false otherwise. Two lists list1 and list2 are equal if and only if for every index i, either both entries list1[i] and list2[i] are unbound, or both are bound and are equal, i.e., list1[i] = list2[i] is true.

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

list1 < list2, list1 <= list2 list1 list2, list1 = list2

The operators <, <=, and = evaluate to true if the list list1 is less than, less than or equal to, greater than, or greater than or equal to the list list2 and to false otherwise. Lists are ordered lexicographically, with unbound entries comparing very small. That means the following. Let i be the smallest positive integer i, such that neither both entries list1[i] and list2[i] are unbound, nor both are bound and equal. Then list1 is less than list2 if either list1[i] is unbound (and list2[i] is not) or both are bound and list1[i] < list2[i] is true.

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

You can also compare objects of other types, for example integers or permutations with lists. Of course those objects are never equal to a list. Records (see Records) are greater than lists, objects of every other type are smaller than lists.

    gap> 123 < [ 1, 2, 3 ];
    true
    gap> [ 1, 2, 3 ] < rec( a := 123 );
    true 

27.13 Operations for Lists

list * obj
obj * list

The operator * evaluates to the product of list list by an object obj. The product is a new list that at each position contains the product of the corresponding element of list by obj. list may contain holes, in which case the result will contain holes at the same positions.

The elements of list and obj must be objects of the following types; integers (see Integers), rationals (see Rationals), cyclotomics (see Cyclotomics), elements of a finite field (see Finite Fields), permutations (see Permutations), matrices (see Matrices), words in abstract generators (see Words in Abstract Generators), or words in solvable groups (see Words in Finite Polycyclic Groups).

    gap> [ 1, 2, 3 ] * 2;
    [ 2, 4, 6 ]
    gap> 2 * [ 2, 3,, 5,, 7 ];
    [ 4, 6,, 10,, 14 ]
    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) ] 

Many more operators are available for vectors and matrices, which are Operations for Matrices).

27.14 In

elm in list

The in operator evaluates to true if the object elm is an element of the list list and to false otherwise. elm is an element of list if there is a positive integer index such that list[index]=elm is true. elm may be an object of an arbitrary type and list may be a list containing elements of any type.

It is much faster to test for membership for sets, because for sets, which are always sorted (see Sets), in can use a binary search, instead of the linear search used for ordinary lists. So if you have a list for which you want to perform a large number of membership tests you may consider converting it to a set with the function Set (see Set).

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

Position (see Position) and PositionSorted (see PositionSorted) allow you to find the position of an element in a list.

27.15 Position

Position( list, elm ) Position( list, elm, after )

Position returns the position of the element elm, which may be an object of any type, in the list list. If the element is not in the list the result is false. If the element appears several times, the first position is returned.

The three argument form begins the search at position after+1, and returns the position of the next occurence of elm. If there are no more, it returns false.

It is much faster to search for an element in a set, because for sets, which are always sorted (see Sets), Position can use a binary search, instead of the linear search used for ordinary lists. So if you have a list for which you want to perform a large number of searches you may consider converting it to a set with the function Set (see Set).

    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 );
    false
    gap> Position( [ 4, -1, 0, 3 ],  1 );
    false
    gap> s := Set([2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32]);;
    gap> Position( s,  17 );
    false        # uses binary search and only 4 comparisons
    gap> Position( [ "This", "is", "a", "list", "of", "strings" ],  1 );
    false
    gap> Position( [ [0,6], [0,4], [1,3], [1,5], [1,2], [3,4] ],  [1,2] );
    5 

The in operator (see In) can be used if you are only interested to know whether the element is in the list or not. PositionSorted (see PositionSorted) can be used if the list is sorted. PositionProperty (see PositionProperty) allows you to find the position of an element that satisfies a certain property in a list.

27.16 PositionSorted

PositionSorted( list, elm )
PositionSorted( list, elm, func )

In the first form PositionSorted returns the position of the element elm, which may be an object of any type, with respect to the sorted list list.

In the second form PositionSorted returns the position of the element elm, which may be an object of any type with respect to 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 <= 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.

    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 

Position (see Position) is another function that returns the position of an element in a list. Position accepts unsorted lists, uses linear instead of binary search and returns false if elm is not in list.

27.17 PositionSet

PositionSet( list, elm )
PositionSet( list, elm, func )

In the first form PositionSet returns the position of the element elm, which may be an object of any type, with respect to the sorted list list.

In the second form PositionSet returns the position of the element elm, which may be an object of any type with respect to 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.

PositionSet returns pos such that list[pos-1] < elm and elm = 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, then false is returned.

    gap> PositionSet( [1,4,5,5,6,7], 0 );
    false
    gap> PositionSet( [1,4,5,5,6,7], 2 );
    false
    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 );
    false 

PositionSet is very similar to PositionSorted (see PositionSorted) but returns false when elm is not an element of list.

27.18 PositionProperty

PositionProperty( list, func )

PositionProperty returns the position of the first element in the list list for which the unary function func returns true. list must not contain holes. If func returns false for all elements of list false is returned. func must return true or false for every element of list, otherwise an error is signalled.

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

First (see First) allows you to extract the first element of a list that satisfies a certain property.

27.19 Concatenation

Concatenation( list1, list2.. )
Concatenation( list )

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.

    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 ] 

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

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

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 lists (see Identical Lists).

Note that Concatenation creates a new list and leaves it arguments unchanged, while Append (see Append) changes its first argument. As usual the name of the function that works destructively is a verb, but the name of the function that creates a new object is a substantive.

Set(Concatenation(set1,set2..)) (see Set) is a way to compute the union of sets, however, Union (see Union) is more efficient.

27.20 Flat

Flat( list )

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

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

27.21 Reversed

Reversed( list )

Reversed returns a new list that contains the elements of the list list, which must not contain holes, in reverse order. The argument list is unchanged.

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

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

27.22 Sublist

Sublist( list, inds )

Sublist returns a new list in which the i-th element is the element list[ inds[ i ] ], of the list list. inds must be a list of positive integers without holes, it need, however, not be sorted and may contains duplicate elements. If list[ inds[ i ] ] is unbound for an i, an error is signalled.

    gap> Sublist( [ 2, 3, 5, 7, 11, 13, 17, 19 ], [4..6] );
    [ 7, 11, 13 ]
    gap> Sublist( [ 2, 3, 5, 7, 11, 13, 17, 19 ], [1,7,1,8] );
    [ 2, 17, 2, 19 ] 

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

Filtered (see Filtered) allows you to extract elements from a list according to a predicate.

Sublist has been made obsolete by the introduction of the construct list{ inds } (see List Elements).

27.23 Cartesian

Cartesian( list1, list2.. )
Cartesian( list )

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 set if and only if all argument lists are sets.

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

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

27.24 Number

Number( list )
Number( list, func )

In the first form Number returns the number of bound entries in the list list.

For lists that contain no holes 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.

Number returns the number of elements of the list list 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 several times. func must return either true or false for every element of list, otherwise an error is signalled.

    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 
Filtered (see Filtered) allows you to extract the elements of a list that have a certain property.

27.25 Collected

Collected( list )

Collected returns a new list new that contains for each different element elm of list a list of two elements, the first element 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.

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

27.26 Filtered

Filtered( list, func )

Filtered returns a new list that contains those elements of the list list for which the unary function func returns true. 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. func must return either true or false for every element of list, otherwise an error is signalled.

    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 ] 

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

Sublist (see Sublist) allows you to extract elements of a list according to indices given in another list.

27.27 ForAll

ForAll( list, func )

ForAll returns true if the unary function func returns true for all elements of the list list and false otherwise. list may contain holes. func must return either true or false for every element of list, otherwise an error is signalled.

    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 

ForAny (see ForAny) allows you to test if any element of a list satisfies a certain property.

27.28 ForAny

ForAny( list, func )

ForAny returns true if the unary function func returns true for at least one element of the list list and false otherwise. list may contain holes. func must return either true or false for every element of list, otherwise ForAny signals an error.

    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 

ForAll (see ForAll) allows you to test if all elements of a list satisfies a certain propertie.

27.29 First

First( list, func )

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 every element of list, otherwise an error is signalled. If func returns false for every element of list an error is signalled.

    gap> First( [10^7..10^8], IsPrime );
    10000019
    gap> First( [10^5..10^6],
    >           n -> not IsPrime(n) and IsPrimePowerInt(n) );
    100489 

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

27.30 Sort

Sort( list )
Sort( list, func )

Sort sorts the list list in increasing order, using shellsort. In the first form Sort uses the operator < to compare the elements. In the second form Sort uses the function func to compare elements. This function must be a function taking two arguments that returns true if the first is strictly smaller than the second and false otherwise.

Sort does not return anything, since it 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.

    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 ); list;
    [ [ 1, 2 ], [ 1, 3 ], [ 0, 4 ], [ 3, 4 ], [ 1, 5 ], [ 0, 6 ] ]
    #  sorted according to the Euclidian distance from [0,0]
    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 ); list;
    [ [ 0, 6 ], [ 0, 4 ], [ 1, 3 ], [ 1, 5 ], [ 1, 2 ], [ 3, 4 ] ]
    # note the random order of the elements with equal first component 

SortParallel (see SortParallel) allows you to sort a list and apply the exchanges that are necessary to another list in parallel. Sortex (see Sortex) sorts a list and returns the sorting permutation.

27.31 SortParallel

SortParallel( list1, list2 )
SortParallel( list1, list2, func )

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

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

Sortex (see Sortex) sorts a list and returns the sorting permutation.

27.32 Sortex

Sortex( list )

Sortex sorts the list list and returns the permutation that must be applied to list to obtain the sorted list.

    gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
    gap> list2 := Copy( 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 ] 

Permuted (see Permuted) allows you to rearrange a list according to a given permutation.

27.33 SortingPerm

SortingPerm( list )

SortingPerm returns the permutation that must be applied to list to sort it into ascending order.

    gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
    gap> list2 := Copy( 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 ] 

Sortex( list ) (see Sortex) returns the same permutation as SortingPerm( list ), and also applies it to list (in place).

27.34 PermListList

PermListList( list1, list2 )

PermListList returns a permutation that may be applied to list1 to obtain list2, if there is one. Otherwise it returns false.

    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 ] 

27.35 Permuted

Permuted( list, perm )

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

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

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

27.36 Product

Product( list )
Product( list, func )

In the first form Product returns the product of the elements of the list list, which must have no holes. If list is empty, the integer 1 is returned.

In the second form Product applies the function func to each element of the list list, which must have no holes, and multiplies the results. If the list is empty, the integer 1 is returned.

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

Sum (see Sum) computes the sum of the elements of a list.

27.37 Sum

Sum( list )
Sum( list, func )

In the first form Sum returns the sum of the elements of the list list, which must have no holes. If list is empty 0 is returned.

In the second form Sum applies the function func to each element of the list list, which must have no holes, and sums the results. If the list is empty 0 is returned.

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

Product (see Product) computes the product of the elements of a list.

27.38 Maximum

Maximum( obj1, obj2.. )
Maximum( list )

Maximum returns the maximum of its arguments, i.e., that argument obj_i for which obj_k <= obj_i for all k. In its second form Maximum takes a list list and returns the maximum of the elements of this list.

Typically the arguments or elements of the list respectively will be integers, but actually they can be objects of an arbitrary type. This works because any two objects can be compared using the < operator.

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

27.39 Minimum

Minimum( obj1, obj2.. )
Minimum( list )

Minimum returns the minimum of its arguments, i.e., that argument obj_i for which obj_i <= obj_k for all k. In its second form Minimum takes a list list and returns the minimum of the elements of this list.

Typically the arguments or elements of the list respectively will be integers, but actually they can be objects of an arbitrary type. This works because any two objects can be compared using the < operator.

    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 ]        # lists are compared elementwise 

27.40 Iterated

Iterated( list, f )

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

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

27.41 RandomList

RandomList( list )

RandomList returns a random element of the list list. The results are equally distributed, i.e., all elements are equally likely to be selected.

    gap> RandomList( [1..200] );
    192
    gap> RandomList( [1..200] );
    152
    gap> RandomList( [ [ 1, 2 ], 3, [ 4, 5 ], 6 ] );
    [ 4, 5 ] 

RandomSeed( n )

RandomSeed seeds the pseudo random number generator RandomList. Thus to reproduce a computation exactly you can call RandomSeed each time before you start the computation. When GAP is started the pseudo random number generator is seeded with 1.

    gap> RandomSeed(1);  RandomList([1..100]);  RandomList([1..100]);
    96
    76
    gap> RandomSeed(1);  RandomList([1..100]);  RandomList([1..100]);
    96
    76 

RandomList is called by all random functions for domains (see Random).

Previous Up Next
Index

GAP 3.4.4
April 1997