Lists

from Essential Mathematica for Students of Science
© James J. Kelly, 1998
Last revised: January, 2004

Initialization

ClearAll["Global`*"];
Off[General::spell,  General::spell1]

Introduction

Types of lists

Lists are the fundamental data structure in Mathematica.  Lists can represent sets, vectors, matrices, tensors, or storage objects containing data of mixed type.  The elements of a list can be numerical, symbolic, graphical, other lists, or objects of any other type recognized by Mathematica.  Several different types of data can be stored in the same list.  In this notebook we introduce functions that create and manipulate lists and some programming techniques that exploit the properties of lists.

A List is an ordered set of objects separated by commas and enclosed in curly brackets.  There are no restrictions on the contents or structure of lists.  There are several functions which report the structure of lists.

Length[list] returns the number of elements in the first level of a list, where any sublists are counted just once like any other element would be counted.

Dimensions[list] reports the structure of a list.  If the structure is uniform, a list of lengths is returned for each sublist, but if the structure is irregular the report stops at the deepest regular level.

TensorRank[expr] returns the tensor rank of an expression, which is interpreted as the depth to which an expression is represented by sublists of the same length.

Vectors, matrices, tensors

The simplest types of lists are vectors, matrices, and tensors.  A vector is a simple list of one or more objects.  A matrix is a list of vectors of the same length.  A tensor is a list of matrices with the same dimensionality.  Note that a matrix is a special case of a tensor of rank 2, a vector is a tensor of rank 1, and a scalar is tensor of rank 0.

aVector  =  {x, y, z};
aMatrix  =  {{a, b, c, d}, {e, f, g, h} };
aTensor  = {{{a, b, c},  {d, e, f}},  {{g, h, i}, {j, k, 
              l}} };

Length  /@  {aVector,  aMatrix,  aTensor}

Dimensions  /@  {aVector,  aMatrix,  aTensor}

TensorRank  /@  {a, aVector, aMatrix,  aTensor}

VectorQ[expr] returns True if expr has the structure of a vector, and False otherwise.  Similarly, MatrixQ[expr] returns True if expr has the structure of a matrix.

VectorQ  /@  {aVector, aMatrix,  aTensor}

MatrixQ  /@  {aVector, aMatrix,  aTensor}

A vector can be printed in ColumnForm or in MatrixForm, but you will need to write your own display function for more general tensors.

ColumnForm[aVector]

MatrixForm[aVector]

MatrixForm[aMatrix]

Generic arrays can be created using Array[name,dimensions] where name is the label applied to each element and dimensions is a list of dimensions for the array.

Array[ψ, {3}]

Array[ζ, {4, 3}]  // MatrixForm

Define a replacement rule which can be used to print matrix elements in subscripted form, viz. (Subscript[ζ, i, j]).

General lists

Lists need not have a uniform structure — the sublists may vary in length and the types of contents.

\(\(references\  = \ {{{"Author", "J.J. Kelly"}, {"Title", "Essential Mathematica for Students of Science"}, \ {"Date", 
              1998}}, \ {{"Author", \ "S. Wolfram"}, \ {"Title", \ "The Mathematica Book"}, \ {\ "Publisher", \ {"Wolfram Media", "Cambridge University Press"}}, \ \ {"Date", 
              1996}}, \ \ {{"Author", \ "P.T. Tam"}, \ {"Title", \ "A Physicist's Guide to Mathematica"}, \ {"Publisher", \ "Academic Press"}, \ \ {"Date", 1997}}\ };\)\)

Length[references]

Dimensions[references]

TensorRank[references]

TableForm[references[[2]], 
      TableAlignments -> {Left, Top}]

Manipulating lists

Adding, removing, or moving elements

Append[list,element] adds an element to the end of a list while Prepend[list,element] inserts an element at the beginning.

Append[{a, b, c, d}, e]

Prepend[{a, b, c, d}, e]

Note that if the element to be inserted is itself a list, its list structure is retained.

Append[{a, b, c, d}, {e, f}]

Insert[list,element,position] inserts a new element into a specified position of a list.  Negative positions count from the end.

Insert[{a, b, c, d}, ξ, 3]

ReplacePart[list,element,n] replaces the element at position n with new element.

ReplacePart[{a, b, c, d}, ξ, 3]

Join[list1,list2,⋯] combines two or more lists into a single list.  Note that to include a scalar, it must be given in the form a list containing a single element.

