Fifty Shades of J/Chapter 07
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
- /: (grade up) : (grade down) |: (transpose) a. (alphabet) ? (deal), “ (rank conjunction) sorting, ranking, collating sequence, tied ranks, schoolmasters rank, reflections, rotations, mean, median
Sorting Lists
A Vector obituary preview column? Well not quite, or maybe the answer should be, of a 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 V[⍋V]) has a direct J equivalent in the following bridge hook
({~/:)4 2 7 1
1 2 4 7
The algorithm applies equally to character lists
({~/:)>'Fred';'Joe';'Egbert'
Egbert
Fred
Joe
For convenience give names to the verbs which sort lists up and down
sortu=:{~/:
sortd=:{~\:
sortd>'Fred';'Joe';'Egbert'
Joe
Fred
Egbert
Sort by rows and sort within rows are differentiated by using the rank (") conjunction
]u=:?3 4$10 4 0 1 2 7 9 3 2 1 2 9 5 (sortu u);sortu"1 u ┌───────┬───────┐ │1 2 9 5│0 1 2 4│ │4 0 1 2│2 3 7 9│ │7 9 3 2│1 2 5 9│ └───────┴───────┘
For sort by columns do a row sort under (&.) the transformation (|:) (transpose)
sortu&.|: u 0 1 2 4 9 3 2 7 2 9 5 1
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 3 5 7 0 2 4 6 8
(/:oe i.v){v=.4 2 7 1
1 7 2 4
Consolidate this in a verb
csortu=:/:@i.{] NB. x is collating seq.
oe csortu 4 2 7 1
1 7 2 4
Here is a collating sequence which blurs the distinction between uppercase and lowercase characters
]cs=:(,|:65 97+every <i.26){a.
AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz
m=:>'bless';'This ';'house'
(];sortu;cs&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-up applies
x/:y is equivalent to (/:y){x
so that x must be at least as long as y . A special case satisfying this constraint is when x and y are equal, in 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
sortu=:/:~ sortd=:\:~
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=:] /: {"1
(];1&colsort;3&colsort)u
┌───────┬───────┬───────┐
│4 0 1 2│4 0 1 2│4 0 1 2│
│7 9 3 2│1 2 9 5│7 9 3 2│
│1 2 9 5│7 9 3 2│1 2 9 5│
└───────┴───────┴───────┘
It is worth while pausing to consider how this fork works. The verb from ({) at 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 as in data base tables the principle remains unchanged but some minor variations may be necessary involving the use of open (>) and @: to take care of rank inheritance
selectc=:>@{"1 NB. select xth column of y
sortc=:/:@:selectc { ] NB. order y by column x
dbase=:'York';'England';100000
dbase=:|:('Edinburgh';'Scotland';500000),.dbase
dbase=:('Aberdeen';'Scotland';200000),dbase
]dbase=:('Bristol';'England';400000),dbase
┌─────────┬────────┬──────┐
│Bristol │England │400000│
├─────────┼────────┼──────┤
│Aberdeen │Scotland│200000│
├─────────┼────────┼──────┤
│Edinburgh│Scotland│500000│
├─────────┼────────┼──────┤
│York │England │100000│
└─────────┴────────┴──────┘
1&sortc dbase NB. sort by country
┌─────────┬────────┬──────┐
│Bristol │England │400000│
├─────────┼────────┼──────┤
│York │England │100000│
├─────────┼────────┼──────┤
│Aberdeen │Scotland│200000│
├─────────┼────────┼──────┤
│Edinburgh│Scotland│500000│
└─────────┴────────┴──────┘
2&sortc dbase NB. sort by population
┌─────────┬────────┬──────┐
│York │England │100000│
├─────────┼────────┼──────┤
│Aberdeen │Scotland│200000│
├─────────┼────────┼──────┤
│Bristol │England │400000│
├─────────┼────────┼──────┤
│Edinburgh│Scotland│500000│
└─────────┴────────┴──────┘
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.
It might be expected that, by analogy with APL, /:/:v delivers the upward ranking of the elements of v
/:/:4 2 7 1 2 1 3 0
However, if /:/: is isolated by parens around the functions or named, then they are evaluated differently, i.e.
(/:/:)4 2 7 1 7 2 1 4
The reason is that /:/: by itself is a hook.The rightmost /: 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 above, a second grade-up is performed resulting in the intermediate generation of the rank list 2 1 3 0 which is then applied as a selection list (from) on the original right argument leading to the result 7 2 1 4. To block this last step it is necessary to use a different composition mechanism for the two /: verbs, viz.
(rku=:/:@/:)4 2 7 1 2 1 3 0
Downward ranking uses both grade-up and grade-down
(rkd=:/:@\:)4 2 7 1 1 2 0 3
Upward and downward tied ranks require slightly unwieldy verb combinations
rktu=:-:@(rku + \:@/:@|.) rktd=:-:@(rkd + \:@\:@|.) rktu v1=:5 3 3 5 2 5 8 4 1.5 1.5 4 0 4 6 rktd v1 2 4.5 4.5 2 6 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 be achieved by a single fork
sch=:i.~{rkd
>:sch v1
2 5 5 2 7 2 1
The grade verbs have applications outside the realm of strict sorting. In Essay #30: Just what do they sell at C&A? grade-up is 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 /: is a self-inverse verb, and so in these circumstances /:/:y is identical to y .
Then in Essay #26: Working in Groups it transpires 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 e.g. 1 0 2 3 is represented by
. 1 . . 1 . . . . . 1 . . . . 1
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. /:@\: 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), n=length of vector y
minmax=:<. , >. NB. floor,ceiling of real number y
mean=:+/%# NB. arithmetic mean
median=:mean @ ((minmax@mindex) { sortu)
median 4 2 7 1 NB.mean of two middle values
3
Now introduce sortu as the right prong of a fork, and use mean to average the values of the two (possibly identical) middle values
median=:mean @ ((minmax@mindex) { sortu)
median 4 2 7 1 NB.mean of two middle values
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!
Code Summary
sortu=:/:~ NB. sort upwards
sortd=:\:~ NB. sort downwards
cs=:(,|:65 97+every <i.26){a. NB. alphabet AaBbCc…
colsort=:] /: {"1 NB. sort matrix by columns
selectc=:>@{"1 NB. select xth column of y
sortc=:/:@:selectc { ] NB. order y by column x
rku=:/:@/: NB. upward ranking
rkd=:/:@\: NB. downward ranking
rktu=:-:@(rku + \:@/:@|.) NB. upward ranking with ties
rktd=:-:@(rkd + \:@\:@|.) NB. downward ranking with ties
sch=:i.~{rkd NB. schoolmaster’s ranking
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
median=:mean @ ((minmax@mindex) { sortu)