Macaulay2 » Documentation
Packages » Macaulay2Doc » The Macaulay2 language » lists and sequences
next | previous | forward | backward | up | index | toc

# lists and sequences -- a detailed overview of lists and sequences in Macaulay2

This page gives an overview of the use of lists of all types, including:

basic lists (of class BasicList),
visible lists (of class VisibleList),
lists (of class List),
sequences (of class Sequence),
arrays (of class Array), angle bar lists (of class AngleBarList), and
mutable lists (of class MutableList).

The sections of the overview are, in order:

Creating lists; kinds of lists.
Elements and indexing.
Nested lists.
Ranges and repetitions.
Manipulating lists and sequences.
Mapping over lists.
Conditional expressions; selecting elements matching a criterion.

Links to individual documentation pages for the functions described in this article are collected in an alphabetized list at the very end of the page.

Creating lists; kinds of lists.

To create a list, use curly braces around a comma-separated series of elements.

    i1 : L = {a,b,c,d,e}

    o1 = {a, b, c, d, e}

    o1 : List

Sequences are created and displayed using parentheses instead of braces.

    i2 : S = (a,b,c,d,e)

    o2 = (a, b, c, d, e)

    o2 : Sequence

Sequences are implemented in a more efficient way than lists, since a sequence is created every time a function is called with more than one argument. On the other hand, parentheses are also used for grouping algebraic expressions. This complicates some tasks, such as creating a sequence of length 1.

    i3 : ()

    o3 = ()

    o3 : Sequence

    i4 : (1,2)

    o4 = (1, 2)

    o4 : Sequence

    i5 : (1)

    o5 = 1

The functions toList and toSequence, which convert between lists and sequences, may be useful here.

    i6 : toSequence {1}

    o6 = 1 : (1)

    o6 : Sequence

Lists can be used as vectors, provided their elements are the sorts of things that can be added and multiplied.

    i7 : 10000*{3,4,5} + {1,2,3}

    o7 = {30001, 40002, 50003}

    o7 : List

An array is another type of list, created and displayed using square brackets. Unlike lists and sequences, arrays can't be used as vectors. Their main use is notational; for example, they appear in the construction of polynomial rings.

    i8 : v = [1,2,3]

    o8 = [1, 2, 3]

    o8 : Array

    i9 : ZZ[a,b,c]

    o9 = ZZ[a..c]

    o9 : PolynomialRing

An angle bar list is another type of list, created and displayed using angle bars. They are used in much the same way as arrays are.

    i10 : v = <|1,2,3|>

    o10 = <|1, 2, 3|>

    o10 : AngleBarList

    i11 : v#1

    o11 = 2

Lists, sequences, and arrays are the three examples of what we call visible lists, which constitute the class VisibleList. Many functions are defined to act uniformly on visible lists. There is a type of list more general than a visible list, which we call a BasicList. Basic lists are a secure choice for defining new datatypes, since the many functions that act on visible lists do not act on basic lists. Here we illustrate how to create a new type of basic list, in this case called Container.

    i12 : Container = new Type of BasicList

    o12 = Container

    o12 : Type

    i13 : t = new Container from {a,b}

    o13 = Container{a, b}

    o13 : Container

We can then declare a new method for the operator ++ that will join two Containers:

    i14 : Container ++ Container := join;

    i15 : t ++ t

    o15 = Container{a, b, a, b}

    o15 : Container

Basic lists are normally immutable; that is, no element can be replaced, added, or removed. (Functions like append, and the many others described in the Manipulating lists and sequences section, will return a new list in Macaulay2, as a general rule, rather than modify the existing list.)

However, there is a certain type of basic list, called a mutable list (of class MutableList), whose elements can be changed. This allows the possibility of creating circular structures that would cause a print routine to go into an infinite loop. To avoid such infinite loops, the contents of mutable lists are not printed. Instead, use peek to display the elements in a controlled way.

    i16 : A = new MutableList from {a,b,c}

    o16 = MutableList{...3...}

    o16 : MutableList

    i17 : peek A

    o17 = MutableList{a, b, c}

    i18 : A#2 = 1234;

    i19 : A

    o19 = MutableList{...3...}

    o19 : MutableList

    i20 : peek A

    o20 = MutableList{a, b, 1234}

