2,954
edits
Key: Difference between revisions
Jump to navigation
Jump to search
History, and J and Kap documentation links
(Problems) |
(History, and J and Kap documentation links) |
||
| (3 intermediate revisions by one other user not shown) | |||
| Line 4: | Line 4: | ||
[[Monadic]]ally, Key will group identical [[major cell]]s 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: | [[Monadic]]ally, Key will group identical [[major cell]]s 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: | ||
< | <syntaxhighlight lang=apl> | ||
{⍺⍵}⌸'Mississippi' | {⍺⍵}⌸'Mississippi' | ||
┌─┬────────┐ | ┌─┬────────┐ | ||
| Line 15: | Line 15: | ||
│p│9 10 │ | │p│9 10 │ | ||
└─┴────────┘ | └─┴────────┘ | ||
</ | </syntaxhighlight> | ||
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: | 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: | ||
< | <syntaxhighlight lang=apl> | ||
'Mississippi'{⍺⍵}⌸'ABCDEFGHIJK' | 'Mississippi'{⍺⍵}⌸'ABCDEFGHIJK' | ||
┌─┬────┐ | ┌─┬────┐ | ||
| Line 30: | Line 30: | ||
│p│IJ │ | │p│IJ │ | ||
└─┴────┘ | └─┴────┘ | ||
</ | </syntaxhighlight> | ||
The monadic case, < | The monadic case, <syntaxhighlight lang=apl inline>f⌸Y</syntaxhighlight> is equivalent to <syntaxhighlight lang=apl inline>Y f⌸ ⍳≢Y</syntaxhighlight>. | ||
== Problems == | == Problems == | ||
=== Vocabulary === | === 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: | 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: | ||
< | <syntaxhighlight lang=apl> | ||
{⍺,≢⍵}⌸'TCCGCGGTGGCG' | {⍺,≢⍵}⌸'TCCGCGGTGGCG' | ||
T 2 | T 2 | ||
C 4 | C 4 | ||
G 6 | G 6 | ||
</ | </syntaxhighlight> | ||
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: | 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: | ||
< | <syntaxhighlight lang=apl> {⍺,¯1+≢⍵}⌸'ACGT','TCCGCGGTGGCG' | ||
A 0 | A 0 | ||
C 4 | C 4 | ||
G 6 | G 6 | ||
T 2 | T 2 | ||
</ | </syntaxhighlight> | ||
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: | 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: | ||
< | <syntaxhighlight lang=apl> | ||
¯1+{≢⍵}⌸'ACGT','TCCGCGGTGGCG' | ¯1+{≢⍵}⌸'ACGT','TCCGCGGTGGCG' | ||
0 4 6 2 | 0 4 6 2 | ||
</ | </syntaxhighlight> | ||
=== Computing the unique === | === 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: | 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: | ||
< | <syntaxhighlight lang=apl> | ||
⊃⍒{≢⍵}⌸'TCCGCGGTGGCG' | ⊃⍒{≢⍵}⌸'TCCGCGGTGGCG' | ||
3 | 3 | ||
</ | </syntaxhighlight> | ||
Notice that 3 is the index in the unique set of letters, and so it is tempting to write: | Notice that 3 is the index in the unique set of letters, and so it is tempting to write: | ||
< | <syntaxhighlight lang=apl> | ||
{(⊃⍒{≢⍵}⌸⍵)⌷∪⍵}'TCCGCGGTGGCG' | {(⊃⍒{≢⍵}⌸⍵)⌷∪⍵}'TCCGCGGTGGCG' | ||
G | G | ||
</ | </syntaxhighlight> | ||
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: | 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: | ||
< | <syntaxhighlight lang=apl> | ||
(keys counts)←,⌿{⍺,≢⍵}⌸'TCCGCGGTGGCG' | (keys counts)←,⌿{⍺,≢⍵}⌸'TCCGCGGTGGCG' | ||
keys⌷⍨⊃⍒counts | keys⌷⍨⊃⍒counts | ||
G | G | ||
</ | </syntaxhighlight> | ||
Unfortunately, this can introduce a different inefficiency, in that the result of Key's operand can end up being a [[heterogeneous array]] (containing multiple [[datatype]]s), 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: | Unfortunately, this can introduce a different inefficiency, in that the result of Key's operand can end up being a [[heterogeneous array]] (containing multiple [[datatype]]s), 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: | ||
< | <syntaxhighlight lang=apl> | ||
data←'TCCGCGGTGGCG' | data←'TCCGCGGTGGCG' | ||
keys←0⌿data | keys←0⌿data | ||
| Line 79: | Line 79: | ||
keys⌷⍨⊃⍒counts | keys⌷⍨⊃⍒counts | ||
G | G | ||
</ | </syntaxhighlight> | ||
If there are a large number of unique values, the repeated updating of the accumulating < | If there are a large number of unique values, the repeated updating of the accumulating <syntaxhighlight lang=apl inline>keys</syntaxhighlight> 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]].<ref>[[Roger Hui]]. [https://code.jsoftware.com/wiki/Essays/Key Essays/Key]. "History".</ref> | |||
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 <syntaxhighlight lang=j inline>/..</syntaxhighlight> 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 <syntaxhighlight lang=apl inline>⌸</syntaxhighlight> that functions like Dyalog's <syntaxhighlight lang=apl inline>{⍺⍵}⌸</syntaxhighlight>. [[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 [[K|K3]]'s [[Group (K)|Group]], except the list of keys is specified explicitly rather than being taken from the unique values of the argument. | |||
== External links == | == External links == | ||
| Line 87: | Line 94: | ||
=== Documentation === | === Documentation === | ||
* [https://help.dyalog.com/latest/Content/Language/Primitive%20Operators/Key.htm Dyalog] | * [https://help.dyalog.com/latest/Content/Language/Primitive%20Operators/Key.htm Dyalog] | ||
* [https://kapdemo.dhsdevelopments.com/reference.html#_key Kap] (a primitive function variation) | |||
* J [https://code.jsoftware.com/wiki/Vocabulary/slashdot#dyadic NuVoc] (<syntaxhighlight lang=j inline>/.</syntaxhighlight> and <syntaxhighlight lang=j inline>/..</syntaxhighlight>), [https://code.jsoftware.com/wiki/Vocabulary/slashdot#dyadic Dictionary] (<syntaxhighlight lang=j inline>/.</syntaxhighlight> only) | |||
{{APL built-ins}}[[Category:Primitive operators]] | {{APL built-ins}}[[Category:Primitive operators]] | ||