J-ottings 24: One Foot in the Grade

VECTOR Vol.16 No.4

J-ottings 24: One Foot in the Grade

by Norman Thomson

A Vector obituary preview column? Well not quite, or maybe the answer should be, sort, since that is what grade (used generically to refer to both the grade- up and grade-down verbs) is all about. Sorting a list (the equivalent of APL VLAV]) has a direct J equivalent in the following bridge hook”:

este 274 1247

The algorithm applies equally to character lists:

({-/1)>'Pred';'Joe'; Egbert! Egbert Fred Joe

For convenience give names to the verbs which sort lists up and down:

sortus: {-/: sortd=: {-\: sortd>'Fred';'Joe';'Egbert' Joe Fred Egbert

Sort by rows and sort within rows are differentiated by using the conjunction :

23 4$10 4 2 6 t ctu u)s;sortu"i u

sae won IO NEO Ono ous ana Oa rank

For sort by columns do a row sort under (&.) the transformation |: (transpose):

ortué. |}: u

VECTOR Vol.16 No.4

Flexibility in the choice of collating sequence (say all the odd numbers are to be prior to any of the evens) is achieved by using dyadic i. :

oe=.1 3570 (/ioe t.v) {v= 1724 2 a

Consolidate this in a verb:

csortu=,/:@i.{] NB. x. is collating seq. ee=.1 3579024 68 oe csortu 4 27 1 1724

Here is a collating sequence which blurs the distinction between upper and lower case characters : ,

each=. &> Jes=.(,|]:65 97+each <i.26){a. AaBbCcDdEeF fGgHhIid jKKLIMMNnNOoPpQqRrSsTtUuVvWwXxYyZz

m=,>'bless';'This ';'house' (]isortu;csaécsortu)m

bless|This |bless This |bless|house house|house| This

Dyadic Grade

Whereas dyadic grade in APL provides a means of changing the collating sequence, this is not the case in J where the following rule for dyadic grade applies :

x./:y. isequivalentto (/: y.){x.

so that x. must be at least as long . A special case satisfying this constraint is when x. and y. are which case y. /: y. (or equivalently /:~y.) is simply another definition of sortu. The definitions of sortu and sortd can therefore be shortened by one character to

35

VECTOR Vol.16 No.4

Sorting by columns of a matrix other than the first requires dyadic grade. The following display demonstrates sorting on the 2nd and 4th columns. colsort=,] /: {"4 (];14colsort;3&colsort)u 506 4%/5 06 4/7 972 7:97 21/073 4 0736/7 97 2/0736

It is worth while pausing to consider how this fork works, The from rank 1 on the right of the fork selects the chosen column as y.. ] selects the entire table as x.. Now apply the dyadic grade rule above. The indices for ordering the chosen column are obtained as /: y. and are used to select from all the columns in the table.

When items within matrices have complex structures tables the principle remains unchanged but some minor variations may be necessary involving the use of open (>) and @: to take rank inheritance : selectc sortcs: r>@{ra NB. select x.th column of y. :@:selecte { ] NB. order y. by column x. dbase Bristol England {400000 Aberdeen |Scotland| 200000 Edinburgh |Scotland|500000 York England |100000

(1&4sortc,,2&sortc) dbase NB. sort by country, then population Bristol England |400000/ York England |100000 York England |100000/Aberdeen |Scotland|200000 Aberdeen |Scotland|200000/Bristol England /|400000 Edinburghj Scotland|500000|£Edinburgh | Scotland| 500000

36

VECTOR Vol.16 No.4

Ranking

The potential confusion between rank in the J sense (as in rank conjunction) and rank in the sense of collating sequence ordering can be avoided by referring to the latter as ranking.

Tt might be expected that, by analogy with APL, v delivers the upward ranking of the elements of v_ .

AYIA 7244

Why does APL intuition fail? The reason is that is a hook. The rightmost 7: obtains the upward ordering index vector of v which is 3 1 0 2, which, in the absence of an explicit left argument is both left and right argument to the leftmost dyadic /+ . Following the rule second grade up is performed resulting in the intermediate generation rank vector 2 1 3 0 which is then applied as a selection vector (from) on the original right argument leading to the result 7 21 4. To block this last step it is necessary to use a different composition mechanism for the two /:’s, viz

(rkusi/:@/:)4 2 7 4 2130

Downward ranking uses both grade up and grade down:

(rkd=:/:@\: 4 27 4 1204

Upward and downward tied rankings require slightly unwieldy verb combinations :

vktu=.-1@(rku + \:@/:@|.) rktd=,-:@(ckd + \:@\:@1.) rktu vie.§ 33525 8 1.5 1.5 4% 04 6 rktd vi 24.5 4.5 26 2 0

A variation of rktd is schoolmaster s rank” in which students with equal scores are each rated as highly as possible, a property inherent in dyadic i. . The work for the schoolmaster’s ranking verb has largely been done and it can by a single fork :

sche.i.~{rkd >rsch vi 2552721

37

VECTOR Vol.16 No.4

The grade verbs have applications outside the realm of strict sorting. In J-ottings 23 grade up was used to perform inverse permutations, that to reverse the effects of a shuffle. In technical terms, when the argument y. is a permutation, that is an arrangement of all the items in i. n where n is a positive integer, then /: isa self-inverse verb, and so in these circumstances /: /: y. isidenticalto y. -

Then in J-ottings 22 it transpired that the application of grade verbs to permutations matched exactly the transformations of rotations and reflections about axes in the plane applied to matrices which provide alternative representations of: the permutation in the sense that, for example, 1 0 2 3 is represented by

wld. wl

Specifically /: is a reflection in the line x+y=0 but \: is a clockwise rotation through 90 degrees. The reflection/rotation distinction underlines the non- symmetrical behaviour of /: and \: in the ranking algorithms given above. 7:@\: and /:@\: represent reflections in the x and y-axes, \: @\: @\: represents an anti-clockwise rotation through 90 degrees and \:@\: represents a half-turn. Finally /: @\: @\: represents a reflection in the line x=y.

Order statistics, such as median, require the use of grade. A median algorithm can be built up using three auxiliary verbs:

mindex=.-:@<:@# NB. 0.5*(n-1) where n is length of vector y minmax=:<. , >. NB. Floor,ceiling of real number y. mean=.+/%# NB. Arithmetic mean

Now introduce sortu as the right prong fork, and use mean to average the values of the two (possibly identical) middle values:

median=:mean @ (minmax@mindex) { sortu median 4 2714 NB. mean of two middle values 2 and 4 3

Verbs defining other partition values, e.g. percentiles, use the same principle, although inevitably are more complex in detail.

In short grade is a very versatile verb for which you should rightly have grade expectations.

Have a grade day!

38