Because the contents of mutable lists are not printed, they can be used as containers for big things one doesn't want to print. Although any mutable list can be used in this way, there is a a special type of mutable list called a Bag, which is designed for this purpose. When printed, the bag displays only a little information about its contents.

    i21 : r = Bag {100!}; r

    o22 = -*a bagged integer*-

    o22 : Bag

    i23 : q = Bag {1/100!}; q

    o24 = -*a bagged rational number*-

    o24 : Bag

    i25 : unbag q

    o25 = -----------------------------------------------------------------------
          93326215443944152681699238856266700490715968264381621468592963895217599
          =======================================================================
                  1
          -----------------------------------------------------------------------
          99322991560894146397615651828625369792082722375825118521091686400000000
          =======================================================================
          ----------------
          0000000000000000

    o25 : QQ

The hierarchy of types mentioned above is summarized here using showStructure:

    i26 : showStructure(List,Sequence,Array,Container,MutableList,Bag,BasicList)

    o26 = Thing : BasicList : Container
                              MutableList : Bag
                              VisibleList : Array
                                            List
                                            Sequence

    o26 : Descent

Elements and indexing.

We retrieve the length of a list with the operator # or with the function length.

    i27 : L = {926, 621, 429, 67, 594, 904, 264, 18, 35, 961};

    i28 : #L

    o28 = 10

    i29 : length L

    o29 = 10

The expression $L\#n$ returns the $n$th element of $L$. The elements are numbered consecutively starting with 0. Alternatively, they are numbered consecutively ending with -1.

    i30 : L#0

    o30 = 926

    i31 : L#2

    o31 = 429

    i32 : L#-1

    o32 = 961

The _ operator is similar to #, except that it can also take a list or range of indices. However, it may only be used with visible lists.

    i33 : L_1

    o33 = 621

    i34 : L_{3,6}

    o34 = {67, 264}

    o34 : List

The functions first and last retrieve the first and last elements of a list.

    i35 : first L

    o35 = 926

    i36 : last L

    o36 = 961

Omitting an element of a list causes the symbol null to be inserted in its place. When the value of an expression is null, like when we ask for A#2 in the next example, the output line doesn't appear at all.

    i37 : A = {3,4,,5}

    o37 = {3, 4, , 5}

    o37 : List

    i38 : peek A

    o38 = {3, 4, null, 5}

    i39 : A#2

Ranges and repetitions.

The operator .. can be used to create sequences of numbers, sequences of subscripted variables, and so on.

    i40 : 1 .. 5, x_1 .. x_5, a .. e

    o40 = ((1, 2, 3, 4, 5), (x , x , x , x , x ), (a, b, c, d, e))
                              1   2   3   4   5

    o40 : Sequence

The operator ZZ : Thing creates a sequence by replicating an element a given number of times.

    i41 : 12:a

    o41 = (a, a, a, a, a, a, a, a, a, a, a, a)

    o41 : Sequence

Replicating something once is another way to create a sequence of length 1, which cannot be entered by simply typing parentheses.

    i42 : 1:a

    o42 = 1 : (a)

    o42 : Sequence

Both .. and : produce sequences, and may not behave as expected with respect to nesting. For instance, to create the list \{3, 4, 5, 6, 9, 12, 12, 12\}, the following command will not work:

    i43 : A = {3 .. 6, 9, 3:12}

    o43 = {(3, 4, 5, 6), 9, (12, 12, 12)}

    o43 : List

Instead, we get a list of length 3, some of whose elements are sequences. This is easily resolved with splice.

    i44 : A = splice {3..6, 9, 3:12}

    o44 = {3, 4, 5, 6, 9, 12, 12, 12}

    o44 : List

