The TAO of Dyalog APL

Roger K.W. Hui
John M. Scholes

 




⎕io←0

Here, the index origin is 0, although the ideas, algorithms, code, examples, …, work in 1-origin with obvious modifications.
 

Benefits

The extension to index-of () since version 14.0 [0] made it possible to “find anything”. Here, we propose to extend grade () so that we can “sort anything”.

In a sorted array, equal items are put adjacent to each other, thereby facilitating grouping, classification, removing duplicates, etc. Having a TAO (total array ordering) also expands the utility of interval index ().

And, of course, walking in the TAO is the way to enlightenment.

J has a TAO [1] implemented no later than 1996-01-16 [2]; the idea was suggested by Arthur Whitney.
 

The Current

The current grade(and) works on non-scalar arrays which are all real numbers or all characters. It compares major cells item-wise in ravel order (lexicographic ordering), and uses exact comparisons, as if 0=⎕ct .

Grade currently rejects complex numbers and (more importantly) rejects non-simple arrays. In initial discussions some Dyalog colleagues were surprised [3] that it currently rejects arrays of character strings. (Because it makes so much sense to be able to sort them.)
 

Precede (le) 0

What is required to have a TAO is to extend the precede relation used in grade, commonly denoted by the curly less than or equal symbol ≼ [4]. For arrays A and B , A≼B is 1 if if and only if A precedes (or is equal to) B in the ordering.

The first example shows precede working on arrays with different shapes. The next two example show it working on arrays with different types and that it is anti-symmetric. The next example shows that precede is transitive. The last example shows it working on complex numbers.

The function le in the dfns workspace models the extended precede [5]. Conversely, you can discover and recover the precede used in grade with a simple function.
 

Precede (le) 1

The extended rules for precede are shown here and are a consistent extension of the current rules. Certain aspects are necessarily arbitrary (e.g. characters precede numbers) but the benefits described at the beginning still obtain.
 

Precede (le) 2

It is instructive to look at which parts of the rules are new. The current rules are shown in red.

The rules covering namespaces and ⎕or are quite involved. They are not discussed here; the full details are in the dfns page [5]. It is possible that the initial implementation of the TAO will not include namespaces and ⎕or .
 

TAO in Action 0

Sort and grade can be implemented readily on top of precede by use of a comparison sort. For example, Quicksort [6].

Quicksort works by choosing a “pivot” at random among the major cells, then catenating the sorted result of the major cells which strictly precede the pivot, the major cells equal to the pivot, and the sorted result of the major cells which strictly follow the pivot.

The operand ⍺⍺ is required to be a function which returns a number less than 0, equal to 0, or greater than 0, according to whetherstrictly precedes, equals, or strictly follows . This is specified as the function in red in qsort .

Grade obtains from sort by sorting a 2-column matrix of the major cells and corresponding indices (shown in red), and then discarding the first column from the result.
 

TAO in Action 1

These examples show the extended sort and grade working on enclosed strings, on complex numbers, on arrays with mixed types, and on arrays with different ranks.
 

TAO in Action 2

The problem is to group people by last name and trying to have equal sized groups. Because names are not equally distributed by initial letters, you’d want to have ranges. e.g. A-H, I-O, P-R, Sa-Sl, Sm-Sz, T-Z.
 

References

[0]   Hui, Roger K.W., Potential Version 14.0 Language Features, Dyalog User Conference, Helsingør, Denmark, 2012-10-15.
[1] Hui, Roger K.W., and Kenneth E. Iverson, J Introduction and Dictionary, 2001-05-03; /: entry.
[2] Hui, Roger K.W., J Implementation Status, Release 3.01, 1996-01-06.
[3] Hui, Roger K.W., v17 Ideas, Dyalog Internal Meeting, 2017-02-08.
[4] Knuth, Donald E., The Art of Computer Programming, Volume 1, Fundamental Algorithms, Addison-Wesley, 1968; page 258.
[5] Scholes, John M., Total Array Ordering, dfns, 2012-05-29.
[6] Hui, Roger K.W., A History of APL in 50 Functions, 2016-11-27; §7.



created:  2016-05-23 06:00
updated: