Workshop: Learning Maths with APL
Vector 9:4, page 36
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 36
Sample Topic: "Triangular Numbers"¶
First, the primitive function ⍳ is introduced by an example:
The example is intended to be strongly suggestive in provoking thinking. The learner may well try other examples, such as ⍳6 or ⍳8 or even ⍳1000 (which would overflow the screen while instilling a certain sense of power) or better yet experiment systematically (⍳5, then ⍳4, then ⍳3, then ⍳2, then ⍳1) to see a pattern clearly. Then one can infer how to define the function precisely: ⍳ is the Integer function, which generates all consecutive indices starting with 1 up to (and including) the integer given. The learner might also test special cases, such as ⍳0 (which produces an empty list, yet is consistent with the above definition) and discover the limits of its domain — ruling out negative numbers and decimal numbers (which yield DOMAIN ERROR from the computer).
Further, the syntax is important to notice: ⍳ is a "monadic" function (i.e. it has one input), in contrast to "dyadic" functions, such as + and * (which have two inputs). This distinction may have been introduced already, perhaps along with the new knowledge that all APL functions are either monadic or dyadic. Nevertheless, this is an opportunity to reinforce this important APL concept while monitoring disequilibrium with the learner’s previous understanding of function syntax, which may need clarification due to inconsistencies inherent in conventional mathematical notation (see [1]).
Careful interpretation is also needed because the learner may well try using ⍳ with other functions, as in 10×⍳7, which gives 10 20 30 40 50 60 70; or ⍳7×10, which yields 1 2 3 ... 69 70. The contrast is important to note — 10 Times the result of ⍳7 vs. ⍳ of the result of 7 Times 10 — because it raises the issue of how APL evaluates expressions with more than one function. Through experimentation, the learner can realize APL’s rule: every function uses the entire expression on its right (unless indicated otherwise with parentheses). This rule applies equally to all functions; that is, there is no hierarchy of functions in APL, as there is in conventional mathematics (exponentiation before × and / before + and −).
Although APL appears to accommodate many cases (e.g. (2×3)+4 is 10), it can produce some unexpected results (e.g. 2×3+4 is 14 in APL because 3+4 is done first). While it may take more time for the learner to adjust to APL, at this stage it is advisable to use redundant parentheses to clarify order of operation. Eventually changing to this new rule can empower the learner by offering some 60 primitive functions on the keyboard (plus more which can be derived or defined as programs) and the convenience of a single, completely general rule to handle any expression with any number of functions, without having to memorize or look up which gets done before another.
The next expression shown on the handout is:
The Sum function +/ has probably been introduced already (as in the topic on Averaging). If not, for now suffice it to say that +/ inserts + between each number (and evaluates the resulting expression). And defer interest in exploring the operator / (which can be used with other functions) for another time.
The overall objective of this topic is to explore alternative ways of finding the sum of consecutive integers. Accordingly, the next four expressions illustrate a different algorithm.
The learner may explore the behaviour of the Reverse function ⌽ on other lists (including characters, for instance ⌽'LIVE' is 'EVIL') or indeed on other arrays such as matrices (which become reversed about the vertical axis, as indicated mnemonically by the symbol ⌽ itself). This leads naturally to another topic: palindromes (not discussed here).
APL performs this addition in parallel, automatically. Learners may try similar expressions with other appropriate functions. Since the concept of parallel processing is likely to be new knowledge, it may need to be addressed again later (as in a "spiral curriculum"), perhaps including the special case of a single value (e.g. 10×⍳7 mentioned above). For now, however, the learner should concentrate on building an expression to represent this particular algorithm, which involves adding a list to itself. Incidentally, another similar algorithm folds the list about its centre point but raises the issue of odd vs. even length lists (not discussed here).
Note that +/ applies to the result of everything to its right. (+/(⌽⍳7)+(⍳7))÷2 Half of that is 28 28. The learner may notice that this is the same result obtained earlier (by summing directly using +/). So, this is apparently another way to find the sum of counting integers!
This algorithm can be embodied in a "glass box" program for further study, like this:
The name of the program (GAUSS) is chosen for historical reasons (see story below).
Note use of ⍵ to represent the input, which can be any integer. If other mechanics of defining a program have not been introduced yet, just say: "Type a name followed by a colon, then the algorithm (expressed in terms of ⍵ for the input it will get later)" and be prepared to help in subsequent editing.
Giving an algorithm a name provides a more convenient way to try it out. For example:
The learner may try it again for a different input (besides 7). Reflecting on the algorithm can lead to insight: there are always N copies of N+1 to be summed and then halved.
Anecdotally, there is a story about the young German mathematics prodigy, Karl Friedrich Gauss, who is said to have discovered a simple way of calculating the sum of N integers in the late 18th century. When asked by his schoolmaster to take out his slate and add the integers from 1 to 1000 (or some such large number) in order to keep Karl busy for a while (since he was probably bored and disturbing other students and the teacher with difficult questions), Karl came up with the answer startlingly fast. Here, having experienced the development of the algorithm (above), the learner can join in speculation about how Karl might have done it.
Finally, another expression is given. It also results in 28:
This may be recognised as a particular case of what has come to be known as "Gauss’s Formula": n(n+1)/2 in conventional notation. The formula calculates the sum of the integers from 1 to n. It may be compared with the algorithms above and seen to be exceedingly more efficient. The learner can easily express this in APL: N×(N+1)÷2 and try it for any value(s) of N or, better yet, construct another glass box program:
This program may be used with several input values at once, yielding patterns worthy of further study. For example:
TRI 10 100 1000 10000 100000
55 5050 500500 50005000 500000500000
TRI 1 2 3 4 5 6 7 8 9 10
1 3 6 10 15 21 28 36 45 55
Note: the 7th TRI result is 28.
These are "triangular numbers", so named because they represent the number of (lattice) points in a triangle, as shown below:
. Note: The first triangular number is 1
. . (one dot in the first row); the second
. . . is 3 (1+2 dots in the first two rows);
. . . . third is 6 (1+2+3 dots in three rows);
. . . . . fourth is 10 (1+2+3+4 from four rows);
. . . . . . fifth is 15; sixth is 21; and seventh
. . . . . . . is 28 (1+2+3+4+5+6+7 from all seven rows).
Thinking of a triangular number as an area leads to a nice geometric representation of Gauss’ formula as half the area of a N by N+1 rectangle formed by sliding two triangles together:
_ _______________
|.\ \. . . . . . .|
|. .\ \. . . . . .|
|. . .\ \. . . . .|
|. . . .\ \. . . .|
|. . . . .\ \. . .|
|. . . . . .\ \. .|
|. . . . . . .\ \.|
‾‾‾‾‾‾‾‾‾‾‾‾‾‾ ‾
Finally, the learner may now be informed that APL provides a primitive function, called Sum-Scan, which produces a list of triangular numbers directly:
Exploring this function by itself may lead to more discoveries, for instance, that Sum-Scan of odd integers produces squares:
And successive Sum-Scans are found in Pascal’s triangle (which is a likely next topic for a workshop).
For now, in closing, the learner can put GAUSS and TRI in his/her conceptual "tool box" (as well as save them on a computer disk) for later modification and use, perhaps along with other tools, for learning mathematics.
Reference¶
[1] Peelle, H.A. "Introduction to APL for Learning Mathematics", Journal of Computers in Mathematics and Science Teaching, Vol.9(1) Fall 1989.
Sample Hand-out Worksheet: Teaching Mathematics with APL¶
Examine the following APL expressions and write annotations in the margins on this page (and back, if needed) briefly describing what you think each expression does.
As you proceed, use the computer to explore unfamiliar symbols by trying additional similar expressions. By observing patterns in the results, try to infer how each symbol works in general.
Review the overall sequence of expressions given and identify the algorithm or topic illustrated here. Embody the algorithm in a program, modify it for your own purposes, explore related topics (if you have time), and mention possible applications of the program(s).