Contents Previous Next Index

4 Basic Data Structures


The appropriate use of data structures is an important part of writing efficient programs. Maple provides various data structures that can be used to help make your programs efficient.

4.1 In This Chapter


•

Defining and manipulating sets, lists, tables, Arrays, records, stacks, and queues

•

Converting between data structures

•

Mathematical versus programmer indexing for Arrays

•

Performance comparisons of data structures



4.2 Introduction


Maple provides various data structures that you can use for programming and interacting with Maple functions. This chapter focuses on the use of data structures in programming. However, the sections Lists and Sets may be useful for users who want to construct arguments for Maple functions.
Maple has many data structures that provide similar functionality, but certain data structures are better suited for certain types of operations. Therefore, when choosing which data structures to use, it is important to select a structure that performs well on the operations used in your code.
Many aspects affect the performance of data structures. However, in Maple, the provided data structures can be divided into two basic classes: mutable and immutable. The mutable data structures can be modified, that is, the values they store can change. The immutable data structures cannot be changed after they are created. Instead, copies of these structures can be made with different contents. This difference in behavior can have significant impact on the performance of code that uses these structures.


4.3 Immutable Data Structures


Immutable data structures can be useful when storing a fixed collection of elements. Also, because immutable structures are more compact than mutable data structures, especially when storing a small number of elements, they are more memory efficient.
Immutable structures are created with their contents fixed. This means that they cannot be modified inplace. When you change an immutable data structure, a new copy is created with the modified contents and stored as a distinct object in memory. Thus, immutable structures may not be the correct choice if you want to modify the contents of a structure.
In Maple, there are two basic immutable data structures: lists and sets.

Lists


A list stores an ordered sequence of expressions. The ordering of the elements in a list is fixed when the list is created. Lists, in contrast to sets, will maintain duplicate elements.

Creating Lists


The easiest way to create a list is to enclose a sequence of expressions in square brackets ([]). A sequence of expressions is a series of commaseparated expressions.
This creates a list that contains the elements of sequence in the specified order. In the case where sequence is empty, [] represents an empty list. Compare the results of these examples to those in the Sets section.
$\left[{x}{\,}{y}{\,}{y}\right]$
 (1) 
$\left[{a}{\,}{1}{\,}{b}{\,}{2}\right]$
 (2) 
$\left[{{y}}_{{1}}{\,}{x}{\,}{{x}}_{{1}}{\,}{{y}}_{{1}}\right]$
 (3) 
The elements of a list can be any expressions, even other lists.
>

L := [[1], [2, a], [X, Y, Z]];

${L}{\u2254}\left[\left[{1}\right]{\,}\left[{2}{\,}{a}\right]{\,}\left[{X}{\,}{Y}{\,}{Z}\right]\right]$
 (4) 
In Maple, nested lists whose inner lists have the same number of elements have a special name, listlist.
>

M := [[a,b], [1,2], [3, 4]];

${M}{\u2254}\left[\left[{a}{\,}{b}\right]{\,}\left[{1}{\,}{2}\right]{\,}\left[{3}{\,}{4}\right]\right]$
 (5) 
Many Maple functions return sequences. Thus, enclosing a call to one of those functions in square brackets [] creates a list. For example, the seq command generates sequences.
$\left[{x}{\,}{{x}}^{{2}}{\,}{{x}}^{{3}}\right]$
 (9) 
The op command can be used to extract the sequence of elements in a list.
${L}{\u2254}\left[{1}{\,}{2}{\,}{3}\right]$
 (10) 
Thus op can be used to create new lists based on existing lists. For example, you can create a new list with an additional element added to the start of the list.
${\mathrm{L2}}{\u2254}\left[{0}{\,}{1}{\,}{2}{\,}{3}\right]$
 (12) 
A list with another element added to the end of the list can be created in a similar way.
${\mathrm{L3}}{\u2254}\left[{0}{\,}{1}{\,}{2}{\,}{3}{\,}{4}\right]$
 (13) 
Multiple lists can also be combined into a single list.
>

L4 := [ op(L), op(L2), op(L3) ];

${\mathrm{L4}}{\u2254}\left[{1}{\,}{2}{\,}{3}{\,}{0}{\,}{1}{\,}{2}{\,}{3}{\,}{0}{\,}{1}{\,}{2}{\,}{3}{\,}{4}\right]$
 (14) 


Accessing Data Stored in a List


The selection operation, [], can be used to read an element from a list.
${L}{\u2254}\left[{1}{\,}{2}{\,}{3}\right]$
 (15) 
You can also specify a range in the selection operation to extract a sublist containing the elements that are indexed by that range.
>

L := [ seq( i^2, i=1..10 ) ];

${L}{\u2254}\left[{1}{\,}{4}{\,}{9}{\,}{16}{\,}{25}{\,}{36}{\,}{49}{\,}{64}{\,}{81}{\,}{100}\right]$
 (19) 
$\left[{9}{\,}{16}{\,}{25}{\,}{36}\right]$
 (20) 
$\left[{25}{\,}{36}{\,}{49}{\,}{64}\right]$
 (21) 
While it is possible to make an assignment to a list index, this operation can be inefficient since it creates a new list. In fact, assignment to a large list is not permitted in Maple and will produce an error. Assigning a list element is a common error, so if you find yourself wanting to do this, consider using a mutable data structure instead. For more information, see Mutable Data Structures.
${L}{\u2254}\left[{3}{\,}{2}{\,}{3}\right]$
 (22) 
$\left[{3}{\,}{2}{\,}{3}\right]$
 (23) 
L is now a new list with a different element at index 1. Thus, assigning to a single element of a list causes the entire list to be copied in the same way as using the subsop command. In fact, the previous example is equivalent to the following except in how the result is displayed.
${L}{\u2254}\left[{3}{\,}{2}{\,}{3}\right]$
 (24) 
If you attempt to assign to an index to a large list, an error will occur. Therefore, if you need to make a copy of a list with one changed element, it is recommended that you use the subsop command instead.
>

LL := [ seq( i, i=1..200 ) ]:

 (25) 


Determining If an Element Is in a List


To test if an expression is contained in a list, use the member function.
>

member( 1, [ 1,2,3 ] );

>

member( 1, [ 2,3,4 ] );

You can also use the in operator.