Join[{a, b, c}, {d, e, f, g}, {h}]

Union[list1,list2,⋯] combines two or more lists into a single list, eliminating duplicates.  If only one argument is given, duplicated elements in it are dropped.

Union[{a, b, c, d}, {b, c, d}, {e, f}, {g}, {a}]

Union[{a, b, a, b, c}]

Reverse[list] reverses the order of a list.

Reverse[{a, b, c, d}]

RotateLeft[list,n] rotates n elements toward the left, while RotateRight[list,n] rotates toward the right where the list is visualized as written upon a circular band.  If n is omitted, it is assumed to be 1.

RotateLeft[{a, b, c, d, e}]

RotateLeft[{a, b, c, d, e}, 2]

RotateRight[{a, b, c, d, e}]

RotateRight[{a, b, c, d, e}, 2]

It is usually more efficient to employ list operations to perform numerical or symbolic calculations by treating lists as entire objects rather than breaking them apart and putting them back together again like one might with loop calculations in Fortran or C.  For example, if one has an array of equally-spaced function values (Subscript[f, i]) = f[(Subscript[x, i])] at (Subscript[x, i]) = (Subscript[x, 0]) + i h for {i, 1, n}, the second derivative at these points can be approximated by the central-difference formula
	(Subscript[f, i]^″) ≈ ((Subscript[f, i - 1]) - 
              2  (Subscript[f, i]) + (Subscript[f, i + 1]))/(h^2)
where h is the step size.  The array of second derivatives can be constructed using RotateLeft and RotateRight without having to access list elements directly, as follows.

SecondDerivative[f_List, 
        h_] := (RotateRight[f] - 2  f + RotateLeft[f])/(h^2)

SecondDerivative[Array[f, 10], h]

This method works well in the interior of the array, but the end points are more subtle because the basic algorithm can be extended past the edges of the input array without making model-dependent assumptions about the behavior of the function at the boundaries.  Our implementation implicitly assumes periodic boundary conditions, namely (Subscript[f, 0]) = (Subscript[f, n + 1]).

Selecting elements by position

First[list] returns the first element, Rest[list] returns everything but the first element, and Last[list] returns the last element of a list.

First[{a, b, c, d}]

First[{{a, b}, {c, d}, {e, f}}]

Rest[{a, b, c, d}]

Last[{a, b, c, d}]

Take[list,n] takes whereas Drop[list,n] removes the first n elements of a list.  Similarly, Take[list,{n,m}] and Drop[list,{n,m}] take or drop elements n through m.  Negative indices count from the end.

Take[{a, b, c, d, e, f}, 3]

Take[{a, b, c, d, e, f}, -3]

Take[{a, b, c, d, e, f}, {3, 5}]

Take[{a, b, c, d, e, f}, {-5, -3}]

Drop[{a, b, c, d, e, f}, 3]

Drop[{a, b, c, d, e, f}, -3]

Drop[{a, b, c, d, e, f}, {3, 5}]

Drop[{a, b, c, d, e, f}, {-5, -3}]

Selecting elements by value

Elements satisfying some criterion can be selected using Select[list,criterion] where criterion is a logical function acting on the elements of the list one at a time.  The result is a list elements for which the criterion function tests True, with ambiguous cases omitted.

Select[{1, q, 2, 3, -3, "Oscar"},  OddQ]

