Grade: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
m (Text replacement - "</source>" to "</syntaxhighlight>")
(7 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]] <source lang=apl inline>⍋</source> is called '''Grade Up''' and gives the ascending sort order, while <source lang=apl inline>⍒</source> is called '''Grade Down''' and gives the descending sort order.
{{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 5: Line 5:
[[Monadic]] Grade returns the sorting order of the major cells of the [[argument]]. [[Indexing]] into the original argument gives the sorted array; indexing into another array gives the result commonly known as '''Sort By'''.
[[Monadic]] Grade returns the sorting order of the major cells of the [[argument]]. [[Indexing]] into the original argument gives the sorted array; indexing into another array gives the result commonly known as '''Sort By'''.


<source lang=apl>
<syntaxhighlight lang=apl>
       ⎕←A←↑'foo' 'bar' 'baz'  ⍝ A character matrix
       ⎕←A←↑'foo' 'bar' 'baz'  ⍝ A character matrix
foo
foo
Line 27: Line 27:
bar
bar
foo
foo
</source>
</syntaxhighlight>


Grade usually 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.


<source lang=apl>
<syntaxhighlight lang=apl>
       S←6 10 10 3 2 15 ⋄ T←S,¨⍳6
       S←6 10 10 3 2 15 ⋄ T←S,¨⍳6
       ⍝ Note that the order of two 10s are preserved in both cases
       ⍝ Note that the order of two 10s are preserved in both cases
Line 46: Line 46:
│          │└────┴────┴────┴───┴───┴───┘│
│          │└────┴────┴────┴───┴───┴───┘│
└───────────┴────────────────────────────┘
└───────────┴────────────────────────────┘
</source>
</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).


<source lang=apl>
<syntaxhighlight lang=apl>
       ⎕←A←(1(⍪2 3)) (1 3) (⊂0 1 2)
       ⎕←A←(1(⍪2 3)) (1 3) (⊂0 1 2)
┌─────┬───┬───────┐
┌─────┬───┬───────┐
Line 60: Line 60:
       ⍋A
       ⍋A
3 1 2
3 1 2
</source>{{Works in|[[Dyalog APL]]}}
</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, <source lang=apl inline>X⍋Y</source> equals <source lang=apl inline>⍋X⍳Y</source>, and same for <source lang=apl inline>⍒</source>.
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>.


<source lang=apl>
<syntaxhighlight lang=apl>
       ⎕A⍋'ZAM,.BIA'  ⍝ Alphabetical order, garbage goes last
       ⎕A⍋'ZAM,.BIA'  ⍝ Alphabetical order, garbage goes last
2 8 6 7 3 1 4 5
2 8 6 7 3 1 4 5
       (⌽⎕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
</source>
</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.


<source lang=apl>
<syntaxhighlight lang=apl>
       Data
       Data
ABLE
ABLE
Line 97: Line 97:
ACES
ACES
ACRE
ACRE
</source>
</syntaxhighlight>


[[J]] does not implement dyadic grade, but provides '''Sort By''' as the dyadic counterparts of <source lang=j inline>/:</source> and <source lang=j inline>\:</source> instead.
[[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.


== External links ==
== External links ==
=== Lessons ===
* [https://chat.stackexchange.com/transcript/52405?m=41581276#41581276 APL Cultivation]


=== Documentation ===
=== Documentation ===
Line 112: Line 108:
* APLX [http://microapl.com/apl_help/ch_020_020_630.htm Grade Up], [http://microapl.com/apl_help/ch_020_020_640.htm Grade Down]
* APLX [http://microapl.com/apl_help/ch_020_020_630.htm Grade Up], [http://microapl.com/apl_help/ch_020_020_640.htm Grade Down]
* J Dictionary [https://www.jsoftware.com/help/dictionary/d422.htm Grade Up], [https://www.jsoftware.com/help/dictionary/d432.htm Grade Down], NuVoc [https://code.jsoftware.com/wiki/Vocabulary/slashco Grade]
* J Dictionary [https://www.jsoftware.com/help/dictionary/d422.htm Grade Up], [https://www.jsoftware.com/help/dictionary/d432.htm Grade Down], NuVoc [https://code.jsoftware.com/wiki/Vocabulary/slashco Grade]
* [https://mlochbaum.github.io/BQN/doc/order.html#grade BQN]


=== Libraries ===
=== Other ===
 
* [https://github.com/abrudz/Sort abrudz/Sort]: Examples of sorting variations ([[Atomic vector|Classic]], [[wikipedia:Natural_sort_order|Natural]], Danish, Finnish, German) using dyadic grade


* [https://chat.stackexchange.com/transcript/52405?m=41581276#41581276 APL Cultivation] lesson
* [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
{{APL built-ins}}[[Category:Primitive functions]]
{{APL built-ins}}[[Category:Primitive functions]]

Revision as of 22:03, 10 September 2022

Grade (, ) is a pair of ambivalent primitive functions related to sorting. Instead of sorting the given array directly, Grade returns a permutation vector whose length equals the number of major cells, so that indexing into the argument gives the sorted array. The glyph is called Grade Up and gives the ascending sort order, while is called Grade Down and gives the descending sort order.

Monadic form

Monadic Grade returns the sorting order of the major cells of the argument. Indexing into the original argument gives the sorted array; indexing into another array gives the result commonly known as Sort By.

      ⎕←A←↑'foo' 'bar' 'baz'  ⍝ A character matrix
foo
bar
baz
      ⍋A  ⍝ Grade up its rows
2 3 1
      A[⍋A;]  ⍝ Move the rows to sorted order (ascending)
bar
baz
foo
      ⍒A  ⍝ Grade down its rows
1 3 2
      A[⍒A;]  ⍝ Move the rows to sorted order (descending)
foo
baz
bar
      B←15 10 5
      A[⍋B;]  ⍝ Sort A by B
baz
bar
foo

Grade performs 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.

      S←6 10 10 3 2 15 ⋄ T←S,¨⍳6
      ⍝ Note that the order of two 10s are preserved in both cases
      (⍋S) (T[⍋S])
┌───────────┬────────────────────────────┐
│5 4 1 2 3 6│┌───┬───┬───┬────┬────┬────┐│
│           ││2 5│3 4│6 1│10 2│10 3│15 6││
│           │└───┴───┴───┴────┴────┴────┘│
└───────────┴────────────────────────────┘
      (⍒S) (T[⍒S])
┌───────────┬────────────────────────────┐
│6 2 3 1 4 5│┌────┬────┬────┬───┬───┬───┐│
│           ││15 6│10 2│10 3│6 1│3 4│2 5││
│           │└────┴────┴────┴───┴───┴───┘│
└───────────┴────────────────────────────┘

Dyalog APL supports total array ordering when comparing 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).

      ⎕←A←(1(⍪2 3)) (1 3) (⊂0 1 2)
┌─────┬───┬───────┐
│┌─┬─┐│1 3│┌─────┐│
││1│2││   ││0 1 2││
││ │3││   │└─────┘│
│└─┴─┘│   │       │
└─────┴───┴───────┘
      ⍋A
3 1 2
Works in: Dyalog APL

Dyadic form

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, X⍋Y equals ⍋X⍳Y, and same for .

      ⎕A⍋'ZAM,.BIA'  ⍝ Alphabetical order, garbage goes last
2 8 6 7 3 1 4 5
      (⌽⎕A)⍋'ZAM,.BIA'  ⍝ Reverse alphabetical order, garbage still goes last
1 3 7 6 2 8 4 5

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.

      Data
ABLE
aBLE
ACRE
ABEL
aBEL
ACES
      Coll
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
      Coll⍋Data
4 5 1 2 6 3
      Data[Coll⍋Data;]
ABEL
aBEL
ABLE
aBLE
ACES
ACRE

J does not implement dyadic grade, but provides Sort By as the dyadic counterparts of /: and \: instead.

External links

Documentation

Other

APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic ConjugateNegateSignumReciprocalMagnitudeExponentialNatural LogarithmFloorCeilingFactorialNotPi TimesRollTypeImaginarySquare Root
Dyadic AddSubtractTimesDivideResiduePowerLogarithmMinimumMaximumBinomialComparison functionsBoolean functions (And, Or, Nand, Nor) ∙ GCDLCMCircularComplexRoot
Non-Scalar
Structural ShapeReshapeTallyDepthRavelEnlistTableCatenateReverseRotateTransposeRazeMixSplitEncloseNestCut (K)PairLinkPartitioned EnclosePartition
Selection FirstPickTakeDropUniqueIdentityStopSelectReplicateExpandSet functions (IntersectionUnionWithout) ∙ Bracket indexingIndexCartesian ProductSort
Selector Index generatorGradeIndex OfInterval IndexIndicesDealPrefix and suffix vectors
Computational MatchNot MatchMembershipFindNub SieveEncodeDecodeMatrix InverseMatrix DivideFormatExecuteMaterialiseRange
Operators Monadic EachCommuteConstantReplicateExpandReduceWindowed ReduceScanOuter ProductKeyI-BeamSpawnFunction axis
Dyadic BindCompositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner ProductDeterminantPowerAtUnderRankDepthVariantStencilCutDirect definition (operator)
Quad names Index originComparison toleranceMigration levelAtomic vector