Essays/Key

From J Wiki
Jump to: navigation, search

/. key has a concise definition in the dictionary

x u/.y ↔ (=x) u@# y , that is, items of x specify keys for corresponding items of y
and u is applied to each collection of y having identical keys.

that belies its usefulness. We present some of its uses.


Elementary Examples

   ] x=: 20 ?.@$ 5
1 0 4 2 4 4 0 2 0 4 1 3 3 3 1 2 3 0 0 2
   ] y=: 20 ?.@$ 10
6 5 9 2 4 9 0 7 0 4 6 8 3 8 1 2 8 0 0 2

   x </. y
┌─────┬─────────┬───────┬───────┬───────┐
│6 6 1│5 0 0 0 0│9 4 9 4│2 7 2 2│8 3 8 8│
└─────┴─────────┴───────┴───────┴───────┘
   x +//. y
13 5 26 13 27

   avg=: +/ % #
   x avg/. y
4.33333 1 6.5 3.25 6.75

   ] names=: 'Ken';'Roger';'Arthur';'Arthur';'Ken';'Arthur'
┌───┬─────┬──────┬──────┬───┬──────┐
│Ken│Roger│Arthur│Arthur│Ken│Arthur│
└───┴─────┴──────┴──────┴───┴──────┘
   ] numbers=: 6 2 ?.@$ 100
46 55
79 52
54 39
60 57
60 94
46 78
   names </. numbers
┌─────┬─────┬─────┐
│46 55│79 52│54 39│
│60 94│     │60 57│
│     │     │46 78│
└─────┴─────┴─────┘
   names +//. numbers
106 149
 79  52
160 174
   names avg/. numbers
     53 74.5
     79   52
53.3333   58

Nub

{./.~ y computes the nub of y .

   ] y=: 20 ?.@$ 10