However, many operators and functions will automatically splice lists for you. Two examples are the array of variables defining a polynomial ring, and the indices passed to the _ operator.

    i45 : QQ[a..c,x_1..x_4]

    o45 = QQ[a..c, x ..x ]
                    1   4

    o45 : PolynomialRing

    i46 : L_{1..3,-3..-1}

    o46 = {621, 429, 67, 18, 35, 961}

    o46 : List

Nested lists.

When the elements of a list are themselves lists, we call it a nested list.

    i47 : A = {{a,b,c},{d,{e,f}}}

    o47 = {{a, b, c}, {d, {e, f}}}

    o47 : List

    i48 : #A

    o48 = 2

    i49 : #(first A)

    o49 = 3

One level of nesting may be eliminated with flatten.

    i50 : flatten A

    o50 = {a, b, c, d, {e, f}}

    o50 : List

The function splice acts analogously on sequences, removing those pairs of parentheses that are one level inward.

    i51 : splice (a, (b, c), (d, (e, f, (g, h))) )

    o51 = (a, b, c, d, (e, f, (g, h)))

    o51 : Sequence

To remove all layers of nesting at once, use deepSplice.

    i52 : deepSplice (a, (b, c), (d, (e, f, (g, h))) )

    o52 = (a, b, c, d, e, f, g, h)

    o52 : Sequence

A table is a list whose elements are lists all of the same length. The inner lists are regarded as rows when the table is displayed as a two-dimensional array with MatrixExpression.

    i53 : T = {{a,1},{b,2},{c,3}}

    o53 = {{a, 1}, {b, 2}, {c, 3}}

    o53 : List

    i54 : isTable T

    o54 = true

    i55 : MatrixExpression T

    o55 = | a 1 |
          | b 2 |
          | c 3 |

    o55 : Expression of class MatrixExpression

The function table can be used to create a table (doubly nested list) from two lists and a function of two arguments. It applies the function consecutively to each element from the first list paired with each element from the second list, so the total number of evaluations of the function is the product of the lengths of the two lists.

    i56 : table({1,2,3},{7,8},(i,j) -> 1000*i+j)

    o56 = {{1007, 1008}, {2007, 2008}, {3007, 3008}}

    o56 : List

The function pack(L, n) turns the list $L$ into a nested list, whose elements are lists containing the elements of $L$ taken $n$ at a time.

    i57 : pack(1..15, 4)

    o57 = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15}}

    o57 : List

On the other hand, mingle(L) takes the nested list $L = \{L_1, L_2, \ldots, L_n\}$ and combines the elements of the $L_i$ into a single list in the following way:

    i58 : mingle({{1,2,3,4}, {10,20,30,40}, {100,200,300,400}, {a, b}})

    o58 = {1, 10, 100, a, 2, 20, 200, b, 3, 30, 300, 4, 40, 400}

    o58 : List

Manipulating lists and sequences.

Use append(L, x) to create a copy of $L$ with the element $x$ added to the end. Since lists are immutable in Macaulay2, $L$ itself is not changed, unless redefined.

    i59 :

          L = {926, 621, 429, 67, 594, 904, 264, 18, 35, 961};

    i60 : append(L, -10)

    o60 = {926, 621, 429, 67, 594, 904, 264, 18, 35, 961, -10}

    o60 : List

    i61 : L

    o61 = {926, 621, 429, 67, 594, 904, 264, 18, 35, 961}

    o61 : List

    i62 : L = append(L, -10); L

    o63 = {926, 621, 429, 67, 594, 904, 264, 18, 35, 961, -10}

    o63 : List

Use prepend(x, L) to create a copy of $L$ with $x$ added to the beginning of the list. Notice the order of arguments is the opposite of append!

    i64 : L = prepend(-20, L)

    o64 = {-20, 926, 621, 429, 67, 594, 904, 264, 18, 35, 961, -10}

    o64 : List

Use insert(n, x, L) to specify that the element $x$ should be added to the list $L$ at position $n$.

    i65 : L = insert(5, -30, L)

    o65 = {-20, 926, 621, 429, 67, -30, 594, 904, 264, 18, 35, 961, -10}

    o65 : List

