Key

From APL Wiki
Jump to navigation Jump to search
⌸

Key (⌸) is a primitive monadic operator which takes a dyadic function operand where specified keys group the indices or major cells of an argument. It was introduced in Dyalog APL version 14.0 and is commonly compared to SQL's GROUP BY statement.

Description

Monadically, Key will group identical major cells together and applies the function operand once for each unique major cell. The function is applied with the unique major cell as left argument, while the right argument is the indices of major cells that match it: 

      {⍺⍵}⌸'Mississippi'
┌─┬────────┐
│M│1       │
├─┼────────┤
│i│2 5 8 11│
├─┼────────┤
│s│3 4 6 7 │
├─┼────────┤
│p│9 10    │
└─┴────────┘

In the dyadic case, Key applies the function to collections of major cells from the right argument corresponding to unique elements of the left argument: 

      'Mississippi'{⍺⍵}⌸'ABCDEFGHIJK' 
┌─┬────┐
│M│A   │
├─┼────┤
│i│BEHK│
├─┼────┤
│s│CDFG│
├─┼────┤
│p│IJ  │
└─┴────┘

The monadic case, f⌸Y is equivalent to Y f⌸ ⍳≢Y.

Problems

Vocabulary

A common problem with Key is the inability to control the order of the result (as Key will use the order of appearance) and the "vocabulary" (as Key will never include information for a major cell that doesn't occur). For example, here we want to count occurrences of the letters A, C, G, T: 

      {⍺,≢⍵}⌸'TCCGCGGTGGCG'
T 2
C 4
G 6

Since A is entirely missing in the argument, it isn't mentioned in the result either. Likewise, the result is mis-ordered due to G and T appearing before the first C. A common solution is to inject the vocabulary before the actual data, and then decrement from the counts: 

      {⍺,¯1+≢⍵}⌸'ACGT','TCCGCGGTGGCG'
A 0
C 4
G 6
T 2

Now that the meaning of each count is known, the operand's left argument can be ignored, and the decrementing can be factored out from the operand: 

      ¯1+{≢⍵}⌸'ACGT','TCCGCGGTGGCG'
0 4 6 2

Computing the unique

Key computes the set of unique major cells. Often, this collection is needed separately from the occurrence information, but can be hard to extract. For example, to get the most frequently occurring letter: 

      ⊃⍒{≢⍵}⌸'TCCGCGGTGGCG'
3

Notice that 3 is the index in the unique set of letters, and so it is tempting to write: 

      {(⊃⍒{≢⍵}⌸⍵)⌷∪⍵}'TCCGCGGTGGCG'
G

However, while this code works, it is inefficient in that the unique is computed twice. This can be avoided by letting Key return the unique and using that: 

      (keys counts)←,⌿{⍺,≢⍵}⌸'TCCGCGGTGGCG'
      keys⌷⍨⊃⍒counts
G

Unfortunately, this can introduce a different inefficiency, in that the result of Key's operand can end up being a heterogeneous array (containing multiple datatypes), and these are stored as pointer arrays, consuming memory for one pointer per element, and forcing "pointer chasing" when addressing the data. A possible work-around is to collect the unique keys separately from the result of counts: 

      data←'TCCGCGGTGGCG'
      keys←0⌿data
      counts←{keys⍪←⍺ ⋄ ≢⍵}⌸data
      keys⌷⍨⊃⍒counts
G

If there are a large number of unique values, the repeated updating of the accumulating keys variable can be an issue in itself.

History

A key operator was first defined in J by 1990. J's implementer Roger Hui had written a J model taking a monadic function operand and two arguments in January following a discussion at I.P. Sharp Associates; he mentioned that such an operator had been proposed in the past by himself as well as Joey Tuttle and Bob Bernecky.[1]

Hui also implemented the operator in Dyalog APL 14.0, released in 2014. This version added the left argument to the operand function call based on experience with J, and also defined the monadic case, which in J had been defined as Oblique, calling the function on diagonals of an argument matrix. This definition was adopted by Dyalog-like dialects including ngn/apl, dzaima/APL (with changes), and April. In 2023, Henry Rich added a new key primitive /.. to J that also passes the unique value as the left argument (however, calling the derived function monadically was not defined).

Other variations on Key have been implemented. Since 2023 Kap defines a primitive function ⌸ that functions like Dyalog's {⍺⍵}⌸. Dyalog APL Vision defines an extension to Key when the operand is an array. The operand defines a vocabulary, so that result elements correspond to cells of the operand, and these elements contain either a list of indices where that value was found (if monadic), or right argument cells corresponding to positions where it was found in the left argument (if dyadic). The monadic form is similar to K3's Group, except the list of keys is specified explicitly rather than being taken from the unique values of the argument.

External links

Lessons

Documentation


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
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
Dyadic Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator)
Quad names Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector
  1. ↑ Roger Hui. Essays/Key. "History".
Retrieved from ‘https://aplwiki.com/index.php?title=Key&oldid=11433’