6 5 9 2 4 9 0 7 0 4 6 8 3 8 1 2 8 0 0 2
   {./.~ y
6 5 9 2 4 0 7 8 3 1
   ~. y
6 5 9 2 4 0 7 8 3 1

Nub Count

#/.~ y computes the nub count, the number of occurrences of each item of the nub.

   #/.~ y
2 1 2 3 2 4 1 3 1 1
   +/ y =/&(<"_1) ~. y
2 1 2 3 2 4 1 3 1 1
   +/"1 = y
2 1 2 3 2 4 1 3 1 1

Self-Classify

(</. i.@#) y are indices where each item of the nub occurs.

   y ,: i.#y
6 5 9 2 4 9 0 7 0 4  6  8  3  8  1  2  8  0  0  2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
   (</. i.@#) y
┌────┬─┬───┬───────┬───┬─────────┬─┬────────┬──┬──┐
│0 10│1│2 5│3 15 19│4 9│6 8 17 18│7│11 13 16│12│14│
└────┴─┴───┴───────┴───┴─────────┴─┴────────┴──┴──┘

Unique

Computations on unique items (those that occur exactly once).

   y
6 5 9 2 4 9 0 7 0 4 6 8 3 8 1 2 8 0 0 2
   ((1=#/.~) # ({./. i.@#)) y   NB. indices of unique items
1 7 12 14
   ((1=#/.~) # ~.) y            NB. unique items
5 7 3 1

   usieve=: i.~ = i:~           NB. unique sieve
   usieve y
0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0
   I. usieve y                  NB. indices of unique items
1 7 12 14
   (usieve # ]) y               NB. unique items
5 7 3 1

f//.

x f//. y applies f/ to items of y having identical keys. Continuing with the examples, suppose y identifies salesmen and a are the account values. Then:

   a=: 0.1 * 20 ?.@$ 100
   y ,: a
  6   5   9   2   4   9 0   7 0   4   6   8   3   8   1   2   8 0 0   2
4.6 5.5 7.9 5.2 5.4 3.9 6 5.7 6 9.4 4.6 7.8 1.3 1.8 5.1 9.2 7.8 6 9 6.2
   (~.y) ,: y +//. a    NB. total sales for each salesman
  6   5    9    2    4  0   7    8   3   1
9.2 5.5 11.8 20.6 14.8 27 5.7 17.4 1.3 5.1
   (~.y) ,: y >.//. a   NB. minimum accounts
  6   5   9   2   4 0   7   8   3   1
4.6 5.5 7.9 9.2 9.4 9 5.7 7.8 1.3 5.1
   (~.y) ,: y <.//. a   NB. maximum accounts
  6   5   9   2   4 0   7   8   3   1
4.6 5.5 3.9 5.2 5.4 6 5.7 1.8 1.3 5.1

Oblique

The monad  u/. can be modelled as follows on arguments with rank at least 2.

   oblique=: 1 : '+/&i./@(2&{.)@$ u/.&(,/) ]'

   < oblique i.3 4 2
┌───┬───┬─────┬─────┬─────┬─────┐
│0 1│2 3│ 4  5│ 6  7│14 15│22 23│
│   │8 9│10 11│12 13│20 21│     │
│   │   │16 17│18 19│     │     │
└───┴───┴─────┴─────┴─────┴─────┘
   (</. -: < oblique) i.3 4 2
1

   2 3 4 +/ oblique@(*/) 5 6 7 8
10 27 52 61 52 32
   (2 3 4&p. * 5 6 7 8&p.) t. i.6
10 27 52 61 52 32

Cut

u;.1 and u;.2 can be modelled as follows. In the dyads the left argument is assumed to be a boolean list that begins with a 1 for the 1-cut and ends with a 1 for the 2-cut.

   cut1=: 1 : '((e.{.) $: ]) : (+/\ @[ u/. ])'
   cut2=: 1 : '((e.{:) $: ]) : (+/\.@[ u/. ])'

   1 0 0 1 1 0 0 0 < cut1 'dazlious'
┌───┬─┬────┐
│daz│l│ious│
└───┴─┴────┘
   0 1 1 0 0 0 0 1 < cut2 'dazlious'
┌──┬─┬─────┐
│da│z│lious│
└──┴─┴─────┘
   < cut1 ' the quick brown fox'
┌────┬──────┬──────┬────┐
│ the│ quick│ brown│ fox│
└────┴──────┴──────┴────┘
   < cut2 'mississippi'
┌──┬───┬───┬───┐
│mi│ssi│ssi│ppi│
└──┴───┴───┴───┘

Special Code

Several key expressions are supported by special code. See the following entries in the J release notes:

  • J6.02   f//.  (+/%#)/.
  • J5.03   #/.~  </. i.@#  f//.
  • J5.04   #/. on boolean list arguments
  • J5.04   ({.,#)/.

History

Key was not in the APL90 paper by Hui et al. (which introduced J) but was in the J shareware distributed at APL90, 1990-08-13 to 17. Therefore, its definition and implementation happened between the draft deadline in November 1989 and August 1990. It was described in the following e-mail on the IPSA system.

no. 3939637 filed  4.08.09  fri 26 jan 1990
from hui
to   swz
cc   eem jkt kei rbe
subj Do by Key

The operator we discussed this afternoon have been proposed before,
by JKT, RBE, and myself (and no doubt others).  When I was working for
BLEND I observed that this operation arises naturally in many computations.

  ⍺ f adv ⍵     ←→  (=⍺) f⍥#⍤1 99 ⍵     (# is replicate)

Items of ⍺ are keys corresponding to items of ⍵; apply f to items of ⍵
having the same keys.  I was able to model this in J (a new interpreter),
using the 'fork' phrasal form, thus:

  adv =. 1::'=@}: x.@#"1 99 {:'

⍺ <adv ⍵   ⍺ +/adv ⍵   etc. worked.

A plausible monad for the derived function is to use the first item
of each item of ⍵ as keys.

The time in the e-mail was Toronto time, and

hui  Roger Hui
swz  Walter Schwarz
eem  Eugene McDonnell
jkt  Joey Tuttle
kei  Ken Iverson
rbe  Bob Bernecky

The key idea was described in W. Daniel Hillis, The Connection Machine, MIT Press, 1985, Section 2.6, Generalized Beta:

The simplest use of beta is to reduce a xector to a single value. This is actually a special case of a more general operation that reduces portions of xectors and associates the results with other indices. This more general beta operation corresponds closely to the action of the message routers in the same sense that an alpha operation corresponds to the actions of the processors. It is a powerful programming tool that can be used to express some of the most basic functions of CmLisp, such as the inversion of xectors.

The general form of β takes as arguments a combining function and two xectors. It returns a third xector whose values are created from the values of the first xector and whose indexes are taken from the values of the second xector. In other words, it sends the values of the first xector to the indexes specified by the second xector. The combining function specifies how collisions are handled. In the simplest case no combining function is specified, and any collision results in an error. This corresponds to the simple two-argument β used to create a xector with a specified range and domain:

      (β `[1 2 5] `[x y z]) ⇒ {x→1 y→2 z→5}
      (β `[1 2 5] `[x z z]) ⇒ error
When a combining function is specified, it is used to reduce colliding values into a single value:
      (β+ `[1 2 5] `[x z z])     ⇒ {x→1 z→7}
      (β* `[1 2 5] `[x z z])     ⇒ {x→1 z→10}
      (βprog2 `[1 2 5] `[x z z]) ⇒ {x→1 z→5}
In this example, the function prog2 , which returns the second of two arguments, is used to make an arbitrary choice among the possible values.  Because the order of reduction is unspecified, the expression can return a xector with z mapped to either 2 or 5.

When the second xector argument is unspecified, it is taken to be a constant xector, so that all the values in the xector are reduced to a single value, which is returned as the value of the expression. This special case is the single-argument beta operation that was originally introduced.

The general two-argument form of β can be used to define xector inverse as follows:

      (defun inverse (x)
          (β (domain x) x))
Because β is used without a combining function, this version of the inverse produces an error if the xector is noninvertible.

The following is an example that uses both the general and single-argument forms of beta reduction to calculate the maximum number of occurrences of any single value within a vector:

      (defun arity (x)
          (βmax (β+ α1 x)))

      (arity [a b a c a b]) ⇒ 3
      (arity {a b c d})     ⇒ 1

Key in APL

Suitably restricted, key can be programmed readily in APL as a dyadic derived function of a monadic operator:

Dyalog APL:
      Key←{⍺⍺¨(↓(∪⍺)∘.=⍺)⌿¨⊂⍵}
      Key←{j←⍋i←1+⍳⍨⊂[1↓⍳⍴⍴⍺]⍺ ⋄ ↑⍺⍺¨(1,2≠/i[j])⊂[0]⍵⌷⍨⊂j}  ⍝ more general and more efficient

APL2:
      z←x(f Key)y;i;j
      z←f¨i[j]⊂y[j←⍋i←1+t⍳t←⊂[⍳1↓⍴⍴x]x]  ⍝ y must be a vector



Contributed by Roger Hui.