Use switch(m, n, L) to switch the elements of $L$ in indices $m$ and $n$.

    i66 : L = switch(1, 2, L)

    o66 = {-20, 621, 926, 429, 67, -30, 594, 904, 264, 18, 35, 961, -10}

    o66 : List

The function delete removes elements that have a particular value, NOT a particular index.

    i67 : L = delete(-10, L)

    o67 = {-20, 621, 926, 429, 67, -30, 594, 904, 264, 18, 35, 961}

    o67 : List

To remove the element at index $n$, use the command drop(L, \{n,n\}).

    i68 : L = drop(L, {1,1})

    o68 = {-20, 926, 429, 67, -30, 594, 904, 264, 18, 35, 961}

    o68 : List

You can also use drop to remove a specified number of elements from the beginning or end of $L$.

    i69 : L = drop(L, 2)

    o69 = {429, 67, -30, 594, 904, 264, 18, 35, 961}

    o69 : List

    i70 : L = drop(L, -2)

    o70 = {429, 67, -30, 594, 904, 264, 18}

    o70 : List

On the other hand, use take to specify the number of elements to keep, or a range of indices to keep:

    i71 : L = take(L, 6)

    o71 = {429, 67, -30, 594, 904, 264}

    o71 : List

    i72 : L = take(L, {1,4})

    o72 = {67, -30, 594, 904}

    o72 : List

Use between(x, L) to insert the element $x$ between every two elements of $L$.

    i73 : L = between(-5, L)

    o73 = {67, -5, -30, -5, 594, -5, 904}

    o73 : List

Useful commands for reordering lists are reverse (reverse the current order), sort (put elements in ascending order), and rsort (put elements in descending order).

    i74 : L

    o74 = {67, -5, -30, -5, 594, -5, 904}

    o74 : List

    i75 : reverse L

    o75 = {904, -5, 594, -5, -30, -5, 67}

    o75 : List

    i76 : sort L

    o76 = {-30, -5, -5, -5, 67, 594, 904}

    o76 : List

    i77 : rsort L

    o77 = {904, 594, 67, -5, -5, -5, -30}

    o77 : List

Use unique to remove duplicates from a list or sequence.

    i78 : unique L

    o78 = {67, -5, -30, 594, 904}

    o78 : List

Use join to concatenate two lists or sequences. The symbol | is also used for concatenation.

    i79 : join(a..f, 1..6)

    o79 = (a, b, c, d, e, f, 1, 2, 3, 4, 5, 6)

    o79 : Sequence

    i80 : x_1..x_3 | y_1..y_4

    o80 = (x , x , x , y , y , y , y )
            1   2   3   1   2   3   4

    o80 : Sequence

Mapping over lists.

In programming, loops that operate on consecutive elements of a list are common, so we offer various ways to apply functions to each of the elements of a list, along with various ways to treat the returned values.

The most basic operation is provided by scan, which applies a function consecutively to each element of a list, discarding the values returned.

    i81 : scan({a,b,c}, print)
    a
    b
    c

The keyword break can be used to terminate the scan prematurely, and optionally to specify a return value for the expression. Here we use it to locate the first even number in a list.

    i82 : scan({3,5,7,11,44,55,77}, i -> if even i then break i)

    o82 = 44

The function apply is similar to scan, but creates a list storing the values returned.

    i83 : apply({1,2,3,4}, i -> i^2)

    o83 = {1, 4, 9, 16}

    o83 : List

This operation is so common that we offer two shorthand notations for it, one with the function on the right and one with the function on the left.

    i84 : {1,2,3,4} / (i -> i^2)

    o84 = {1, 4, 9, 16}

    o84 : List

    i85 : (i -> i^2) \ {1,2,3,4}

    o85 = {1, 4, 9, 16}

    o85 : List

