APL Identities in Progressive Index Idiom

Question

These idioms have a few things in common. The final step for both is an index-of operation, they both use sort of a mirrored concatenation strategy, and perhaps most importantly, the output of the left and right arguments is the same for both. That simplifies the search for an identity quite a bit, because we can compare the right argument of #1 with the right argument of of #5:

(⍴Y)⍴⍋⍋X⍳Y,X                ⍝ right arg #1
(⍋X⍳Y,X)⍳⍳⍴Y                ⍝ right arg #5

Another thing that can simplify the search is getting rid of or modifying anything that truncates the output, because the output of both arguments is the same without truncating. Idiom # 1 uses (⍴Y)⍴ to truncate it to the length of Y, and the length of right argument in idiom #5 depends on the length of Y in ⍳⍴Y. In the first case, the truncation can be removed, and in the second, it can be modified to the full length of Y,X :

⍋⍋X⍳Y,X                     ⍝ #1
(⍋X⍳Y,X)⍳⍳⍴Y,X              ⍝ #5

Given that both expressions contain ⍋X⍳Y,X, let's assign that to a variable A ← ⍋X⍳Y,X and simplify. However, it's important to point out that the identity we have now only applies if A is a permutation vector, and I'll be talking more about that later. In the meantime, we have this identity:

⍋A ←→ A⍳⍳⍴Y,X

Since ´Y,X´ does nothing in this expression except for provide the vector length, and since that length is equal to ´A´, the identity can be simplified to its final form:

⍋A ←→ A⍳⍳⍴A, where A is a permutation vector

This makes a lot of sense. The grade-up operator, on the left side of the identity, returns the index values that each value of A would have if it were assorted in ascending order. The index-of operator, on the right, returns the index in A where the ascending values of ⍳⍴A are located. For example:

5 2 1 4 3                   ⍝ A←5 2 1 4 3
3 2 5 4 1                   ⍝ ⍋A

5 2 1 4 3                   ⍝ A←5 2 1 4 3
1 2 3 4 5                   ⍝ ⍳⍴A
3 2 5 4 1                   ⍝ A⍳⍳⍴A

Looking at the last two rows, the 1 has an index of 3 in A, 2 has 2, 3 has 5, 4 has 4 and the final 5 has an index of 1. That makes sense because that is pretty much by definition what the grade-up operator does.

Permutation Vectors

As already said, this identity is only valid if A is a permutation vector. In his essay Notation as a Tool of Thought , Kenneth Iverson defined a permutation vector: “A vector P whose elements are some permutation of its indices (that is, ^/1=+/P∘.=⍳⍴P) will be called a permutation vector.” Looking at some of the idioms themselves, you can see this idea represented in various ways:

Y[⍋Y]^.=X[⍋X]           #6 permutations of each other 
X^.=⍋⍋X                 #7 test if permutation vector
X[⍋X]^.=⍳⍴X             #29 test if permutation vector
⍋X                      #48 Inverting a permutation 
X⍳⍳⍴X                   #212 Inverting a permutation
^/1=+⌿X∘.=⍳⍴X           #281 test if permutation vector
^/(⍳⍴X)∊X               #454 test if permutation vector
A←⍳⍴X ⋄ A[X]←A ⋄ A      #654 Inverting a permutation

In idiom #7, the right side of the expression is the ascending cardinal numbers idiom, which I discussed in another post, and in that post I talked about the fact that the grade up operator switches back and forth between two states, rank and index, such that we have the following two identities:

⍋X ←→ ⍋⍋⍋X ←→ ⍋⍋⍋⍋⍋X ...
⍋⍋X ←→ ⍋⍋⍋⍋X ←→ ⍋⍋⍋⍋⍋⍋X ...

That second identity could be extend as follows, if X is a permutation vector as idiom #7 establishes:

X ←→ ⍋⍋X ←→ ⍋⍋⍋⍋X ←→ ⍋⍋⍋⍋⍋⍋X …

We know that the grade-up operator returns all the numbers from 1 to the number of values in the argument. Apply the grade-up operator two more times and you get the exact same vector in the same order. Therefore idiom #7 is just saying that a permutation vector is one which contains all the numbers from 1 to some other value once and only once. (This assumes that 1 is set as the first index value.)

Another thing that is interesting about the list of idioms above is that idiom #48 and #212 are the left and right sides of the identity discussed in the answer:

⍋A ←→ A⍳⍳⍴Y,X