Array ordering

Array ordering is the ordering of arrays exposed by functions such as Grade and Interval Index. It may be more general than comparison, for example by allowing characters to be compared to each other and to numbers. However, not all arrays need to be comparable, meaning that functions that depend on array ordering can throw an error. Traditionally, ordering is defined only for simple arrays of the same shape and type (Grade of a simple array only requires this sort of comparison), and is determined by the ordering of the first unequal pair of elements in those arrays in ravel order. Various extensions to other domains have been defined, including an extension to numbers and characters in all shapes and combinations in Dyalog APL known as total array order (TAO).

Examples

While two characters can't be compared directly in most APL implementations, their array ordering can be observed with Grade:

      'b'>'a'
DOMAIN ERROR
      'b'>'a'
         ∧

      ⍋ 'ba'
2 1

Grade reverses the order of these elements, showing that 'a' comes before 'b' in the array ordering. In general, 1=⊃⍋X Y tests whether array X precedes or matches Y. However, ⍋X Y doesn't distinguish between these two cases, so for complete information about the ordering, these arrays must also be graded in the opposite order.

The concept of an ordering distinct from comparison functions was introduced by SHARP APL in 1980: "The domain of the grade functions (⍋ and ⍒), previously restricted to numeric vectors, has been extended to all numeric arrays of rank greater than 0". For the major cells of such an array, which may have any shape but all share the same one, SHARP defines a "lexical" ordering where the first pair of differing elements in ravel order decides how the cells compare. This definition has been widely adopted but is extended to arrays of differing shape, and non-numeric types and complex numbers (which were added later to SHARP but not supported in Grade), in different ways by various dialects.

Differing shapes

Ordering of arrays with different shapes can arise in Grade on non-simple arrays, either because they're nested or when the ordering is extended to boxes. Interval Index (assuming major cell search) may also allow arguments with differing cell shapes.

GNU APL and NARS2000 implement a shortlex order-like ordering, comparing first rank, then shape, then type, and finally element values in ravel order. By comparing elements only in the case of matching shapes, there's no question of how indices in differently-shaped arrays might correspond to each other.

Dyalog APL's total array ordering, introduced with version 17.0 in 2018, begins by comparing elements instead, in order to conform with lexicographic order as used in dictionaries. Two elements may be compared only if they have matching indices, ignoring leading zeros to allow a correspondence even if the arrays differ in rank. Elements are visited by (lexicographically) increasing index, and if an element is reached in one array that doesn't correspond to any element in the other array, then its array is ordered later, as if the empty spot contained a special "nothing" value that comes before any element. This can also be defined recursively, as a lexicographic comparison on major cells in equal-rank arrays, and when ranks differ by comparing the entire lesser-rank array with the major cells of the higher-rank array. The shape (possibly in addition to prototypes) is used to break ties when all elements match, which may happen if both arrays are empty or if one has the same shape as the other but with extra leading 1s.

J, which defined its ordering early on in 1996 (release 3.01), uses a mix of strategies. It first compares array types, then ranks, then elements after padding with fills (according to documentation; however, as of version 9.5 there are various differences from this definition when values equal or less than the fill are used).

Scalar types

Array ordering may also support simple scalars that aren't valid arguments to comparison functions, such as characters. Some languages, including GNU APL, TinyAPL, BQN, and Uiua, extend comparisons to non-numeric values, although they may retain some difference between comparison and array ordering of scalars.

Dyalog APL extended Grade to apply to simple character arrays in 1982. This extension had not been implemented by SHARP, as dyadic Grade was used instead. With total array ordering Dyalog extended further to allow comparisons between characters and numbers, as well as the special value ⎕null. Other simple scalars (namely namespaces, objects, and object representations) were excluded, because ordering them was considered "contentious but of little incremental benefit." However, the dfns workspace includes an APL model which is truly total, though it differs from the native implementation in ordering characters before numbers instead of the opposite.

Complex numbers

Complex numbers were added to SHARP APL in 1981 but not supported in comparison functions or Grade, "Because the complex numbers are not ordered". That is, complex numbers and other extensions of the reals don't belong to any ordered field: any ordering that remains the same after adding a constant could not be compatible with multiplication in the sense that the product of any two numbers greater than zero is greater than zero. NARS2000 doesn't order complex numbers, quaternions, and octonions for the same reason.

Languages including J, Dyalog APL, and GNU APL order complex numbers by real part and then imaginary part, producing an ordering that's compatible with the one on reals even if some error is added to the complex part (which is common in complex calculations where the final value is real, due to the high sensitivity of floating-point components around 0). Regarding the fact that this design doesn't conform to a mathematical ordered field, Dyalog's designers remark: "A TAO does not (and can not) claim to order the complex numbers and preserve arithmetic properties".

Documentation

• Dyalog APL
• GNU APL
• TinyAPL
• J
• BQN