Fifty Shades of J/Chapter 7

From J Wiki
Jump to: navigation, search

Table of Contents ... Glossary ... Previous Chapter ... Next Chapter

One Foot in the Grade

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)

Script

File:Fsojc07.ijs