Difference between revisions of "Total array ordering"

From APL Wiki
Jump to navigation Jump to search
m
(We don't know if this is the reason NARS2000 excludes them.)
 
(2 intermediate revisions by one other user 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.
 
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.
  
[[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 [[M. Kromberg|Morten 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.
+
[[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.
  
 
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 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]].
Line 9: Line 9:
 
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>
 
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. It should be noted that "complex numbers cannot be ordered if field (arithmetic) properties are to be preserved."<ref name=bfh/>
+
NARS2000's  excludes [[complex number]]s (including quaternions and octonions) from the ordering. It should be noted that 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 ==
 
== Documentation ==

Latest revision as of 20:55, 24 November 2020

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 functions. Traditionally ordering is defined only for simple arrays of the same shape and type, so TAO refers to the extension to nested or boxed arrays of arbitrary rank, shape, and type.

J has had such an ordering since 1996 (release 3.01). Dyalog APL added a total array ordering with version 17.0. Both of these are based on a lexicographic ordering.[1][2] GNU APL and NARS2000 also implement total ordering, but based on shortlex ordering instead, comparing first rank, then shape, then type, and finally value.

The name total array ordering is taken partly from the mathematical concept of a 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.

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 scalars other than nulls, numbers or characters (namely namespaces, objects, and object representations), because ordering those was considered "contentious but of little incremental benefit."[3] 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.[4]

NARS2000's excludes complex numbers (including quaternions and octonions) from the ordering. It should be noted that these numbers do not 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.[3]

Documentation

References

  1. Hui, R.. The TAO of J.
  2. Hui, R. and M. Kromberg. APL since 1978. ACM HOPL IV. 2020-06.
  3. 3.0 3.1 Brudzewsky, A., J. Foad, and R. Hui. TAO Axioms. 2018-02-02.
  4. Dfns workspace. le ― Total array ordering (TAO) comparison.


APL features [edit]
Built-ins Primitive functionPrimitive operatorQuad name
Array model ShapeRankDepthBoundIndex (Indexing) ∙ AxisRavelRavel orderElementScalarVectorMatrixSimple scalarSimple arrayNested arrayCellMajor cellSubarrayEmpty arrayPrototype
Data types Number (Boolean, Complex number) ∙ Character (String) ∙ BoxNamespace
Concepts and paradigms Leading axis theoryScalar extensionConformabilityScalar functionPervasionGlyphIdentity elementComplex floorTotal array ordering
Errors LIMIT ERRORRANK ERRORSYNTAX ERRORDOMAIN ERRORLENGTH ERRORINDEX ERRORVALUE ERROR