Getting the Number of Elements in a List


To find the length of a list, use the numelems command.
>

numelems( [ 1,2,3,4,5 ] );

>

numelems( [ seq( i, i=1..127 ) ] );

This can be useful for many tasks, for example, using lists in a loop. For more information on selectremove, see Filtering Data Structure Elements.
>

L := [seq( i, i=2..100)]:

>

while ( numelems( L ) > 0 )
do
divisible, L := selectremove( i>(i mod divisor = 0), L ):
n := numelems( divisible );
if ( n > 0 ) then
printf( "%d integer%s whose smallest prime divisor is %d\n",
n, `if`( n > 1, "s", "" ), divisor ):
end if;
divisor := nextprime( divisor );
end do:

50 integers whose smallest prime divisor is 2
17 integers whose smallest prime divisor is 3
7 integers whose smallest prime divisor is 5
4 integers whose smallest prime divisor is 7
1 integer whose smallest prime divisor is 11
1 integer whose smallest prime divisor is 13
1 integer whose smallest prime divisor is 17
1 integer whose smallest prime divisor is 19
1 integer whose smallest prime divisor is 23
1 integer whose smallest prime divisor is 29
1 integer whose smallest prime divisor is 31
1 integer whose smallest prime divisor is 37
1 integer whose smallest prime divisor is 41
1 integer whose smallest prime divisor is 43
1 integer whose smallest prime divisor is 47
1 integer whose smallest prime divisor is 53
1 integer whose smallest prime divisor is 59
1 integer whose smallest prime divisor is 61
1 integer whose smallest prime divisor is 67
1 integer whose smallest prime divisor is 71
1 integer whose smallest prime divisor is 73
1 integer whose smallest prime divisor is 79
1 integer whose smallest prime divisor is 83
1 integer whose smallest prime divisor is 89
1 integer whose smallest prime divisor is 97
 


Sorting a List


The sort command can create a new list with sorted elements from any given list. By default, sort arranges elements in ascending order.
$\left[{2}{\,}{3}{\,}{4}\right]$
 (33) 
The sort command can also accept a second argument that specifies the ordering to use when sorting the elements.
$\left[{4}{\,}{3}{\,}{2}\right]$
 (34) 


Applying a Function to the Contents of a List


It is often useful to be able to apply a function to all the elements of a list. The map command performs this operation in Maple.
>

L := [ seq( Pi*i/4, i=0..3 ) ]:

$\left[{0}{\,}\frac{\sqrt{{2}}}{{2}}{\,}{1}{\,}\frac{\sqrt{{2}}}{{2}}\right]$
 (35) 
$\left[{1}{\,}\frac{\sqrt{{2}}}{{2}}{\,}{0}{\,}{}\frac{\sqrt{{2}}}{{2}}\right]$
 (36) 
Maple provides other operations that can work with the members of a list, such as add and mul.
>

add( i, i in [ seq( j, j=1..100 ) ] );

>

mul( i^2, i in [ 1,2,3,4,5,6,7,8,9,10 ] );

Finally, a for loop can be combined with the in operator to loop over the contents of a list.
>

for i in [1,2,3,4]
do
print( i^2 );
end do;




Sets


A set is an unordered sequence of unique expressions. When a set is created, Maple reorders the expressions to remove duplicate values and to make certain operations faster.

Creating Sets


The easiest way to create a set is to enclose a sequence of expressions in braces ({}).
When Maple creates the set, it performs automatic simplification. This process creates a set that contains the elements of sequence; however, during the automatic simplification process, any duplicate elements are removed and the remaining elements are reordered.
Compare the results of these examples to those in the Lists section.
$\left\{{x}{\,}{y}\right\}$
 (40) 
$\left\{{1}{\,}{2}{\,}{a}{\,}{b}\right\}$
 (41) 
$\left\{{x}{\,}{{x}}_{{1}}{\,}{{y}}_{{1}}\right\}$
 (42) 
Similar to lists, sets can be created using functions such as seq that return sequences.
>

{ seq( i mod 3, i=1..10 ) };

$\left\{{0}{\,}{1}{\,}{2}\right\}$
 (43) 
Again, similar to lists, the op command can be used to extract the sequence of elements in a set.
${S}{\u2254}\left\{{1}{\,}{2}{\,}{3}\right\}$
 (44) 
However, unlike lists, Maple provides operations for set arithmetic, so for sets op is somewhat less important.


Set Arithmetic


Maple provides operators for mathematical set manipulations: union, minus, intersect, and subset. These operators allow you to perform set arithmetic in Maple.
${s}{\u2254}\left\{{x}{\,}{y}{\,}{z}\right\}$
 (46) 
${t}{\u2254}\left\{{w}{\,}{y}{\,}{z}\right\}$
 (47) 
$\left\{{w}{\,}{x}{\,}{y}{\,}{z}\right\}$
 (48) 
$\left\{{x}\right\}$
 (49) 
$\left\{{y}{\,}{z}\right\}$
 (50) 


Accessing Data Stored in a Set


The selection operation, [], can be used to read an element from a set. However, unlike lists, the order in which the elements are specified when creating the set may not correspond to the order they are accessed by indexing.
Unlike lists, you cannot use the selection operation to create new sets.
You can specify a range in the selection operation to extract the elements indexed by the range.
>

S2 := { seq( i^2, i=1..10 ) };

${\mathrm{S2}}{\u2254}\left\{{1}{\,}{4}{\,}{9}{\,}{16}{\,}{25}{\,}{36}{\,}{49}{\,}{64}{\,}{81}{\,}{100}\right\}$
 (56) 
$\left\{{9}{\,}{16}{\,}{25}{\,}{36}\right\}$
 (57) 
$\left\{{25}{\,}{36}{\,}{49}{\,}{64}\right\}$
 (58) 


Determining If an Element Is in a Set


To test if an element is contained in a set, use the member function.
You can also use the in operator.


Getting the Number of Elements in a Set


To find the number of elements in a set, use the numelems command.
>

numelems( {1,2,3,4,5} );

>

numelems( {seq( i, i=1..127 )} );

In this example, the features of sets are used to test Collatz's conjecture on the first million integers. Collatz's conjecture states that given any integer, i, if the following function is applied repeatedly, the result will eventually be 1.
>

