An expression sequence is the underlying data structure for lists, sets, and function call arguments in Maple. Conceptually, a list is just a sequence enclosed in "[" and "]", a set is a sequence (with no duplicate elements) enclosed in "{" and "}", and a function call is a sequence enclosed in "funcName(" and ")". A sequence can also be used as a data structure itself:
> Q := x, 42, "string", 42;
Q := x, 42, "string", 42
> L := [ Q ];
L := [x, 42, "string", 42]
> S := { Q };
S := {42, "string", x}
> F := f( Q );
F := f(x, 42, "string", 42)
A sequence, like most data structures in Maple, is immutable. Once created, it cannot be changed. This means the same sequence can be shared by multiple data structures. In the example above, the list assigned to L and the function call assigned to F both share the same instance of the sequence assigned to Q. The set assigned to S refers to a different sequence, one with the duplicate 42 removed, and sorted into a canonical order.
Appending an element to a sequence creates a new sequence. The original remains unaltered, and still referenced by the list and function call:
> Q := Q, a+b;
Q := x, 42, "string", 42, a + b
> L;
[x, 42, "string", 42]
> S;
{42, "string", x}
> F;
f(x, 42, "string", 42)
Because appending to a sequence creates a new sequence, building a long sequence by appending one element at a time is very inefficient in both time and space. Building a sequence of length N this way creates N sequences of lengths 1, 2, ..., N-1, N. The extra space used will eventually be reclaimed by Maple's garbage collector, but this takes time.
This leads to the subject of this article, which is how to create long sequences efficiently. For the remainder of this article, the sequence we will use is the Fibonacci numbers, which are defined as follows:
- Fib(0) = 0
- Fib(1) = 1
- Fib(N) = Fib(N-1) + Fib(N-2) for all N > 1
In a computer algebra system like Maple, the simplest way to generate individual members of this sequence is with a recursive function. This is also very efficient if option remember is used (and very inefficient if it is not; computing Fib(N) requires 2 Fib(N) - 1 calls, and Fib(N) grows exponentially):
> Fib := proc(N)
> option remember;
> if N = 0 then
> 0
> elif N = 1 then
> 1
> else
> Fib(N-1) + Fib(N-2)
> end if
> end proc:
> Fib(1);
1
> Fib(2);
1
> Fib(5);
5
> Fib(10);
55
> Fib(20);
6765
> Fib(50);
12586269025
> Fib(100);
354224848179261915075
> Fib(200);
280571172992510140037611932413038677189525
How Not to Do It
Let's start with the most straightforward, and most inefficient way to generate a sequence of the first 100 Fibonacci numbers, starting with an empty sequence and using a for-loop to append one member at a time. Part of the output has been elided below in the interests of saving space:
> Q := ();
Q :=
> for i from 0 to 99 do
> Q := Q, Fib(i)
> end do:
> Q;
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811,
...
51680708854858323072, 83621143489848422977, 135301852344706746049,
218922995834555169026
As mentioned previously, this actually produces 100 sequences of lengths 1 to 100, of which 99 will (eventually) be recovered by the garbage collector. This method is O(N2) (Big O Notation) in time and space, meaning that producing a sequence of 200 values this way will take 4 times the time and memory as a sequence of 100 values.
Using the seq Function
The traditional Maple wisdom is to use the seq function instead, which produces only the requested sequence, and no intermediate ones:
> Q := seq(Fib(i),i=0..99);
Q := 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
...
51680708854858323072, 83621143489848422977, 135301852344706746049,
218922995834555169026
This is O(N) in time and space; generating a sequence of 200 elements takes twice the time and memory required for a sequence of 100 elements.
Loops That Are Expressions
As of Maple 2019, it is also possible to achieve O(N) performance by constructing a sequence directly using a for-expression, without the cost of constructing the intermediate sequences that a for-statement would incur:
> Q := (for i from 0 to 99 do Fib(i) end do);
Q := 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
...
51680708854858323072, 83621143489848422977, 135301852344706746049,
218922995834555169026
This method is especially useful when you wish to add a condition to the elements selected for the sequence, since the full capabilities of Maple loops can be used (see The Two Kinds of Loops in Maple). The following two examples produce a sequence containing only the odd members of the first 100 Fibonacci numbers, and the first 100 odd Fibonacci numbers respectively:
> Q := (for i from 0 to 99 do
> f := Fib(i);
> if f :: odd then
> f
> else
> NULL
> end if
> end do);
Q := 1, 1, 3, 5, 13, 21, 55, 89, 233, 377, 987, 1597, 4181, 6765, 17711, 28657,
75025, 121393, 317811, 514229, 1346269, 2178309, 5702887, 9227465,
...
19740274219868223167, 31940434634990099905, 83621143489848422977,
135301852344706746049
> count := 0:
> Q := (for i from 0 while count < 100 do
> f := Fib(i);
> if f :: odd then
> count += 1;
> f
> else
> NULL
> end if
> end do);
Q := 1, 1, 3, 5, 13, 21, 55, 89, 233, 377, 987, 1597, 4181, 6765, 17711, 28657,
75025, 121393, 317811, 514229, 1346269, 2178309, 5702887, 9227465,
...
898923707008479989274290850145, 1454489111232772683678306641953,
3807901929474025356630904134051, 6161314747715278029583501626149
> i;
150
A for-loop used as an expression generates a sequence, producing one member for each iteration of the loop. The value of that member is the last expression computed during the iteration. If the last expression in an iteration is NULL, no value is produced for that iteration.
Examining i after the second loop completes, we can see that 149 Fibonacci numbers were generated to find the first 100 odd ones. (The loop control variable is incremented before the while condition is checked, hence i is one more than the number of completed iterations.)
Generating the Fibonacci Sequence Directly
Until now, we've been using calls to the Fib function to generate the individual Fibonacci numbers. These numbers can of course also be generated by a simple loop which, together with assignment of its initial conditions, can be written as a single sequence:
> Q := ((f0 := 0),
> (f1 := 1),
> (for i from 2 to 99 do
> f0, f1 := f1, f0 + f1;
> f1
> end do));
Q := 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
...
51680708854858323072, 83621143489848422977, 135301852344706746049,
218922995834555169026
Using Arrays
A Maple Array is a mutable data structure. Changing an element of an Array modifies the Array in-place; no new copy is generated:
> A := Array([a,b,c]);
A := [a, b, c]
> A[2] := d;
A[2] := d
> A;
[a, d, c]
It is also possible to append elements to an array, either by using programmer indexing, or the recently introduced ,= operator:
> A(numelems(A)+1) := e; # () instead of [] denotes "programmer indexing"
A := [a, d, c, e]
> A;
[a, d, c, e]
Like appending to a sequence, this sometimes causes the existing data to be discarded and new data to be allocated, but this is done in chunks proportional to the current size of the Array, resulting in time and memory usage that is still O(N). This can be used to advantage to generate sequences efficiently:
> A := Array(0..1,[0,1]);
[ 0..1 1-D Array ]
A := [ Data Type: anything ]
[ Storage: rectangular ]
[ Order: Fortran_order ]
> for i from 2 to 99 do
> A ,= A[i-1] + A[i-2]
> end do:
> A;
[ 0..99 1-D Array ]
[ Data Type: anything ]
[ Storage: rectangular ]
[ Order: Fortran_order ]
> Q := seq(A);
Q := 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
...
51680708854858323072, 83621143489848422977, 135301852344706746049,
218922995834555169026
Bonus Feature - Efficient String Construction Using Arrays of Characters
Although unrelated specifically to the goal of producing sequences, the same techniques can be used to construct Maple strings efficiently:
> A := Array("0");
A := [48]
> for i from 1 to 99 do
> A ,= " ", String(Fib(i))
> end do:
> A;
[ 1..1150 1-D Array ]
[ Data Type: integer[1] ]
[ Storage: rectangular ]
[ Order: Fortran_order ]
> A[1..10];
[48, 32, 49, 32, 49, 32, 50, 32, 51, 32]
> S := String(A);
S := "0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 \
10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 134626\
9 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 1\
02334155 165580141 267914296 433494437 701408733 1134903170 1836311903 \
2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53\
316291173 86267571272 139583862445 225851433717 365435296162 5912867298\
79 956722026041 1548008755920 2504730781961 4052739537881 6557470319842\
10610209857723 17167680177565 27777890035288 44945570212853 7272346024\
8141 117669030460994 190392490709135 308061521170129 498454011879264 80\
6515533049393 1304969544928657 2111485077978050 3416454622906707 552793\
9700884757 8944394323791464 14472334024676221 23416728348467685 3788906\
2373143906 61305790721611591 99194853094755497 160500643816367088 25969\
5496911122585 420196140727489673 679891637638612258 1100087778366101931\
1779979416004714189 2880067194370816120 4660046610375530309 7540113804\
746346429 12200160415121876738 19740274219868223167 3194043463499009990\
5 51680708854858323072 83621143489848422977 135301852344706746049 21892\
2995834555169026"
A call to the Array constructor with a string as an argument produces an array of bytes (Maple data type integer[1]). The ,= operator can then be used to append additional characters or strings, with O(N) efficiency. Finally, the Array can be converted back into a Maple string.
Conclusion
Constructing sequences in Maple is a common operation when writing Maple programs. Maple gives you many ways to do this, and it's worthwhile taking the time to choose a method that is efficient, and suitable to the task at hand.