Select[{1, q, 2, 3, -3, "Oscar"},  # > 2 &]

Select[{1, q, 2, 3, -3, "Oscar"},  StringQ]

Select[{1, q, 2, 3, -3, "Oscar", "abc"},  
      StringQ[#]  &&  StringLength[#] > 4 &]

A list of elements matching a pattern is produced using Cases[list,pattern].

Cases[{1, q, 2, 3, -3, "Oscar"},  x_?OddQ]

\(Cases[{1, q\^2, 2, 3, \(-3\), "Oscar"}, \ x_\^n_]\)

DeleteCases[list,pattern] removes elements matching a pattern.

DeleteCases[{1, (q^2), 2, 3, -3, "Oscar"},  
      x_?StringQ]

Produce a list of 100 random integers and select those that are even using all three of these functions (Select, Cases, DeleteCases).  How many are prime?

Sorting

The elements of a list can be sorted according to an ordering function that acts pairwise in the list until satisfied by all successive pairs using the function Sort[list,criterion].  If the ordering function is omitted, the internal "canonical" ordering function is applied.

Sort[{3, -1, 4, 99, -27, 0, 2, 2}, #2 > #1 &]

However, sorting stops if ambiguous results are obtained, resulting in partial but incomplete ordering.

Sort[{3, -1, 4, 99, a, -27, 0, 2, 2}, #2 > #1 &]

Sort a list of 10 random integers in decreasing order.

Restructuring

Sometimes it is necessary to regroup the elements of a list into another list with a different structure.  A list containing sublists can be visualized as an inverted tree using TreeForm.

TreeForm[aTensor]

The structure of a list can be "flattened" to a single level using Flatten.

Flatten[aTensor]

TreeForm[%]

Partial flattening to level n is obtained using Flatten[list,n].

Flatten[aTensor, 1]

TreeForm[%]

FlattenAt[list,position] flattens a sublist at a specified position of list.  The position can be a sequence list or a list of sequence lists.

FlattenAt[{a, {b, c, d}, e,  f,  {g, h}}, 2]

The elements of a flattened list can be regrouped into sublists with n elements each using Partition[list,n].  Note that any elements left over which do not comprise a complete sublist are dropped.

Flatten[aTensor]  // Partition[#, 5] &

Flatten[aTensor]  // Partition[#, 2] &

Nest[Partition[#, 2] &, Flatten[aTensor], 2]

If Partition[list,n,d] is supplied another argument, an offset d is used each time a sublist is created.  The offset gives the difference in position between the first elements of successive sublists.  Thus, if the offset is d, the first sublist begins at position 1, the second at position 1 + d, the third at position 1 + 2  d, etc.

Partition[{a, b, c, d, e, f, g, h, i, j}, 3, 1]

Partition[{a, b, c, d, e, f, g, h, i, j}, 3, 2]

Create a list of integers between 1 and 100.  Divide that list into two equal sublists and reverse the order of the second sublist.  Then add corresponding elements of those lists.

Example: extracting specified records from a database

Suppose that we wish to construct a list of authors from the data contained in the list of references.  The irregular structure of this list complicates that task.  Here we develop one of several possible solutions to this problem.  Each reference contains a list of data entries pertaining to some publication, where each entry consists of an identification label and either a single datum or a list of data.  If we just want the data with a particular label, it is useful to flatten the list enough to remove the grouping by publication while preserving the grouping of data by category.

Flatten[references, 2]

Next, we group the label and data entries back together using partition.

Partition[Flatten[references, 2], 2]

Next, we use Select with a skeletal function to isolate the author information

\(Select[
      Partition[Flatten[references, 2], 
        2], #1[[1]] == "Author" &]\)

Finally, we strip off the redundant label to produce just an author list.  Note that multiple authors of a single publication remain grouped together.

\(\(#1[[2]] &\)\  /@ 
      Select[Partition[Flatten[references, 2], 
          2], #1[[1]] == "Author" &]\)

It is now an easy matter to generalize this function to extract a list of records of a particular type from a database with this format.

listRecords[database_, 
        record_]  :=  #1[[2]] &  /@ 
        Select[Partition[Flatten[database, 2], 
            2], #1[[1]] == 
              record &]

listRecords[references, "Author"]

listRecords[references, "Title"]

Write a function which selects the works published before a specified date.

Operations on lists

Listable functions

Many Mathematica functions are Listable, meaning that they can be applied to lists as well as to scalar arguments.  A listable function is applied separately to the elements of any lists which appear in its arguments, provided that the dimensions of those lists are compatible.  For example, a binary function like Plus can receive either a list and a scalar or two lists of the same length.

{a, b, c, d}  + 1

{a, b, c, d} + {1, 2, 3, 4}

{a, b, c, d} {e, f, g, h}

{a, b, c, d}^2

\({a, b, c, d}\^{1, 2, 3, 4}\)

Suppose that two lists contain several sublists of arbitrary structure, but that we want the sum of all elements wherever they are found; how is that done?  Test your method by adding the two lists { {a,b,{c,d}}, 3, 9, {{-f,8}} } and {g,j,{k},{-2,{4.q}}}.

Scalar and vector products

The ordinary scalar product of two vectors is defined by a . b  =  ∑(Subscript[a, i]) (Subscript[b, i]) and is produced by Dot[a,b].  More generally, Dot[a,b] contracts the last index of a with the first index of b and can be applied to various combinations of vectors, matrices, or tensors with compatible dimensions.  The operator form of Dot[a,b] is a.b.

{a, b, c, d} . {e, f, g, h}

{{a, b, c}, {e, f, g}} . {x, y, z}

{x, y} . {{a, b, c}, {e, f, g}}

Inner[f,a,b,g] is generalized inner product between tensors a and b in which the function f plays the role of multiplication while g plays the role of addition.

Clear[f, g, a, b, c, d];
Inner[f, {{a, b}, {c, d}},  {x, y},  g]

Inner[Times, {{a, b}, {c, d}},  {x, y},  Plus]

The vector product or cross product in three dimensions is given by Cross[a,b] or a×b.  Beware: the operator for the cross product is EsccrossEsc or ×, which looks very similar to Esc*Esc or × but is not the same!

Cross[{a, b, c}, {d, e, f}]

More generally, Cross[ (Subscript[v, 1]), (Subscript[v, 2]), ⋯ (Subscript[v, n - 1]) ] produces an totally antisymmetric vector in n dimensions that is orthogonal to each input vector { (Subscript[v, 1]), (Subscript[v, 2]), ⋯ (Subscript[v, n - 1])}.

Cross[{a1, a2, a3, a4}, {b1, b2, b3, b4}, {c1, c2, c3, c4}]

Example: selected vector identities

Here we create four generic vectors in 3-space and test a few identities which are somewhat tedious to evaluate by hand.

Clear[a, b, c, d];
a = Array[aa, 3];  b = Array[bb, 3]; c = Array[cc, 3];  
    d = Array[dd, 3];

(a\[Cross]b) . (c\[Cross]d) == 
        a . (b\[Cross](c\[Cross]d))  // Simplify

(a\[Cross]b) . (c\[Cross]
              d) == (a . c) (b . d)  -  (a . d) (b . c) // 
      Simplify

(a\[Cross]b)\[Cross](c\[Cross]d) == ((a\[Cross]b) . d) 
            c  -  ((a\[Cross]b) . c) d  // Simplify

Outer product

An outer product or tensor product is defined as the set of all possible products of the elements of two tensors, which then forms a tensor of rank equal to the product of the ranks its factors.  Mathematica provides a generalized outer product Outer[f,list1,list2,⋯] in which the function f is applied to all possible selections of elements from the top level of each list supplied.  If f has two slots then two lists are needed, three lists for three slots, etc.

Clear[a, b, f]

at  =  Array[a,  {2, 2}];  bt  =  Array[b, {3, 3}];

ct = Outer[f, at, bt]

Dimensions[ct]

TensorRank[ct]

Example: expansion in terms of orthogonal functions

We can construct a matrix which represents monomials of the form (x^n) in terms of Legendre polynomials (Subscript[P, m])[x] by applying the orthogonality relationship

(∫_(-1)^1) (Subscript[P, n])[x] 
          (Subscript[P, m])[x] \[DifferentialD]x = (2/(2  n + 
              1)) (Subscript[δ, n, m])

to the series representation

(x^n) = (∑_(m = 0)^n) (Subscript[a, n, m]) (Subscript[P, m])[x]

to deduce the expansion coefficients

(Subscript[a, n, m]) = 
      ((2  m + 1)/2) 
        (∫_(-1)^1) (x^n) (Subscript[P, m])[x] \[DifferentialD]x

The coefficient matrix can now be constructed using Outer to form the integrals.

Pm  =  
        Table[((2  m + 1)/2) LegendreP[m,  x], {m, 0, 6}];
xn = Table[(x^n), {n, 0, 6}];
coefficientMatrix  = 
        Outer[Integrate[#1 #2, {x, -1, 1}] &, xn, Pm];
coefficientMatrix  // MatrixForm

We check our work by reconstructing the monomials.

coefficientMatrix  .  LegendreP[Range[0, 6], x] // 
      Simplify

Suppose that eqs is a list of linear equations and that vars is a list of the independent variables.  Write a function that returns a matrix A and a vector rhs such that the system of of linear equations is expressed in the form A.vars==rhs.  [Hints: replace Equal by Subtract to transform eqs to a list of polynomials.  Then use Outer with Coefficient to produce the coefficient matrix A.]

Applying functions to a list

Map[f,expr] or f /@ expr applies f to each element at the first level of an expression.

Clear["Global`*"]

aVector  =  {x, y, z};
aMatrix  =  {{a, b, c, d}, {e, f, g, h} };
aTensor  = {{{a, b, c},  {d, e, f}},  {{g, h, i}, {j, k, 
              l}} };

f /@ aVector

f /@ aMatrix

Map[Sin[((#1  π)/4)] &,  Range[10]]

Apply[f,expr] or f@@expr replaces the head of expr with f.  Thus, if expr is a list and f a function, the result if a function with a list of arguments.  For example, we can calculate the sum of 1/(n^2) over a range of n by first forming a list of n using Range, obtaining a list of 1/(n^2) by applying listable functions to the entire list rather than to its elements, and then using Apply to form the sum (replacing List by Plus).

Apply[ Plus,  1/Range[10]^2 ] // N

The result is within about 10% of the infinite sum.

Sum[(n^(-2)), {n, 1, ∞}]

% // N

The convergence is easily examined using FoldList to produce a list of partial sums and ListPlot to display that list.  Evidently, the convergence is fairly slow.

ListPlot[
        Evaluate[FoldList[ Plus, 0,  1/Range[30]^2 ]]];

Example: Fourier series for a sawtooth signal

The following example is based upon one by MacDonald.

An odd periodic function, for which f[-x] == -f[x] and f[x + b] == f[x], can be represented as a Fourier-Sine series \(TraditionalForm
      \`f[x]\  = \ 
        ∑\+\(n = 1\)\%∞\( a\_n\) Sin[2  π\ n\ x\/b]\) where the coefficients are given by \(TraditionalForm
      \`a\_n = \(2\/b\) 
          \(∫\_0\%b f[x]\ Sin[2  π\ n\ x\/b]\ 
              dx\)\).  A sawtooth function which varies between +1 and -1 in a unit interval can then be represented by Fourier-Sine coefficients of the following form.

2 (∫_0^1)(1 - 2  x) 
            Sin[2  π n x] \[DifferentialD]x  // 
      FullSimplify

These coefficients reduce to just (2/(n π)) because n is an integer.  The convergence of the Fourier-Sine series can be displayed using the following function based upon list programming.  The finite series is represented as a scalar product between two lists produced by applying the listable functions Sin[2  π m x] and ((2/(m π))) to Range[n].

Clear[f, x, n, m];
f[x_, n_]  :=  
      Sin[2  π m x] . ((2/(m π)))  /. 
        m -> Range[n]

Plot[{f[x, 5], 1 - 2  x + 2  Floor[x]}, {x, 0, 2}, 
        PlotPoints -> 100];

Note that it is necessary to increase the number of points plotted in order to fully appreciate the periodic nature of the ripples that are superimposed upon the sawtooth.  We clearly see that the error in a finite Fourier series is dominated by the first omitted term, which impresses its periodicity upon the final result.

Often it is faster to employ functional programming techniques based upon lists than to use traditional procedural programming techniques based upon iteration.  To illustrate this we compare the times needed to sum the Fourier series using a scalar product of lists with the time needed using a direct summation of terms in a Do loop.

time[Dot, x_, 
        nmax_] := Timing[f[x, 
              nmax];][[1]]

time[Do, x_, 
        nmax_] := Timing[sum = 0; 
          Do[sum = sum +  Sin[2  π m x] ((2/(m π))) , {m, 
              1, nmax}];][[1]]

ratio[x_, nmax_]  :=  
      time[Do, x, nmax]/time[Dot, x, nmax]

ratio[0.2, 1000]

ratio[x, 1000]

Thus, we find that for numerical calculations the list method is more than twice as fast as direct summation while for symbolic calculations the ratio increases to almost 20.  (Your results may differ somewhat because of processor dependence, but should be similar.)  Functional programming based upon lists offers some of the advantages of parallel processing where operations are applied to entire lists in parallel rather than to individual elements in series.

\(TraditionalForm\`∂\^2 f[x, y]\/∂x\^2 ≈ \((f[x - h\_x, y] - 2  f[x, y] + f[x + h\_x, y])\)/
        h\_x\^2\)

(∂^2) f[x, y]/∂(y^2) ≈ (f[x, 
              y - (Subscript[h, y])] - 2  f[x, y] + f[x, y + (Subscript[h, y])])/
        ((Subscript[h, y])^2)