Total array ordering: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
mNo edit summary
(Most content moved to Array ordering, see talk page)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
In APL, a '''total array ordering''', or '''TAO''', is an [[ordering]] on all arrays which is used primarily by [[Grade]] and [[Interval Index]], but optionally also by the [[comparison function]]s. Traditionally ordering is defined only for [[simple]] arrays of the same [[shape]] and [[type]], so ''TAO'' refers to the extension to [[Nested array|nested]] or [[box]]ed arrays of arbitrary [[rank]], shape, and type.
:'''''TAO''' links here. For the chat room, see The [[APL Orchard]].''


[[J]] has had such an ordering since 1996 (release 3.01). [[Dyalog APL]] added a total array ordering with [[Dyalog APL 17.0|version 17.0]]. Both of these are based on a [[wikipedia:lexicographic order|lexicographic order]]ing.<ref>[[Roger Hui|Hui, R.]]. [https://code.jsoftware.com/wiki/Essays/The_TAO_of_J The TAO of J].</ref><ref>Hui, R. and [[Morten Kromberg|M. Kromberg]]. [https://dl.acm.org/doi/abs/10.1145/3386319 ''APL since 1978'']. ACM HOPL IV. 2020-06.</ref> [[GNU APL]] and [[NARS2000]] also implement total ordering, but based on [[wikipedia:shortlex order|shortlex order]]ing instead, comparing first [[rank]], then [[shape]], then [[type]], and finally value.
'''Total array ordering''', or '''TAO''', is the [[array ordering]] defined by [[Dyalog APL]] in [[Dyalog APL 17.0|version 17.0]] (2018), which pertains to arrays of nulls, [[number]]s, and [[character]]s in any arrangement. It extends the concept of [[wikipedia:lexicographic order|lexicographic order]] to higher ranks. The name ''total array ordering'' is taken partly from the mathematical concept of a [[wikipedia:total order|total order]], which must order any two values, with values ordering equally only if they are identical. This concept is transferred to APL by specifying that arrays should only order equally if they [[match]]. The name has also been applied retroactively to [[J]]'s array ordering, which has different rules from Dyalog,<ref>[[Roger Hui|Hui, R.]]. [https://code.jsoftware.com/wiki/Essays/The_TAO_of_J The TAO of J].</ref> and is used in [[TinyAPL]], which bases its ordering on Dyalog's but treats scalars differently.


The name ''total array ordering'' is taken partly from the mathematical concept of a [[wikipedia:total order|total order]], which must order any two elements, with elements ordering equally only if they are identical. This concept is transferred to APL by specifying that arrays should only order equally if they [[match]].
The extensions made in Dyalog 17.0 are support for [[complex number]]s and the special value <syntaxhighlight lang=apl inline>⎕null</syntaxhighlight>, the ability to compare values of different types, and the extension to differing shapes and ranks. There is no support for [[simple scalar]]s other than nulls, [[number]]s or [[character]]s (namely [[namespace]]s, [[object]]s, and [[object representation]]s), because ordering those was considered "contentious but of little incremental benefit."<ref name=bfh>[[Adám Brudzewsky|Brudzewsky, A.]], [[Jay Foad|J. Foad]], and R. Hui. [https://www.jsoftware.com/papers/TAOaxioms.htm TAO Axioms]. 2018-02-02.</ref> [[Roger Hui]] has argued that these scalars are not truly arrays, and are not in the scope of a total array ordering. 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.<ref>[[Dfns workspace]]. [http://dfns.dyalog.com/n_le.htm <syntaxhighlight lang=apl inline>le</syntaxhighlight>] ― Total array ordering (TAO) comparison.</ref>
== Exceptions from the ordering ==
Some dialects do not implement a true ''total'' order because they support arrays without defining an order for them.
 
Dyalog APL excludes [[simple scalar]]s other than nulls, [[number]]s or [[character]]s (namely [[namespace]]s, [[object]]s, and [[object representation]]s), because ordering those was considered "contentious but of little incremental benefit."<ref name=bfh>[[Adám Brudzewsky|Brudzewsky, A.]], [[Jay Foad|J. Foad]], and R. Hui. [https://www.jsoftware.com/papers/TAOaxioms.htm TAO Axioms]. 2018-02-02.</ref> [[Roger Hui]] has argued that these scalars are not truly arrays, and are not in the scope of a total array ordering. 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.<ref>[[Dfns workspace]]. [http://dfns.dyalog.com/n_le.htm <source lang=apl inline>le</source>] ― Total array ordering (TAO) comparison.</ref>
 
NARS2000's  excludes [[complex number]]s (including quaternions and octonions) from the ordering, because these numbers do not belong to any [[wikipedia:ordered field|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.<ref name=bfh/>
 
== Documentation ==
* [https://help.dyalog.com/latest/#Language/Primitive%20Functions/Grade%20Up%20Monadic.htm Dyalog APL]
* [https://code.jsoftware.com/wiki/Vocabulary/slashco#Details J]
* [https://www.gnu.org/software/apl/apl.html#Section-3_002e4 GNU APL]


== References ==
== References ==

Latest revision as of 15:40, 17 October 2024

TAO links here. For the chat room, see The APL Orchard.

Total array ordering, or TAO, is the array ordering defined by Dyalog APL in version 17.0 (2018), which pertains to arrays of nulls, numbers, and characters in any arrangement. It extends the concept of lexicographic order to higher ranks. The name total array ordering is taken partly from the mathematical concept of a total order, which must order any two values, with values ordering equally only if they are identical. This concept is transferred to APL by specifying that arrays should only order equally if they match. The name has also been applied retroactively to J's array ordering, which has different rules from Dyalog,[1] and is used in TinyAPL, which bases its ordering on Dyalog's but treats scalars differently.

The extensions made in Dyalog 17.0 are support for complex numbers and the special value ⎕null, the ability to compare values of different types, and the extension to differing shapes and ranks. There is no support for simple scalars other than nulls, numbers or characters (namely namespaces, objects, and object representations), because ordering those was considered "contentious but of little incremental benefit."[2] Roger Hui has argued that these scalars are not truly arrays, and are not in the scope of a total array ordering. 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.[3]

References

  1. ↑ Hui, R.. The TAO of J.
  2. ↑ Brudzewsky, A., J. Foad, and R. Hui. TAO Axioms. 2018-02-02.
  3. ↑ Dfns workspace. le ― Total array ordering (TAO) comparison.


APL features [edit]
Built-ins Primitives (functions, operators) ∙ Quad name
Array model Shape ∙ Rank ∙ Depth ∙ Bound ∙ Index (Indexing) ∙ Axis ∙ Ravel ∙ Ravel order ∙ Element ∙ Scalar ∙ Vector ∙ Matrix ∙ Simple scalar ∙ Simple array ∙ Nested array ∙ Cell ∙ Major cell ∙ Subarray ∙ Empty array ∙ Prototype
Data types Number (Boolean, Complex number) ∙ Character (String) ∙ Box ∙ Namespace ∙ Function array
Concepts and paradigms Conformability (Scalar extension, Leading axis agreement) ∙ Scalar function (Pervasion) ∙ Identity element ∙ Complex floor ∙ Array ordering (Total) ∙ Tacit programming (Function composition, Close composition) ∙ Glyph ∙ Leading axis theory ∙ Major cell search ∙ First-class function
Errors LIMIT ERROR ∙ RANK ERROR ∙ SYNTAX ERROR ∙ DOMAIN ERROR ∙ LENGTH ERROR ∙ INDEX ERROR ∙ VALUE ERROR ∙ EVOLUTION ERROR
Retrieved from ‘https://aplwiki.com/index.php?title=Total_array_ordering&oldid=11655’