Grade

From APL Wiki
Revision as of 20:26, 17 February 2024 by Marshall (talk | contribs) (History)
Jump to navigation Jump to search

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.

History

In A Programming Language, Grade is referred to as the ordering of a vector and written   for vector   and index origin index origin  : 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 ⍋⍒ and index origin-dependent definition in APL\360. By 1968 it had been defined to grade along a particular axis, defaulting to the last;[1] however, this extension has often not been maintained in later APLs.

SHARP APL extended Grade to sort the major cells of its argument, and introduced the dyadic Grade functions,[2] following a suggestion by Howard Smith of IBM motivated by string sorting.[3] 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 extensions were widely adopted at the time, for example in the first versions of Dyalog APL.[4] 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

Documentation

Other

References

  1. ↑ IBM. Contributed Program Library: APL\360. 1968.
  2. ↑ Peter Wooster. "Extended Upgrade and Downgrade". SATN-35. 1980-09-15.
  3. ↑ Howard J. Smith. Sorting - a new/old problem at APL79.
  4. ↑ Stephen Taylor. "How we got here". Vector journal Volume 23 special supplement "Dyalog at 25". 2008-09.
APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic Conjugate ∙ Negate ∙ Signum ∙ Reciprocal ∙ Magnitude ∙ Exponential ∙ Natural Logarithm ∙ Floor ∙ Ceiling ∙ Factorial ∙ Not ∙ Pi Times ∙ Roll ∙ Type ∙ Imaginary ∙ Square Root ∙ Round
Dyadic Add ∙ Subtract ∙ Times ∙ Divide ∙ Residue ∙ Power ∙ Logarithm ∙ Minimum ∙ Maximum ∙ Binomial ∙ Comparison functions ∙ Boolean functions (And, Or, Nand, Nor) ∙ GCD ∙ LCM ∙ Circular ∙ Complex ∙ Root
Non-Scalar
Structural Shape ∙ Reshape ∙ Tally ∙ Depth ∙ Ravel ∙ Enlist ∙ Table ∙ Catenate ∙ Reverse ∙ Rotate ∙ Transpose ∙ Raze ∙ Mix ∙ Split ∙ Enclose ∙ Nest ∙ Cut (K) ∙ Pair ∙ Link ∙ Partitioned Enclose ∙ Partition
Selection First ∙ Pick ∙ Take ∙ Drop ∙ Unique ∙ Identity ∙ Stop ∙ Select ∙ Replicate ∙ Expand ∙ Set functions (Intersection ∙ Union ∙ Without) ∙ Bracket indexing ∙ Index ∙ Cartesian Product ∙ Sort
Selector Index generator ∙ Grade ∙ Index Of ∙ Interval Index ∙ Indices ∙ Deal ∙ Prefix and suffix vectors
Computational Match ∙ Not Match ∙ Membership ∙ Find ∙ Nub Sieve ∙ Encode ∙ Decode ∙ Matrix Inverse ∙ Matrix Divide ∙ Format ∙ Execute ∙ Materialise ∙ Range
Operators Monadic Each ∙ Commute ∙ Constant ∙ Replicate ∙ Expand ∙ Reduce ∙ Windowed Reduce ∙ Scan ∙ Outer Product ∙ Key ∙ I-Beam ∙ Spawn ∙ Function axis ∙ Identity (Null, Ident)
Dyadic Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator) ∙ Identity (Lev, Dex)
Quad names Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector
Retrieved from ‘https://aplwiki.com/index.php?title=Grade&oldid=10962’