collatz := proc( i )
if ( i = 1 ) then
1;
elif ( type( i, even ) ) then
i/2;
else
3*i+1;
end if;
end proc:

Begin with a set S that consists of the integers from 1 to 1 million. Under repeated application of collatz, as numbers converge to 1, the set automatically removes duplicate values, until eventually there is only 1 element left. For more information on the use of map, see Applying a Function to the Contents of a Set.
>

S := {seq( i, i=1..1000000)}:

>

while ( numelems( S ) > 1 )
do
S := map( collatz, S ):
end do:

$\left\{{1}\right\}$
 (66) 


Applying a Function to the Contents of a Set


As with lists, it can be useful to apply a function to all of the elements of a set. The map command works on sets, as it does with lists.
>

S := { seq( Pi*i/4, i=0..3 ) }:

$\left\{{0}{\,}{1}{\,}\frac{\sqrt{{2}}}{{2}}\right\}$
 (67) 
$\left\{{0}{\,}{1}{\,}{}\frac{\sqrt{{2}}}{{2}}{\,}\frac{\sqrt{{2}}}{{2}}\right\}$
 (68) 
Notice that when applying a function to a set, the output is also a set, which means the elements are reordered and duplicate elements are removed.
Maple provides other operations that can work with the members of a list, such as add and mul.
>

add( i, i in { seq( j, j=1..100 ) } );

>

mul( i^2, i in { 1,2,3,4,5,6,7,8,9,10 } );

Finally a for loop can be combined with the in operator to loop over the contents of a set. Note that the set has been reordered.
>

for i in {1,4,3,2}
do
print( i^2 );
end do;





4.4 Mutable Data Structures


Mutable data structures are structures whose contents can be changed.
The most flexible mutable data structure provided by Maple is the table.

Tables


A table stores a collection of index/entry pairs. For a given index, the table contains a particular value, called an entry. Index/entry pairs can be created or removed, or the value associated with an index can be modified.

Creating Tables


A new table can be created by calling the table function.
${t}{\u2254}{table}{}\left(\left[\right]\right)$
 (72) 
With no arguments, table creates a new empty table. To create a table that contains certain index/entry pairs, specify the pairs as a list of equations. The lefthand side of an equation is the index and the righthand side is the entry.
>

t := table( [ 1=2, a=b, f(x)=y ] );

${t}{\u2254}{table}{}\left(\left[{1}{=}{2}{\,}{f}{}\left({x}\right){=}{y}{\,}{a}{=}{b}\right]\right)$
 (73) 
If the given list contains one or more expressions that are not equations, the list is treated as a list of entries and the indices are the positions of the entries in the list (1, 2, 3, ...).
>

t := table( [ a, b, c=d ] );

${t}{\u2254}{table}{}\left(\left[{1}{=}{a}{\,}{2}{=}{b}{\,}{3}{=}\left({c}{=}{d}\right)\right]\right)$
 (74) 
Note that c=d is treated as a entry and not an index/entry pair.
Tables are also created implicitly when you assign to an indexed name.
${{\mathrm{t2}}}_{{\mathrm{new}}}{\u2254}{10}$
 (75) 
${table}{}\left(\left[{\mathrm{new}}{=}{10}\right]\right)$
 (76) 


Accessing Stored Values


Table indexing is performed using the selection operation, []. To extract data from a table, specify an index in square brackets. The corresponding entry is returned.
>

t := table( [1=2,a=b,f(x)=y] );

${t}{\u2254}{table}{}\left(\left[{1}{=}{2}{\,}{f}{}\left({x}\right){=}{y}{\,}{a}{=}{b}\right]\right)$
 (77) 
If the table does not contain a entry associated with the index, an unevaluated table reference is returned.
The selection operation can also be used to add new index/entry pairs to the table.
${{t}}_{{2}}{\u2254}{3}$
 (82) 
${{t}}_{{c}}{\u2254}{d}$
 (83) 
${{t}}_{{\mathrm{sin}}{}\left({x}\right)}{\u2254}{1}$
 (84) 


Removing an Element


The best way to remove an element from a table is to call the unassign function.
${{t}}_{{1}}{\u2254}{x}$
 (88) 
${{t}}_{{\mathrm{sin}}{}\left({x}\right)}{\u2254}{y}$
 (89) 
>

unassign( 't[sin(x)]' );

${{t}}_{{\mathrm{sin}}{}\left({x}\right)}$
 (91) 
