Progressive Index-of Idiom in APL

Question

The first idiom of the FinnAPL Library, which is called “Progressive index of (without replacement) “ is fairly straightforward as far as what the operations are:

X←'dog food'
Y←'fod'
((⍴X)⍴⍋⍋X⍳X,Y)⍳(⍴Y)⍴⍋⍋X⍳Y,X ⍝ output 5 2 1

For every value inY, it returns the index position in X. If Y has the same value twice, it returns the index of the second occurance in X. For example, if Y were 'fodd' the output would be 5 2 1 8, since the second 'd' in X is in the 8th position. For any value in Y that isn't found in X, it returns an index value outside the range of X. For example, if Y were 'fudd' the output would be 5 9 1 8.

This idiom is like a mirror image revolving around the index-of operator ⍳. The right argument concatenates Y followed by X, performs an index-of operation with X and then truncates it to the length of Y. The left argument is almost the same, except that it reverses the roles of X and Y. It concatenates X followed by Y, performs an index-of operation with X and truncates it to the length of Y.

Although it's easy to see what is happening, it's hard to understand why it works. So, that's my question.

Answer 1

As a quick overview of the operators. The index-of operator ⍳ returns the index position in the left argument of the values in the right argument. The ascending cardinal numbers idiom ⍋⍋, which I like to refer to as “rank,” returns the position that an input value would occupy after a grade-up sort. And finally, the use of the shape-of operator ⍴ in the expression (⍴Y)⍴A returns the first values of A as a vector of equal length to Y. In other words, it acts like a substring function (at least as it is applied here).

Having gone over that, let's consider how the left and right arguments of the final index-of operation are formed:

 1  2  3  4  5  2  2  1  5  2  1    X⍳X,Y   left
 1  8 11  2  6  7 10  3  4  5  9    ⍋X⍳X,Y
 1  4  8  9 10  5  6  2 11  7  3    ⍋⍋X⍳X,Y

 5  2  1  1  2  3  4  5  2  2  1    X⍳Y,X   right
 3  4 11  2  5  9 10  6  7  1  8    ⍋X⍳Y,X
10  4  1  2  5  8  9 11  6  7  3    ⍋⍋X⍳Y,X

 1  4  8  9 10  5  6  2             left    (⍴X)⍴⍋⍋X⍳X,Y
10  4  1                            right   (⍴Y)⍴⍋⍋X⍳Y,X
 5  2  1                            result

Looking at the right argument '10 4 1,' you can see than rank has been assigned to the index values of the letters 'fod' in the expression ´X⍳Y,X´. In other words, after a grade-up sort, 'f' would be in position 10, 'o' in 4 and 'd' in position 1. This can be seen more clearly by applying the index values to the letters after the sort:

(Y,X)[⍋X⍳Y,X]                       ⍝ dddoooog ff

This is the exact same result when the index values of the left argument are applied to the concatenation of X followed by Y:

(X,Y)[⍋X⍳X,Y]                       ⍝ dddoooog ff

Even though they are the same, they are the results of applying index values to two different strings, “foddog food” and “dog foodfod.” By applying the grade-up operator a second time along with taking the substring, the frame of reference is returned to the original strings, “dog food” and “fod.” However, they now have a common ground since the left and right arguments are “ranks” relating to a common string “dddoooog ff.” Being ranks, as I discussed in another post, they also refer to the original positions. Therefore, by applying the final index-of operator, the index refers not only to the position of the left argument but to the index positions in original string stored in X, “dog food,” as well.

The general form of many of these sorting idioms is index-rank-index, where the rank acts as a bridge, tying the input to the output. This is possible, because as a set of key-value pairs, the elements of a rank vector can simultaneously refer to two things at the same time. In the example, the 10 in the right argument has a key value of 1, relating to index value of the “f” in “fud.” The 10 in the left argument has a key value of 5, relating to the index value of the “f” in “dog food.” In addition to that, the values are both 10, relating one rank vector to another. Therefore, both the keys and values are referring to the letter “f” but in two different ways.

The moral of the story is when trying to design a sorting idiom, the place to start may just be in figuring out how a rank vector can form a bridge between input and output.