The associativity of these operators during parsing is set up so the following code works as one would wish.

    i86 : {1,2,3,4} / (i -> i^2) / (j -> 1000*j)

    o86 = {1000, 4000, 9000, 16000}

    o86 : List

    i87 : (j -> 1000*j) \ (i -> i^2) \ {1,2,3,4}

    o87 = {1000, 4000, 9000, 16000}

    o87 : List

    i88 : (j -> 1000*j) @@ (i -> i^2) \ {1,2,3,4}

    o88 = {1000, 4000, 9000, 16000}

    o88 : List

The function apply can also be used with two lists of the same length, in which case it will apply the function consecutively to corresponding elements of the two lists.

    i89 : apply({1,2,3}, {7,8,9}, (i,j) -> 1000*i+j)

    o89 = {1007, 2008, 3009}

    o89 : List

The function applyTable can be used to apply a function to each element of a table.

    i90 : applyTable( {{1,2,3},{4,5}}, i -> i^2)

    o90 = {{1, 4, 9}, {16, 25}}

    o90 : List

The functions fold and accumulate provide various ways to iteratively apply a function of two arguments to the elements of a list. One of the arguments is the next element from the list, and the other argument is the value returned by the previous application of the function. As an example, suppose we want to convert the list \{7,3,5,4,2\} of digits into the corresponding number 73542. The formula (((7*10+3)*10+5)*10+4)+2 is a fast way to do it that doesn't involve computing high powers of 10 separately. We can do this with fold and the following code.

    i91 : fold((i,j) -> i*10+j, {7,3,5,4,2})

    o91 = 73542

Using accumulate returns all the intermediate values of this iterative calculation along with the final result.

    i92 : accumulate((i,j) -> i*10+j, {7,3,5,4,2})

    o92 = {73, 735, 7354, 73542}

    o92 : List

Conditional expressions; selecting elements matching a criterion.

Use select to select those elements from a list that satisfy some condition.

    i93 : select({12, 3, -10, 42, 7, 6, 53}, even)

    o93 = {12, -10, 42, 6}

    o93 : List

    i94 : select({12, 3, -10, 42, 7, 6, 53}, i -> i<0 or i>40)

    o94 = {-10, 42, 53}

    o94 : List

An optional first argument of an integer $n$ specifies to select no more than $n$ matching elements.

    i95 : select(2, {12, 3, -10, 42, 7, 6, 53}, even)

    o95 = {12, -10}

    o95 : List

Use positions to select the indices of elements satisfying the condition.

    i96 : positions({12, 3, -10, 42, 7, 6, 53}, i -> i<0 or i>40)

    o96 = {2, 3, 6}

    o96 : List

The singular position returns only the first (or last, by specifying Reverse => true) matching index.

    i97 : position({12, 3, -10, 42, 7, 6, 53}, i -> i<0 or i>40)

    o97 = 2

    i98 : position({12, 3, -10, 42, 7, 6, 53}, i -> i<0 or i>40, Reverse => true)

    o98 = 6

Use number to count how many elements satisfy the condition.

    i99 : number({12, 3, -10, 42, 7, 6, 53}, i -> i<0 or i>40)

    o99 = 3

Use max and min to find the maximum or minimum of the list. The functions maxPosition and minPosition give the index of the maximum/minimum. Note that max and min work with many Macaulay2 types besides numbers, for instance elements of a polynomial ring with respect to a monomial order.

    i100 : R = QQ[x,y,z, MonomialOrder => Lex];

    i101 : max {x^2*y*z, x*y^3*z^2, x^3, y^3, z}

            3
    o101 = x

    o101 : R

    i102 : maxPosition {x^2*y*z, x*y^3*z^2, x^3, y^3, z}

    o102 = 2

    i103 : min {x^2*y*z, x*y^3*z^2, x^3, y^3, z}

    o103 = z

    o103 : R

    i104 : minPosition {x^2*y*z, x*y^3*z^2, x^3, y^3, z}

    o104 = 4

We may use any to tell whether there is at least one element of a list satisfying a condition, and all to tell whether all elements satisfy it.

    i105 : any({3, 6, 7, 8}, even)

    o105 = true

    i106 : all({3, 6, 7, 8}, even)

    o106 = false

## See also