The selection operation can also be used to remove an index/entry pair from a table. By assigning the unevaluated table entry to its name, that element is removed from the table. This can be done by using unevaluation quotes ( ' ) or the evaln command.
${{t}}_{{1}}{\u2254}{x}$
 (92) 
${{t}}_{{1}}{\u2254}{{t}}_{{1}}$
 (93) 
${{t}}_{{\mathrm{sin}}{}\left({x}\right)}{\u2254}{y}$
 (95) 
>

t[sin(x)] := evaln(t[sin(x)]);

${{t}}_{{\mathrm{sin}}{}\left({x}\right)}{\u2254}{{t}}_{{\mathrm{sin}}{}\left({x}\right)}$
 (96) 
${{t}}_{{\mathrm{sin}}{}\left({x}\right)}$
 (97) 


Getting the Number of Elements Stored in a Table


The numelems function returns the number of elements stored in a table.
>

numelems( table( [1] ) );

>

numelems( table( [1,2,3,4,5] ) );

>

numelems( table( [seq( i, i=1..127)] ) );



Checking If an Index Is Used


It is often useful to know if a particular index has a value in a table. Use the assigned function to check if a table index has an associated entry.


Evaluation Rules for Tables


Tables, like procedures, use last name evaluation. If a name is assigned a table, the result of evaluating that name is the name and not the table assigned to the name. For more information about last name evaluation, refer to the last_name_eval help page.
${t}{\u2254}{table}{}\left(\left[{1}{=}{1}{\,}{2}{=}{2}{\,}{3}{=}{3}{\,}{4}{=}{4}\right]\right)$
 (103) 
To get the assigned value (the table), use the eval command.
${table}{}\left(\left[{1}{=}{1}{\,}{2}{=}{2}{\,}{3}{=}{3}{\,}{4}{=}{4}\right]\right)$
 (105) 


Extracting Data


Tables are often used as simple containers for data. Sometimes, it is useful to have a list of the indices used in the table. Maple provides the indices function for this purpose.
>

t := table( [a=1, b=2, c=3, d=4] );

${t}{\u2254}{table}{}\left(\left[{b}{=}{2}{\,}{d}{=}{4}{\,}{c}{=}{3}{\,}{a}{=}{1}\right]\right)$
 (106) 
$\left[{b}\right]{,}\left[{d}\right]{,}\left[{c}\right]{,}\left[{a}\right]$
 (107) 
You may not expect to see that indices returns a sequence of lists, where each list contains the index. This is because Maple allows sequences to be used as indices in tables.
>

t2 := table( [ a=1, b=2, (a,b,c)=3 ] );

${\mathrm{t2}}{\u2254}{table}{}\left(\left[{b}{=}{2}{\,}{a}{=}{1}{\,}\left({a}{\,}{b}{\,}{c}\right){=}{3}\right]\right)$
 (108) 
$\left[{b}\right]{,}\left[{a}\right]{,}\left[{a}{\,}{b}{\,}{c}\right]$
 (109) 
If the indices were not wrapped in a list, it would be impossible to determine if an index is a single expression or a sequence of expressions. Since using sequences as indices is uncommon, indices accepts a nolist option, for which indices returns a simple sequence and does not wrap each index in a list.
>

indices( t, 'nolist' );

${b}{,}{d}{,}{c}{,}{a}$
 (110) 
Note that, with the nolist option, indices that are sequences are not returned properly.
>

indices( t2, 'nolist' );

${b}{,}{a}{,}{a}{,}{b}{,}{c}$
 (111) 
You can also use the entries function to get all the values stored in the table.
$\left[{2}\right]{,}\left[{4}\right]{,}\left[{3}\right]{,}\left[{1}\right]$
 (112) 
>

entries( t, 'nolist' );

${2}{,}{4}{,}{3}{,}{1}$
 (113) 
To extract the index/entry pairs as a sequence of equations, use the pairs option to either of the indices or entries commands.
${b}{=}{2}{,}{d}{=}{4}{,}{c}{=}{3}{,}{a}{=}{1}$
 (114) 


Copying Tables


If you assign a table to multiple names, all the names reference the same table. Thus, changes to the table using one name are visible from the other names.
>

t := table( [a=1,b=2,c=3] );

${t}{\u2254}{table}{}\left(\left[{b}{=}{2}{\,}{c}{=}{3}{\,}{a}{=}{1}\right]\right)$
 (115) 
${\mathrm{t1}}{\u2254}{table}{}\left(\left[{b}{=}{2}{\,}{c}{=}{3}{\,}{a}{=}{1}\right]\right)$
 (116) 
${{t}}_{{d}}{\u2254}{4}$
 (117) 
${table}{}\left(\left[{b}{=}{2}{\,}{d}{=}{4}{\,}{c}{=}{3}{\,}{a}{=}{1}\right]\right)$
 (118) 
${table}{}\left(\left[{b}{=}{2}{\,}{d}{=}{4}{\,}{c}{=}{3}{\,}{a}{=}{1}\right]\right)$
 (119) 
If you want to create a copy of a table, use the copy function so that the tables can be modified independently.
${\mathrm{t1}}{\u2254}{table}{}\left(\left[{b}{=}{2}{\,}{d}{=}{4}{\,}{c}{=}{3}{\,}{a}{=}{1}\right]\right)$
 (120) 
${{t}}_{{e}}{\u2254}{5}$
 (121) 
${table}{}\left(\left[{b}{=}{2}{\,}{d}{=}{4}{\,}{c}{=}{3}{\,}{a}{=}{1}{\,}{e}{=}{5}\right]\right)$
 (122) 
${table}{}\left(\left[{b}{=}{2}{\,}{d}{=}{4}{\,}{c}{=}{3}{\,}{a}{=}{1}\right]\right)$
 (123) 


Applying a Function to the Contents of a Table


The map function works with tables as it does with lists and sets. When executing a map on a table, the mapped function is given the value associated with an index. In the returned table, the result is the entry associated with the index.
>

t := table( [ x, x^2+2, x^3x+1, 1/x^2 ] );

${t}{\u2254}{table}{}\left(\left[{1}{=}{x}{\,}{2}{=}{{x}}^{{2}}{+}{2}{\,}{3}{=}{{x}}^{{3}}{}{x}{+}{1}{\,}{4}{=}\frac{{1}}{{{x}}^{{2}}}\right]\right)$
 (124) 
${table}{}\left(\left[{1}{=}{1}{\,}{2}{=}{2}{}{x}{\,}{3}{=}{3}{}{{x}}^{{2}}{}{1}{\,}{4}{=}{}\frac{{2}}{{{x}}^{{3}}}\right]\right)$
 (125) 
You can use the indices and entries functions to produce a list that can be mapped over or used in a forin loop. You can also use this technique to modify the original table.
>

for i in entries(t,'pairs')
do
t[lhs(i)] := int( rhs(i), x );
end do;

${{t}}_{{1}}{\u2254}\frac{{{x}}^{{2}}}{{2}}$
 
${{t}}_{{2}}{\u2254}\frac{{1}}{{3}}{}{{x}}^{{3}}{+}{2}{}{x}$
 
${{t}}_{{3}}{\u2254}\frac{{1}}{{4}}{}{{x}}^{{4}}{}\frac{{1}}{{2}}{}{{x}}^{{2}}{+}{x}$
 
${{t}}_{{4}}{\u2254}{}\frac{{1}}{{x}}$
 (126) 
${table}{}\left(\left[{1}{=}\frac{{{x}}^{{2}}}{{2}}{\,}{2}{=}\frac{{1}}{{3}}{}{{x}}^{{3}}{+}{2}{}{x}{\,}{3}{=}\frac{{1}}{{4}}{}{{x}}^{{4}}{}\frac{{1}}{{2}}{}{{x}}^{{2}}{+}{x}{\,}{4}{=}{}\frac{{1}}{{x}}\right]\right)$
 (127) 



Arrays


In Maple, an Array stores data as an ndimensional rectangular block (rtable), that is, an Array has 1 or more dimensions and each dimension has an range of integer indices. By specifying one integer from each range, an element of the Array can be indexed.
Because Arrays are mutable, the values stored in an Array can change.

Creating Arrays


To create an Array in Maple, use the Array command and specify the ranges for the dimensions. This creates a new Array with each entry initialized to 0. For Arrays, the ranges do not need to start at 1.
>

Array( 1..3 ); # 1 dimensional Array

$\left[\begin{array}{rrr}0& 0& 0\end{array}\right]$
 (128) 
>

Array( 1..3, 1..4 ); # 2 dimensional Array

$\left[\begin{array}{rrrr}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right]$
 (129) 
>

Array( 1..3, 2..5, 1..1 ); # 3 dimensional Array

When creating an Array, you can also specify a generator function to populate the Array with data. The generator function takes an index as an argument and returns a value for the corresponding entry.
$\left[\begin{array}{rrr}2& 3& 4\end{array}\right]$
 (130) 
>

Array( 1..3, 1..4, (x,y)>(x+y) );

$\left[\begin{array}{rrrr}2& 3& 4& 5\\ 3& 4& 5& 6\\ 4& 5& 6& 7\end{array}\right]$
 (131) 
You can also provide the data for the Array by specifying the data as a list or nested lists.
$\left[\begin{array}{rrr}1& 2& 3\end{array}\right]$
 (132) 
>

Array( [[1,2],[3,4],[5,6]] );

$\left[\begin{array}{rr}1& 2\\ 3& 4\\ 5& 6\end{array}\right]$
 (133) 


Basic Data Access


Arrays are implemented in Maple as a type of rtable, a structure also used for Matrices and Vectors. This means that Arrays have two different indexing mechanisms: mathematical indexing and programmer indexing. Mathematical indexing is intended for use when the Array is viewed as a mathematical object. Programmer indexing provides functionality that is more convenient when using Arrays as a programming tool.
The basic indexing operator, [], provides mathematical indexing. Programmer indexing is accessed by using round brackets, (). For Arrays whose dimension ranges all start at 1, the two indices behave similarly.
>

A := Array( 1..2, 1..3 ):

${{A}}_{{1}{,}{1}}{\u2254}{1}$
 (134) 
$\left[\begin{array}{rrr}1& 0& 0\\ 2& 0& 0\end{array}\right]$
 (135) 
You may notice that the assignment that uses programmer indexing is displayed differently than the assignment that uses mathematical indexing. This is because the result of an assignment to a programmer indexed Array is the entire array. This can be important when working with large subArrays.
When the ranges do not start at 1, mathematical and programmer indexing are different. Mathematical indexing requires that the indices match the specified ranges, but programming indexing always normalizes the ranges to start at 1.
>

A := Array( 3..4, 5..6, (x,y)>x+y ):

This means that programmer indexing can always take advantage of negative indexing, which normally only works when the ranges start at 1. Negative indexing counts backwards from the end of the range.


SubArray Access


A subArray of an Array can be accessed by specifying a subrange in place of the indices.
>

A := Array( 1..5, 1..5, (x,y)>x+y );

$\left[\begin{array}{rrrrr}2& 3& 4& 5& 6\\ 3& 4& 5& 6& 7\\ 4& 5& 6& 7& 8\\ 5& 6& 7& 8& 9\\ 6& 7& 8& 9& 10\end{array}\right]$
 (142) 
$\left[\begin{array}{rrr}2& 3& 4\\ 3& 4& 5\end{array}\right]$
 (143) 
$\left[\begin{array}{rr}4& 5\\ 5& 6\\ 6& 7\end{array}\right]$
 (144) 
SubArray indexing can also be used to assign to the specified subArray.
>

A[2..4,2..3] := Array( [[a,a],[a,a],[a,a]] );

$\left[\begin{array}{cc}a& a\\ a& a\\ a& a\end{array}\right]$
 (145) 
>

A(4..5,4..5) := Array( [[b,b],[b,b]] );

$\left[\begin{array}{ccccc}2& 3& 4& 5& 6\\ 3& a& a& 6& 7\\ 4& a& a& 7& 8\\ 5& a& a& b& b\\ 6& 7& 8& b& b\end{array}\right]$
 (146) 
Note that the commands perform the same operation, but display the result differently. This is the consequence of an important difference in how the modification is performed. This can be important when working with large subArrays. Compare the time to perform the assignment in the following examples:
>

A := Array( 1..N, 1..N, (x,y)>rand() ):

>

B := Array( 1..N, 1..N ):

>

B[1001..4000,1001..4000]:=A[1..3000,1..3000]:

>

B(1001..4000,1001..4000):=A(1..3000,1..3000):

The difference in running time of these copies is due to the difference in the result of an assignment to an Array index. For mathematical indexing, a new 3000 by 3000 Array must be created as the result. With programmer indexing, the result is the Array being assigned to in its entirety  an object that already exists.


Automatic Resizing


One of the most important differences between mathematical and programmer indexing is automatic resizing. When reading from or writing to an entry using mathematical indexing, an index that is outside the bounds of the Array will raise an exception.
>

A := Array( [[1,2,3],[4,5,6]] );

$\left[\begin{array}{rrr}1& 2& 3\\ 4& 5& 6\end{array}\right]$
 (149) 
However, programmer indexing allows you to write to an entry that is outside the bounds of the current Array. Instead of raising an exception, the Array are automatically resized so that the element can be stored. Reading from an outofbounds index will still raise an exception.
$\left[\begin{array}{cccc}1& 2& 3& a\\ 4& 5& 6& 0\end{array}\right]$
 (150) 
$\left[\begin{array}{ccccc}1& 2& 3& a& 0\\ 4& 5& 6& 0& 0\\ 0& 0& 0& 0& b\end{array}\right]$
 (151) 


More Array Indexing


There are more features of, and differences between, mathematical and programmer indexing. For more information on Array indexing, refer to the rtable_indexing help page.


Getting the Number of Elements in an Array


The numelems function returns the number of elements defined by the bounds of an Array.
>

numelems( Array( [1,2,3,4,5] ) );

>

numelems( Array( [[1,2,3],[4,5,6]] ) );



Getting the Bounds of an Array


As Array bounds may not start at $1$, it is important that procedures that accept Arrays be aware of this possibility. The upperbound and lowerbound functions can be used to get the bounds on the ranges of an Array.
>

printer := proc( A )
local lower, upper, i, j;
lower := lowerbound( A );
upper := upperbound( A );
for i from lower[1] to upper[1]
do
for j from lower[2] to upper[2]
do
printf( "%a ", A[i,j] );
end do;
printf( "\n" );
end do;
end proc:

>

printer( Array( [[1,2],[3,4]] ) ):

>

printer( Array( 2..5, 5..7, (x,y)>(x+y) ) ):

7 8 9
8 9 10
9 10 11
10 11 12
 


Copying an Array


As with tables, having multiple variables referencing the same Array does not create new copies of the Array. You can use copy to copy the Array.
>

A := Array( 1..2, 1..2 ):

$\left[\begin{array}{rr}0& 0\\ 0& 0\end{array}\right]$
 (154) 
$\left[\begin{array}{rr}1& 0\\ 0& 0\end{array}\right]$
 (155) 
$\left[\begin{array}{rr}1& 2\\ 0& 0\end{array}\right]$
 (156) 
$\left[\begin{array}{rr}1& 0\\ 0& 0\end{array}\right]$
 (157) 


Testing If Two Arrays Are Equal


For Arrays, there are two notions of equality: do two references point to the same Array, or are they different Arrays that store the same values. To determine if two references refer to the same Array, use = and evalb. To test if two Arrays contain the same elements, use the EqualEntries command.
>

CompareArray := proc( A, B )
if A = B then
print("two names for one array");
elif EqualEntries(A,B) then
print("same elements");
else
print("at least one element is different");
end if;
end proc:

>

A := Array( [[1,2],[3,4]] );

$\left[\begin{array}{rr}1& 2\\ 3& 4\end{array}\right]$
 (158) 
$\left[\begin{array}{rr}1& 2\\ 3& 4\end{array}\right]$
 (159) 
${''same\; elements''}$
 (160) 
$\left[\begin{array}{rr}1& 2\\ 3& 4\end{array}\right]$
 (161) 
${''two\; names\; for\; one\; array''}$
 (162) 
>

B := Array( [[1,2],[3,5]] );

$\left[\begin{array}{rr}1& 2\\ 3& 5\end{array}\right]$
 (163) 
${''at\; least\; one\; element\; is\; different''}$
 (164) 
There are some other advanced notions of equality such as whether or not arrays with undefined entries should be treated as having equal entries, and whether a Matrix and Array with identical entries should be considered the same. The IsEqual command in the ArrayTools package allows for different solutions for these two issues compared to EqualEntries. The ArrayTools package contains a variety of functions for working with Arrays. For more information, refer to the ArrayTools help page.


Applying a Function to the Contents of an Array


map can be used with an Array as you would expect
>

map( x>(x/2), Array( [[1,2,3],[4,5,6]] ) );

$\left[\begin{array}{ccc}\frac{1}{2}& 1& \frac{3}{2}\\ 2& \frac{5}{2}& 3\end{array}\right]$
 (165) 
indices, entries, and the in operator work with Arrays, so you can use Arrays in add, mul, and for loops. entries(A,pairs) can also be used to obtain a list of index/value pairs in the same way that it does for tables.
>

A := Array( [x,x^3,sin(x)] ):

>

for entry in entries(A,'pairs')
do
A[lhs(entry)] := diff( rhs(entry), x ):
end do:

$\left[\begin{array}{ccc}1& 3{}{x}^{2}& \mathrm{cos}{}\left(x\right)\end{array}\right]$
 (166) 


Better Performance with Numeric Arrays


When creating an Array, you can specify a datatype for the Array elements. The given datatype can be either a Maple type or a hardware datatype specifier: integer[n], float[n], complex[n]. n refers to the number of bytes of data for each element. For integer[n], n can be 1, 2, 4, or 8. For float[n] or complex[n], n can be 4 or 8. The datatype integer[4] uses 4bytes, or 32bits per integer, and integer[8] uses 8bytes, or 64bits. The 64bit version has a wider range of signed values, but uses more memory.
When assigning values into the Array, Maple will raise an exception if the given value does not match the specified type.
>

A := Array( [1,2,3,4], datatype=float[8] );

$\left[\begin{array}{cccc}1.0& 2.0& 3.0& 4.0\end{array}\right]$
 (167) 
${{A}}_{{1}}{\u2254}{1.5}$
 (169) 
If you are working with numeric values that can be stored in these hardware types, it can be much faster to use an Array with a hardware type. For more information on numerical programming in Maple, see Numerical Programming in Maple.


Deprecated: array


The array data structure is an older implementation of Arrays. Its use has been deprecated; use Array instead.




4.5 Other Data Structure Operations



Filtering Data Structure Elements


The select, remove, and selectremove functions provide ways to filter the elements of data structures.
select( f, x )

remove( f, x )

selectremove( f, x )



The parameter f must be a Booleanvalued function. This function is applied to each of the elements of the data structure x. select returns the a data structure containing those elements for which f returns true. remove returns a data structure containing those elements for which f returns false. selectremove returns two structures, the first consisting of the elements for which f returned true and the second consisting of the elements for which f returns false.
The type of the return value of these functions matches the type of the argument x.
${x}{\u2254}\left[{1}{\,}{2}{\,}{3}{\,}{4}{\,}{5}{\,}{6}{\,}{7}{\,}{8}{\,}{9}{\,}{10}\right]$
 (170) 
$\left[{2}{\,}{3}{\,}{5}{\,}{7}\right]$
 (171) 
$\left[{1}{\,}{4}{\,}{6}{\,}{8}{\,}{9}{\,}{10}\right]$
 (172) 
>

selectremove( isprime, x );

$\left[{2}{\,}{3}{\,}{5}{\,}{7}\right]{,}\left[{1}{\,}{4}{\,}{6}{\,}{8}{\,}{9}{\,}{10}\right]$
 (173) 
Calling selectremove is more efficient than calling select and remove separately.


Converting Data Structures


Maple provides the convert function, which allows various expressions to be converted from one form to another.
convert attempts to convert the expression x into the form t. In particular, Maple supports conversions between the list, set, table, and Array types.
${x}{\u2254}\left[{1}{\,}{2}{\,}{3}{\,}{4}\right]$
 (174) 
$\left\{{1}{\,}{2}{\,}{3}{\,}{4}\right\}$
 (175) 
${table}{}\left(\left[{1}{=}{1}{\,}{2}{=}{2}{\,}{3}{=}{3}{\,}{4}{=}{4}\right]\right)$
 (176) 
$\left[\begin{array}{rrrr}1& 2& 3& 4\end{array}\right]$
 (177) 



4.6 Other Data Structures



Records


In Maple, a record is a structured data type. It allows you to create a fixedsize structure with userdefined fields. You can use records to create customized structures that can make Maple code easier to read and write.

Create a Record


To create a new record, use the Record command. Record accepts a sequence of names as parameters. Each name becomes a field in the returned record.
>

r := Record( 'expression', 'variable' );

${r}{\u2254}{\mathrm{Record}}{}\left({\mathrm{expression}}{\,}{\mathrm{variable}}\right)$
 (178) 
${\mathrm{expression}}{\u2254}{{x}}^{{2}}$
 (179) 
${\mathrm{variable}}{\u2254}{x}$
 (180) 
>

int( r:expression, r:variable );

$\frac{{{x}}^{{3}}}{{3}}$
 (181) 
If Record is passed a single record as an argument, a copy of that record is returned.
>

r2 := Record( eval(r,1) );

${\mathrm{r2}}{\u2254}{\mathrm{Record}}{}\left({\mathrm{expression}}{=}{{x}}^{{2}}{\,}{\mathrm{variable}}{=}{x}\right)$
 (182) 
>

r2:expression := sin(x^2);

${\mathrm{expression}}{\u2254}{\mathrm{sin}}{}\left({{x}}^{{2}}\right)$
 (183) 
>

int( r2:expression, r2:variable );

$\frac{\sqrt{{2}}{}\sqrt{{\mathrm{\pi}}}{}{\mathrm{FresnelS}}{}\left(\frac{\sqrt{{2}}{}{x}}{\sqrt{{\mathrm{\pi}}}}\right)}{{2}}$
 (184) 
Note that you must call eval on r before passing it into Record. This is because records use last name evaluation rules, similar to tables.


Record Equality


As with Arrays, two references to Records are considered equal if they reference the same structure. Two different structures that have the same fields and values are not considered equal.
>

r := Record( 'a'=1, 'b'=2, 'c'=3 ):

>

r2 := Record( 'a'=1, 'b'=2, 'c'=3 ):

To compare two different records, you can use the verify command with the record argument. verify/record returns true if the two records have the same set of fields with equal values assigned to them.
>

r3 := Record( 'a'=1, 'b'=2, 'c'=3, 'd'=4 ):

>

r4 := Record( 'a'=1, 'b'=2, 'c'=4 ):

>

verify( r, r2, 'record' );

>

verify( r, r3, 'record' );

>

verify( r, r4, 'record' );



Packed Records


The Record constructor function can also be called with the indexed name Record[packed], to produce a packed record.
Unlike a regular record, a packed record does not create a unique instance of each field name for each record instance. When working with thousands of similar records each with many fields, this can save a significant amount of memory.
Fields of packed records do not exhibit last name evaluation. That is, the expression r:a always produces a value, even if that value is a procedure, table, Matrix, Vector, or another record.
Similarly, it is not possible for a packed record field to not have a value. The assigned function will always return true, and unassigning a packed record field will set its value to NULL instead.



Stacks


A stack is an abstract data type that provides two main operations: push and pop. A push places a new value onto the top of the stack and pushes the existing elements down. A pop removes the element from the top of the stack, moving the elements below up. This creates a element access order referred to as last in first out (LIFO).
Stacks are useful for many operations. A typical use of a stack is to turn a recursive algorithm into an iterative one. Instead of recursing on elements, those elements get pushed onto a stack. When the current element has been handled, the element on top of the stack is removed and handled next. By using a stack, the recently discovered elements are handled before elements that were already in the stack, which is similar to how a recursive algorithm works.

Creating a Stack


In Maple, you can create a stack by calling stack:new. If you do not specify any arguments, stack:new creates an empty stack. Maple stacks are implemented on top of tables.
You can also pass values into stack:new that populate the stack. These elements are pushed in the order specified.
>

s := stack:new(1,2,3,4,5):



Pushing and Popping


To push and pop elements onto the stack, use the stack:push and stack:pop functions.


More Stack Functions


To get the number of elements stored in the stack, call stack:depth.
>

s := stack:new(a,b,c):

>

while stack:depth( s ) > 0
do
print( stack:pop( s ) );
end do;

To test if a stack is empty, call stack:empty.
>

s := stack:new(c,b,a):

>

while not stack:empty( s )
do
print( stack:pop( s ) );
end do;

You can examine the element on the top of a stack, without removing it, by calling stack:top.
>

s := stack:new(x,x^2,sin(x)):

${\mathrm{sin}}{}\left({x}\right)$
 (202) 
${\mathrm{sin}}{}\left({x}\right)$
 (203) 



Queues


The queue is an abstract data type similar to a stack; however, instead of the most recently added element being returned first, the oldest element in the queue is returned first. Elements in a queue are analogous to people waiting in a line. The main operations provided by a queue are enqueue, which adds an element to the queue, and dequeue, which removes an element from the queue. The access order used by a queue is called first in first out, or FIFO.
A queue is used when you want to handle elements in the order that they are discovered. A typical example of using a queue is a breadthfirst search of a graph. You dequeue a node and then enqueue any unvisited nodes that are neighbors of the current node. By using a queue, the order in which the nodes are visited is breadthfirst.

Create a Queue


To create a queue in Maple, use the queue:new command.
>

queue:enqueue( q, 1 );

>

queue:enqueue( q, 2 );

You can also pass values into queue:new to populate the new queue. The elements are enqueued in the order they are specified.
>

q := queue:new( 1,2,3 ):



Enqueue and Dequeue


You can insert a new element into a queue using queue:enqueue and remove an element from the queue using queue:dequeue.
>

queue:enqueue( q, 1 ):

>

queue:enqueue( q, 2 ):

>

queue:enqueue( q, 3 ):



More Queue Functions


You can get the number of elements stored in the queue by calling queue:length.
>

q := queue:new(a,b,c):

>

while queue:length( q ) > 0
do
print( queue:dequeue( q ) );
end do;

You can test if a queue is empty by calling queue:empty.
>

q := queue:new(c,b,a):

>

while not queue:empty( q )
do
print( queue:dequeue( q ) );
end do;

You can examine the front element of a queue, without removing it, by calling queue:front.
>

q := queue:new(x,x^2,sin(x)):

${\mathrm{sin}}{}\left({x}\right)$
 (228) 




4.7 Data Coercion


Data Coercion refers to the ability to take one data type and automatically convert it into a different data type. This is particularly useful for arguments passed into a procedure, where the expected data type for the procedure is explicitly declared. For more information on data coercion in Maple, see the coercion help page.
Maple provides two methods for enabling data coercion. For more information see The coercion Modifiers.


4.8 Data Structure Performance Comparisons


Maple provides many different data structures, many of which can be used together to perform specific tasks. However, the different performance characteristics of the data structures means that some are better than others in certain situations.

Indexing


The time to perform an indexed lookup into a list, set, table, and Array are all constant time operations. This means that the time needed to find the element does not vary based on the number of elements stored in the structure. Time to perform a lookup into a list or set is relatively similar and is faster than Arrays, which is faster than a table.
Similarly, writing into a table or Array is also a constant time operation, with Array lookups being slightly faster than table lookups.


Membership


The member function determines if a particular element is stored in a structure. For lists, this requires a linear search of the data in the list. Therefore, the time is proportional to the total length of the list. A set is sorted, so searches of the list can be performed more quickly. Searching within a set takes time proportional to the log[2] of the number of elements in the set.
You can use a table for very fast membership testing. Use the table key as objects you want to test for, and anything you want for the value. You can then call the assigned command to test if the element exists in the table. A table index is a constant time operation, so this membership test is also constant time.
>

memtest := proc( D, N )
local i;
for i from 1 to N
do
member( i, D ):
end do:
end proc:

>

L := [seq( i, i=1..N )]:

>

S := {seq( i, i=1..N )}:

>

t := table( [seq( i=1, i=1..N ) ] ):

>

start := time():
for i from 1 to N
do
assigned( t[i] ):
end do:
time()start;

Note that to benchmark the list and set membership functions, the call to member is within a function. This is because of the Maple evaluation rules. If the call to the member command is at the top level, the list or set is fully evaluated, which requires inspecting each element of the list or set for each call to member. The overhead required for these full evaluations would distort the results.
For more information on the Maple evaluation rules, see Unevaluated Expressions.


Building a Collection of Data


It is often necessary to build a collection of data when you do not know how many elements you are going to have. You should use a table, Array (using programmer indexing), stack, or queue. All of these mutable structures support adding elements in constant time. Using an immutable data structure is slower; the use of a list or a set is not recommended in this situation.
>

A := Array( [] ):
start := time():
for i from 1 to N
do
A( i ) := 1:
end do:
time()start;

>

t := table():
start:=time():
for i from 1 to N
do
t[i] := 1:
end do:
time()start;

>

l := []: # using a list is quite slow
start := time():
for i from 1 to N
do
l := [ op(l), i ]:
end do:
time()start;




4.9 Avoiding Common Problems


When working with data structures, there are a few common problems that you may encounter. This section describes some of these problems to help you avoid making these mistakes yourself.

Passing Sequences into Functions


When a sequence is passed into a procedure, each element of the sequence is treated as a separate argument. This can lead to errors if the procedure is unable to handle the multiple arguments, for example, with the op command.
${s}{\u2254}{a}{,}{b}{,}{c}$
 (235) 
Instead, wrap the sequence in a list.


Incorrect Index Values


Be careful with the values used for indexing. Specifying values outside valid ranges will raise exceptions. In particular, in Maple, lists and sets start indexing at 1, not 0.
>

L := [1,2,3,4,5,6,7,8];

${L}{\u2254}\left[{1}{\,}{2}{\,}{3}{\,}{4}{\,}{5}{\,}{6}{\,}{7}{\,}{8}\right]$
 (237) 
Further, when specifying the endpoints of a range, make sure that the lefthand side of the range specifies an element before the element specified by the righthand side.
The only exception to this is if the lefthand side of the range is n, then the righthand side can be n1 and the result of this range is an empty structure (list or set).
Similar exceptions happen with using [] for selection from Arrays.
>

A := Array( [5,6,7,8,9,10] );

$\left[\begin{array}{rrrrrr}5& 6& 7& 8& 9& 10\end{array}\right]$
 (239) 
Another type of index error occurs when sum is used instead of add to obtain explicit sums over all the elements of a list, Array, Matrix, Vector, or similar data structures.
>

V := Vector(5,{(1)=1,(2)=2,(3)=3,(4)=4,(5)=5}):


Array Indices Do Not Always Start at 1


In an Array, the lower bound of the indices may not be 1. If you write a procedure that accepts an Array, you should be prepared to handle Arrays that have been defined for a range of indices that does not start at 1. For more information on how to write procedures that can handle such Arrays, see Getting the Bounds of an Array.



Do Not Treat Lists and Sets as Mutable


You can use commands such as op and subsop with lists and sets to create new structures. It is, therefore, possible to treat lists and sets like mutable structures. However, by doing so, you can add a significant amount of processing time to your computations. Make sure that you use actual mutable structures instead.
>

l := [seq( i=i, i=1..N)]:

>

t := table( l ):
start:=time():
for i from N to 1 by 1
do
t[i] := evaln(t[i]):
end do:
time()start;

>

start := time():
for i from N to 1 by 1
do
l := subsop( i=NULL, l );
end do:
time()start;




4.10 Exercises


1.

Define a set with elements that are the powers of 13 modulo 100 for exponents ranging from 1 to 1000. Is 5 a member of the set? Why is it beneficial to use a set instead of a list?

Hint: You can determine the set by using one statement if you use the seq command.
2.

Generate the sums of 4 and the first 100 multiples of 3. Determine the sums that are squarefree composite numbers.

Hint: The NumberTheory package has a function that you need to use.
3.

Find floatingpoint approximations for the sum of the square root and cubic root of each of the first 15 powers of 2.

Hint: Use map, seq, and zip.
4.

Write a procedure that implements the sieve of Eratosthenes: Count the number of integers (less than or equal to a given integer) that are prime.



Contents Previous Next Index
