J-ottings 18: Transposition
Vector 15:2, page 43
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 43
A recent question from Bill McLean about transpose in J provided a natural cue for some notes on what can be at first sight one of J’s more daunting corners. The variety of possible options and constraints can make transpose seem quite formidable on first approach — read on to discover that this is not really so!
To begin with, the purpose of transposition, in both J and in APL is to restructure rectangularly oriented data by either reordering or merging axes. In J, the merge/reorder distinction corresponds to that between boxed and non-boxed left arguments. The reorder (non-boxed) case is straightforward, since the rank of the result does not change, only the order of the axes. The result is therefore a "pure" restructure, that is all the original items appear somewhere in the result, and no items are deselected. Permissible left arguments of |: are permutations of m items from i.n where n is the rank of a, that is #$a, and m e. i.n+1, that is m is one of the integers 0,1,..n. The case m=0 is monadic transpose which is equivalent to transposition with the reverse permutation |.i.n. The left argument identifies a vector of indices in $a. The rule is to remove these items from $a and catenate them onto the end of $a. This is different from the APL rule where the left argument specifies the destination indices of the old axes, which means that in general the P-transpose of A in APL, and the P-transpose of A in J where P is a permutation and A is an array, are different. More specifically, the P-transpose in APL is the inverse P-transpose in J, so that (/:P)|:A is equivalent to P⍉A and P|:A is equivalent to (⍋P)⍉A.
Suppose for definiteness that a is a four-dimensional array with $a = 2 3 4 5, and think both of the shape of the transposition, and of the image of the item a[i;j;k;l] in a mapping of a onto itself. Here are a few cases of the above rule in J:
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]
Each entry in the second column is a permutation of $a. There are 64 possible non-empty left arguments (4 with a single integer, 12 with two integers, and 24 each with three and four integers). 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. According to the construction rule, they are necessarily identical since pushing three named indices to the right hand end is equivalent to placing the remaining index first. Thus if n=#$a then both the set of all permutations of i.n and also the set of all possible permutations of n-1 items from i.n account for all possible restructurings by reordering axes. The opportunities afforded by arguments of length one or two can therefore only introduce more redundancy, which in turn increases the apparent complexity of transpose. Redundancy is further increased by 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:
Boxed arguments allow the possibility of restructuring by merging axes. At this point the ways of J and APL diverge even further. In APL, the fact that the left argument of transpose may have repeated indices blurs the distinction between reordering and merging. In J, this difference is sparklingly clear — the argument is either boxed for merge or not-boxed for reordering!
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 r, 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 is given in the final column below. The coordinate 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.
condition on index
for an item of a image of
argument new $a to be selected 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 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,lreplacing 0,1,2,3, and=s inserted, and the fourth column echoes the second column as explained above.
Also merging axes in the present sense must not be confused with the restructuring associated with e.g. ,[1 2]a in APL where all the data is retained but rank is reduced.
There is a parallel between the fourth column above and the SQL command
It may help to think of boxed arguments in these terms, although be aware that it is indices which are selected and not values as would be the case in SQL, so that transpose should not be seen as a vehicle for modelling selection from relational databases.
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 list of three lists, each of which is a list of length five, each item within which is a list of two items. Using the SQL analogy (<0 2)|:a can be read as
So much for structure. The second step is to identify which data occupies each cell of the result. 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 of the three lists are:
and the remaining two are obtained by replacing the 0s in the second column in turn with 1s and 2s. If the result required were a list of five lists, each of which is a list of length three, so that the pattern of indices for the first list is
a further transposition must be applied, viz. 1 0 2|:(<0 2)|:a .
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. Various physical mappings of the non-selected items (that is those whose indices do not appear in the condition in column three in the table above) onto the selected items are possible. The non-selected items may be thought of as being "swept" towards the appropriate diagonal cross-section along either an axial direction or a generalised plane defined by axial directions. For example in the rank two case defined by <0 1 as left argument, there are two possible physical mappings depending on whether items in rows or items in columns are perceived as being swept horizontally onto the diagonal.
The reasoning behind one of the most frequently occurring practical applications
should now be readily apparent, as should
(both the parentheses and the colon are necessary in the definition of ndiag.) and
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.
An inverse transposition is obtained by using the corresponding inverse permutation. Inverse permutations are obtained directly by grade up. In the above example 1 2 0 and 2 0 1 are inverse permutations, that is:
so that …
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.
Describing the whole range of possibilities may have made this discussion seem complex. There is nevertheless a compelling simplicity in the fundamental underlying rules, and an appropriate conclusion is therefore a summary in a few lines of all there is to know about transpose, viz.:
| axes are: | effect on rank | left argument | contents of left arg. | shape vector rule |
|---|---|---|---|---|
| reordered | unchanged | not boxed | permutation | named axes to tail |
| merged | reduced | boxed | combination | merged axis to tail |
Notes¶
- Reordering only: the full potential is available by using only full permutations — lower order permutations are valid, but give no essentially new transformations.
- Reordering and merging axes requires two applications of
|:.