- BasicList #? ZZ -- check existence of value in a list, hash table, database, or string
- Set -- the class of all sets

### Menu

#### Types of lists

- BasicList -- the class of all basic lists
- VisibleList -- the class of all visible lists
- MutableList -- the class of all mutable lists

#### Information about lists

- length(VisibleList) -- length of a visible list
- # List -- length or cardinality of a list, hash table, dictionary, set, or string
- isEmpty -- whether an object is empty

#### Accessing list elements

- List # ZZ -- get value from list, hash table, database, dictionary, or string
- VisibleList _ ZZ -- get element from list
- VisibleList _ List -- get some entries of a list
- drop -- drop some elements from a list or sequence
- take -- take some elements from a list or sequence
- first -- first element of a list
- last -- last element of a list

#### Creating simple lists

- ZZ .. ZZ -- sequences of consecutive integers
- ZZ ..< ZZ -- sequences of consecutive integers
- ZZ : Thing -- repeat an item

#### Iterating over lists

- VisibleList / Function -- apply a function to elements of a list
- VisibleList // Function -- apply a function
- scan -- apply a function to each element in a list or sequence
- apply -- apply a function to each element
- fold -- apply a binary operator repeatedly
- accumulate -- apply a binary operator repeatedly
- ultimate -- ultimate value for an iteration

#### Creating iterators

- Iterator -- class for iterators

#### Searching in lists

- all -- whether all elements satisfy a specified condition
- any -- whether any elements satisfy a specified condition
- same -- whether everything in a list is the same
- uniform -- whether all elements of a list are the same class
- select -- select from a list, hash table, or string
- isMember -- test membership in a list or set
- isSubset -- whether one object is a subset of another
- position -- the first element of a list satisfying a condition
- positions -- which elements of a list satisfy a condition
- min -- get the minimum element in a list or sequence
- minPosition -- position of the smallest element
- max -- get the maximum element in a list or sequence
- maxPosition -- position of the largest element
- number -- count how many elements of a list satisfy a condition
- partition -- partition a set or list by values of a function
- sublists -- process interspersed subsequences of a visible list

#### Nested lists

- table -- make a table from a binary function
- isTable -- whether something is a list of lists of equal length
- subtable -- extract a subtable from a table
- applyTable -- apply a function to each element of a table
- List ** List -- Cartesian product of two lists
- List .. List -- rectangular sequences of consecutive lists and sequences
- List ..< List -- rectangular sequences of consecutive lists and sequences
- pack -- pack elements of a list or string into several shorter lists or strings
- netList -- a table of boxes

#### Sorting lists

- sort -- sort a list or columns of a matrix
- rsort -- sort a list or matrix in reverse order
- isSorted -- whether a list is sorted

#### Manipulating lists

- List + List -- sum of two vectors
- List - List -- difference of two vectors
- List | List -- join lists, sequences or arrays
- join -- join lists, sequences, and iterable objects
- append -- add an element to the end of a list
- prepend -- add an element to the beginning of a list
- rotate -- rotate a list
- insert -- copy a list, inserting an element
- replace -- replacement in strings and lists
- between -- insert something between elements of a list
- delete -- delete some elements of a list
- sum -- compute the sum
- product
- toList -- create a list
- toSequence -- convert to sequence
- flatten -- flatten a nested list or a matrix
- splice -- remove subsequences from a sequence or list
- deepSplice -- remove all levels of subsequences from a sequence or list
- mingle -- mingle elements of several lists
- mergePairs -- merge sorted lists of pairs
- reverse -- reverse a list, sequence, or string
- sequence -- make a sequence
- unsequence -- extract the single element from a sequence of length 1
- switch -- copy a list, switching two elements
- tally -- tally the elements of a list, sequence, array, or string
- commonest -- the most common elements of a list or tally
- unique -- eliminate duplicates from a list
- runLengthEncode -- run length encoding
- uniquePermutations -- produce all unique permutations of a list
- permutations -- produce all permutations of a list
- subsets -- produce the subsets of a set or list

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Macaulay2Doc/ov_lists.m2:535:0.