Fifty Shades of J/Chapter 08
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
- |: (transpose) “(rank conjunction), #(tally) SQL, diagonals of arrays, mappings, transformations, merged axes, symmetry test, inverse permutations.
The Verb: Transpose
Those with a mathematical training will naturally association the verb transpose (|:) with matrices and ‘row and column switches’. This is perfectly natural, but I would suggest that, as with many aspects of J, it is insightful to think also in terms of lists, which also helps to bring thinking closer to what is going on behind the scenes. Consider
i.3 4 0 1 2 3 4 5 6 7 8 9 10 11
This is a 3-list of lists, each of which is 4-list. Where secondary lists are of equal length (or equivalently the data is rectangular) a second list of lists automatically exists, viz. a 4-list of 3-lists, these being obtained by making a list of all the first items, then another of all the second items and so on (in simple terms, working down columns!). If the list hierarchy of i.3 4 is say 0 1, then the effect of transposition is that of turning the secondary list into the primary one, so that the hierarchy becomes 1 0. With every further imbedding of equal-length lists such as i.2 3 4 (a 2-list of 3-lists of 4-lists), there comes a new layer in the list hierarchy, and with it new possibilities for reordering that hierarchy. For example with i.2 3 4 and a hiererchy 0 1 2, promoting 2 to the top level is equivalent to starting with all the first items in the 4-lists. These form a 2-list of 3-lists and lead to another choice, 0 1 or 1 0. Following this argument the number of possible transpositions is equal to the number of permutations amongst these hierarchies. It is very reasonable then that the left argument of |: should be a permutation of the tally (#) of the rank of the right argument. The manner in which such permutations is defined is that the hierarchly levels denoted by the left argument are pushed to the right leaving the remaining levels unchanged, whereas without any argument at all, that is the monadic case, the hierarchy is completely reversed :
$0 2|:i.2 3 4 3 2 4 $|:i.2 3 4 4 3 2
Matrices can be modelled as lists, and higher order rectangular arrays as multi-dimensional cuboids, so that in geometrical terms, transposition is the process of switching the order of axes. Arrays can also be described algebraically in terms of coordinates, and the result of transposition is a mapping (that is, transformation) of an array a onto itself in which each item such as a[i;j;k;l] has an image with the same coordinates in a different order as determined by the permutation list which is the left argument. Here are a few cases in which a=.i.2 3 4 5
| left argument | new $a | image of a[i;j;k;l] |
|---|---|---|
| 0 1 | 4 5 2 3 | a[k;l;i;j] |
| 0 2 3 | 3 2 4 5 | a[j;i;k;l] |
| 3 1 0 | 4 5 3 2 | a[k;l;j;i] |
| 2 3 1 0 | 4 5 3 2 | a[k;l;j;i] |
With a rank 4 array such as a there are 43 = 64 possible non-empty left arguments (4 with a single integer, 12 with two integers, and 24 with three and four integers in each case). Some of the corresponding transpositions must overlap since there are only 24 distinct permutations of $a. Consider the arguments in the last two rows in the table above. These are necessarily identical since pushing 3 1 0 to the right is equivalent to placing the remaining index first. Similarly a left argument 2 3 0 1 produces the same result as 0 1. A singleton left argument demotes that axis to the lowest hierarchy level. The opportunities afforded by arguments of less than full length therefore introduces redundancy. Further redundancy arises from applying monadic transpose at different levels of rank using the rank conjunction. Specifically for a rank 4 object the following monadic transpositions and dyadic transpositions are equivalent
|:"1 |:"2 |:"3 |:"4
0 1 2 3&|: 0 1 3 2&|: 0 3 2 1&|: 3 2 1 0&|:
Boxed arguments
Boxed arguments allow the possibility of restructuring by merging axes. If the argument is boxed, the indices contained in the box are merged, and the corresponding axis-length in the box is the minimum of these axis-lengths. Since this results in general in the non-selection of some items, the overall effect is that of reducing the overall bulk of data. In the shape vector of the result array, the unmerged axes all appear before the merged one. In terms of mappings, transpose effects a many-to-one mapping, for which the image of each point in the result array r is given in the final column below. The co-ordinate names in this column match the values in column two, and can be used to establish systematically from source the value of any item in the result.
| argument | new $a | condition on index for an item of a to be selected |
image of a[i;j;k;l] |
|---|---|---|---|
| <0 1 | 4 5 2 | i=j | r[k;l;i] |
| <0 2 | 3 5 2 | i=k | r[j;l;i] |
| <1 2 | 2 5 3 0 | j=k | r[i;l;j] |
| <0 1 3 | 4 2 | i=j=l | r[k;i] |
Two properties of the above table deserve emphasis:
- unlike the non-boxed case, the order of items in the boxed argument is immaterial, that is the contents of a box is a combination of m items from n rather than a permutation;
- the third column echoes the first column with i,j,k,l replacing 0,1,2,3, and =s inserted, and the fourth column echoes the second column as explained above.
There is a parallel between the third column above and the SQL (Structured Query Language) command
SELECT ... WHERE ...
It may help to think of boxed arguments in these terms, subject to the qualification that it is indices which are selected and not values as would be the case with SQL.
Consider another specific example, say (<0 2)|:a. There are two steps in evaluating this. The first and most straightforward step is to identify the new $a. (<0 2) means that it is axes 0 and 2 which are to be merged. The length of the merged axis-length is 2<.4, that is, 2. The remaining axis lengths are 3 5, and so $a is 3 5 2, which means that the result is a 3-list, each list of which is a 5-list, each item within which is a 2-list. Using the SQL analogy (<0 2)|:a can be read as
SELECT a[i;j;k;l] WHERE i=k
The next step is to identify the original index of the data which occupies each cell in the transposed form. This is where the third column comes in. The constraint i=k means that the only items which are to be selected are those whose indices are of the form 0 x 0 y and 1 x 1 y where x is chosen from i.3 and y is chosen independently from i.5. Specifically the indices of the items in the first 3-list are
0 0 0 0 1 0 1 0
0 0 0 1 1 0 1 1
0 0 0 2 1 0 1 2
0 0 0 3 1 0 1 3
0 0 0 4 1 0 1 4
and those of the remaining two 3-lists are obtained by replacing the 0s in the second column in turn with 1s and 2s. The order of the most rapidly changing indices is l, j, k=i.
To transform a 3-list of 5-lists of 2-lists into a 5-list of 3-lists of 2-lists apply the non-boxed transposition 1 0 2|:(<0 2)|:a. The pattern of indices for the first list is now
0 0 0 0 1 0 1 0
0 1 0 0 1 1 1 0
0 2 0 0 1 2 1 0
and the order of the most rapidly changing indices is now j, k=i, l.
Geometrically speaking, the result of a merge transpose is a diagonal cross-section of rectangular data whose rank is determined by the number of axes merged. If the length of the boxed left argument is n then the rank of the result is less than the rank of the original by n-1.
One of the most frequently occurring practical applications of transpose, which also demonstrates a noun-verb bond, is
diag=:(<0 1)&|: NB. leading diagonal of matrix
Its meaning should be readily apparent, as should that of
ndiag=:diag@:(|."1) NB. non-leading diagonal
The following hook provides a symmetry test
sym=:-:|: (sym i.3 3),sym 3 3$1 NB. 1 if symmetrical 0 1
Transpose can be used as a transformation when either an operational verb is most readily coded for a different arrangement of data axes, or reuse of an existing verb is easier than writing a new one to accommodate a different axis ordering. This principle can be simply illustrated using a rank three object d=.i.2 3 4 thought of as a structure of planes, rows and columns.
1 2+d adds 1 to the first plane and 2 to the second. Corresponding additions to rows are achieved by applying the rank conjunction, 1 2 3 +"2 d, and to columns by 1 2 3 4+"1 d. The rank conjunction can be circumvented by promoting say columns to become the major dimension using transpose, adding, and then using the inverse transposition to restore the original shape.
1 2 0 |: 1 2 3 4 + 2 0 1 |:d
or, to put it more succinctly
(1 2 3 4&+&.(2 0 1&|:))d
An inverse transposition is obtained by using the corresponding inverse permutation. Inverse permutations are obtained directly by grade-up provided that the permutation is spelt out in its full form. In the above example 1 2 0 and 2 0 1 are inverse permutations, that is 1 2 0 -:/: 2 0 1 so that a -: 1 2 0|:2 0 1|:a for any rank three object a.
The single item permutation cases are sometimes useful. For a rank three object, 1|: exchanges rows and columns within planes. For an object of any rank 0|: promotes the second dimension to become the major dimension, and (n-1)|: swaps the two lowest-order dimensions.
It is worth observing that data content has taken little or no part in this discussion, that is transposition is all about changing the shape of data in the unboxed case, and in determining how to make selections from it in the boxed case.
Code Summary
diag=:(<0 1)&|: NB. leading diagonal of matrix ndiag=:diag@:(|."1) NB. non-leading diagonal of matrix sym=:-:|: NB. symmetry test