2,954
edits
Grade: Difference between revisions
Jump to navigation
Jump to search
m
→History: Clarify
m (Text replacement - "<source" to "<syntaxhighlight") |
m (→History: Clarify) |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Built-ins|Grade|⍋|⍒}} is a pair of [[ambivalent]] [[primitive function|primitive functions]] related to [[wikipedia:sorting#sorting information or data|sorting]]. Instead of sorting the given array directly, Grade returns a [[permutation]] [[vector]] whose length equals the number of [[major cell|major cells]], so that [[indexing]] into the argument gives the sorted array. The [[glyph]] <syntaxhighlight lang=apl inline>⍋</ | {{Built-ins|Grade|⍋|⍒}} is a pair of [[ambivalent]] [[primitive function|primitive functions]] related to [[wikipedia:sorting#sorting information or data|sorting]]. Instead of sorting the given array directly, Grade returns a [[permutation]] [[vector]] whose length equals the number of [[major cell|major cells]], so that [[indexing]] into the argument gives the sorted array. The [[glyph]] <syntaxhighlight lang=apl inline>⍋</syntaxhighlight> is called '''Grade Up''' and gives the ascending sort order, while <syntaxhighlight lang=apl inline>⍒</syntaxhighlight> is called '''Grade Down''' and gives the descending sort order. | ||
== Monadic form == | == Monadic form == | ||
| Line 27: | Line 27: | ||
bar | bar | ||
foo | foo | ||
</ | </syntaxhighlight> | ||
Grade performs [[wikipedia:sorting algorithm#stability|stable sorting]], so that the indices of the repeated major cells are sorted by the order of appearance. Because of this, Grade Down produces the reverse of Grade Up only if all the major cells are unique. | Grade performs [[wikipedia:sorting algorithm#stability|stable sorting]], so that the indices of the repeated major cells are sorted by the order of appearance. Because of this, Grade Down produces the reverse of Grade Up only if all the major cells are unique. | ||
| Line 46: | Line 46: | ||
│ │└────┴────┴────┴───┴───┴───┘│ | │ │└────┴────┴────┴───┴───┴───┘│ | ||
└───────────┴────────────────────────────┘ | └───────────┴────────────────────────────┘ | ||
</ | </syntaxhighlight> | ||
[[Dyalog APL]] supports [[total array ordering]] when comparing [[nested array|nested arrays]] of possibly different [[shape]] and [[type]]. Grade is the only built-in function which can perform comparisons between arbitrary arrays of previously unknown order ([[Interval Index]] requires the left argument to be sorted beforehand). | [[Dyalog APL]] supports [[total array ordering]] when comparing [[nested array|nested arrays]] of possibly different [[shape]] and [[type]]. Grade is the only built-in function which can perform comparisons between arbitrary arrays of previously unknown order ([[Interval Index]] requires the left argument to be sorted beforehand). | ||
| Line 60: | Line 60: | ||
⍋A | ⍋A | ||
3 1 2 | 3 1 2 | ||
</ | </syntaxhighlight>{{Works in|[[Dyalog APL]]}} | ||
== Dyadic form == | == Dyadic form == | ||
| Line 66: | Line 66: | ||
[[Dyadic]] Grade is limited to [[simple]] [[character]] array arguments. The left argument specifies the collation order to use when sorting the right argument. | [[Dyadic]] Grade is limited to [[simple]] [[character]] array arguments. The left argument specifies the collation order to use when sorting the right argument. | ||
If the left argument is a [[vector]], the sorting order is simply the order of appearance in the left argument. In other words, <syntaxhighlight lang=apl inline>X⍋Y</ | If the left argument is a [[vector]], the sorting order is simply the order of appearance in the left argument. In other words, <syntaxhighlight lang=apl inline>X⍋Y</syntaxhighlight> equals <syntaxhighlight lang=apl inline>⍋X⍳Y</syntaxhighlight>, and same for <syntaxhighlight lang=apl inline>⍒</syntaxhighlight>. | ||
<syntaxhighlight lang=apl> | <syntaxhighlight lang=apl> | ||
| Line 73: | Line 73: | ||
(⌽⎕A)⍋'ZAM,.BIA' ⍝ Reverse alphabetical order, garbage still goes last | (⌽⎕A)⍋'ZAM,.BIA' ⍝ Reverse alphabetical order, garbage still goes last | ||
1 3 7 6 2 8 4 5 | 1 3 7 6 2 8 4 5 | ||
</ | </syntaxhighlight> | ||
If the left argument is a higher-[[rank]] array, sorting is done in multiple stages. The last [[axis]] of X takes highest precedence, then the next-to-last, and so on, giving ties to all characters that appear at the same index over the current axis. A notable application is case-insensitive sorting. | If the left argument is a higher-[[rank]] array, sorting is done in multiple stages. The last [[axis]] of X takes highest precedence, then the next-to-last, and so on, giving ties to all characters that appear at the same index over the current axis. A notable application is case-insensitive sorting. | ||
| Line 97: | Line 97: | ||
ACES | ACES | ||
ACRE | ACRE | ||
</ | </syntaxhighlight> | ||
[[J]] does not implement dyadic grade, but provides '''Sort By''' as the dyadic counterparts of <syntaxhighlight lang=j inline>/:</ | [[J]] does not implement dyadic grade, but provides '''Sort By''' as the dyadic counterparts of <syntaxhighlight lang=j inline>/:</syntaxhighlight> and <syntaxhighlight lang=j inline>\:</syntaxhighlight> instead. | ||
== History == | |||
In [[A Programming Language]], Grade is referred to as the ordering of a vector and written <math>\theta_j/x</math> for vector <math>x</math> and index origin [[index origin]] <math>j</math>: a special use of the slash that otherwise indicates [[Compress]]. The requirement that indices for equal elements should retain their indices (stable sorting) is mentioned explicitly. | |||
Grade up and down were defined with the standard glyphs <syntaxhighlight lang=apl inline>⍋⍒</syntaxhighlight> and [[index origin]]-dependent definition in [[APL\360]]. By 1968 it had been defined to grade along a particular [[function axis|axis]], defaulting to the last;<ref>[[IBM]]. [http://www.softwarepreservation.org/projects/apl/Manuals/APL360CONTRIBUTEDPROGRAMLIBRARY/view Contributed Program Library: APL\360]. 1968.</ref> however, this extension has often not been maintained in later APLs. | |||
In 1980 [[SHARP APL]] extended Grade to sort the [[major cell]]s of its argument, and introduced the dyadic Grade functions,<ref>Peter Wooster. "Extended Upgrade and Downgrade". SATN-35. 1980-09-15.</ref> following a suggestion by Howard Smith of [[IBM]] motivated by string sorting.<ref>Howard J. Smith. [https://dl.acm.org/doi/10.1145/800136.804449 Sorting - a new/old problem] at [[APL79]].</ref> While sorting cells is consistent with [[leading axis theory]], it predates the beginning of this model's development in 1982. The extension to monadic Grade is incompatible with APL\360's definition of grading along an axis. Both SHARP extensions were widely adopted at the time, for example in the first versions of [[Dyalog APL]].<ref>Stephen Taylor. [http://archive.vector.org.uk/art10013790 "How we got here"]. [[Vector journal]] Volume 23 special supplement "Dyalog at 25". 2008-09.</ref> Newer dialects such as [[Kap]] often don't implement dyadic Grade (which was also left out of [[J]] in favor of [[Sort by]]). | |||
== External links == | == External links == | ||
| Line 115: | Line 123: | ||
* [https://www.dyalog.com/blog/2018/04/dyadic-grade/ Dyadic Grade] by [[Roger Hui]], Dyalog Blog | * [https://www.dyalog.com/blog/2018/04/dyadic-grade/ Dyadic Grade] by [[Roger Hui]], Dyalog Blog | ||
* [https://github.com/abrudz/Sort abrudz/Sort] library: Examples of sorting variations ([[Atomic vector|Classic]], [[wikipedia:Natural_sort_order|Natural]], Danish, Finnish, German) using dyadic grade | * [https://github.com/abrudz/Sort abrudz/Sort] library: Examples of sorting variations ([[Atomic vector|Classic]], [[wikipedia:Natural_sort_order|Natural]], Danish, Finnish, German) using dyadic grade | ||
== References == | |||
<references/> | |||
{{APL built-ins}}[[Category:Primitive functions]] | {{APL built-ins}}[[Category:Primitive functions]] | ||