Indexing Arrays

Lately I have been working on formalizing APL. One of the core problems related to the formalization of APL is how indexing into various arrays that have been derived from other arrays works. In particular, one of the more interesting aspects is the relation between what is known as an array's ravel and the array itself. It has taken me a while, but I have finally come to appreciate the relationship between number systems, multi-dimensional array indexing, and the core operators provided in APL, which actually all work in unison to provide an interesting illustration of the relationship of all of this.

Let's first consider the definitions of indexing into an array and its ravel. Say that we have an array A that has shape ⍴A. This shape is represented as another Vector (also called a one-dimensional array) S. We say that the Ravel of Array A, which we will call R, is given by the expression ,R. The number of elements of the array A is then given by the product of the elements of the shape of A, which is also equal to the length of the ravel of A. This is expressed by the expression (,×/⍴A)≡(,×/S)≡⍴,A, that is, the vector containing the product of the elements of the shape of A is equivalent to the shape vector of the ravel of A. The ravel is just the vector of all the element of A as if selected in row-major order. We can grab the individual elements out of an array with the indexing operation ⌷ which, given an index vector on the left and an array to index on the right, will give the element in A at the location represented by the index vector I. For this discussion, we will assume that all index vectors are the same shape as the shape of S. That is, we assume that the length of the vector I is the same as the rank of A, which is expressed succinctly by the expression (⍴I)≡⍴⍴A. [Note: In this discussion, all operations are considered as evaluating from right-to-left when questions of precedent come into play.]

With these preliminaries out of the way, the question then becomes how we can talk about the relationship of I⌷A and J⌷,A. That is, how do we relate in a more precise way the elements in A to the elements in ,A. In this discussion, we will frame this in terms of finding a suitable value J for a given I such that (I⌷A)≡J⌷,A.

To begin this search, let's restrict ourselves to only those arrays whose shape is a vector of all the same elements. That is, an array with the same sized dimensions for all its dimensions. If we consider only Matrixes (two dimensional arrays), then the row-major traversal says that for a given index vector Ir Ic the corresponding index J into the ravel of the array is (Ir×Sc)+Ic, or, in other words, we traverse the total number of columns in the array the number of rows we have, which gets us to the right row of the matrix, whereupon we can simply skip forward to the column that we care about it. Let's try to generalize this, which leads to the following recursive program. In the following code, ∇ is a recursive call to the function, ⍺ is the left argument, and ⍵ is the right argument. In this function we expect the shape of the function to be the left argument and the index vector from which we are trying to get a ravel index to be the right argument.

{
	⍺≡⍬: 0 ⍝ Return 0 if we have an empty shape
	(×/ (⊃⍵) , 1 ↓ ⍺) + (1 ↓ ⍺) ∇ 1 ↓ ⍵
}

This function basically says that for every element in the index vector, we multiply that element by the elements in the shape that are lower order (we say 1 ↓ X to indicate the array X with the first element dropped off) and sum that result to the ravel index generated for the rest of the elements, recursively. Does this look familiar? No? Let's say that we have a three-dimensional array where each dimension size is 10. If we want to get the ravel index for the index vector 3 5 7 the recursion will look something like this:

((3×10×10)+(5×10)+7+0)≡357

Thus, the ravel index of 3 5 7 for an array of shape 10 10 10 is 357. Now does that look familiar? It should, because this is exactly the same operation that we do when we want to build up a decimal number from a vector of its decimal digits! Indeed, in APL, we already have a built in operation that does this for us. It's called ⊥ and given a base on the left and digits on the right, it gives you the number in that base. So, for this example, we could have computed the ravel index for 3 5 7 by getting the value of 10 ⊥ 3 5 7. Thus, if we have an array that is all of the same sized dimensions we can say that (I⌷A)≡((⊃ ⍴ A) ⊥ I)⌷,A. But here we are only taking the first element of the shape of A and assuming that all the others are the same (⊃ X gives us the first element out of X). What happens if we have differently sized dimensions? Well, it's actually the same process that is going on, and ⊥ is written to scale to any sized vector as its left argument, where each element of the vector represents one of the place-values in the number system. In normal number systems, the place-values are all the same, such as 10 or 2. However, that's not always the case, and we often consider values such as dates or times, which have different places, or we consider, as is this case, row-major array indices. Thus, we can say that definitively that the following expression holds for all arrays and valid indexes:

(I⌷A)≡((⍴A) ⊥ I)⌷,A

Thus, the process of getting the corresponding element out of the ravel of A based on an index vector into A is the same process as converting that index vector into a natural number value based on the number system described by the shape of A. For me, this is a nice, clean sort of symmetry between number systems and multi-dimensional arrays. In fact, that symmetry goes the other way to. We can, given a shape and any ravel index, easily get back the index vector to the corresponding element in the original array using the inverse function of ⊥ which is the function ⊤. So, if we were given 357 as a ravel index, we could get back the original index vector assuming that we knew the original shape of the array. In our example, this is 3⍴10 (a three dimensional array with each dimension of size 10), so the index vector corresponding to the ravel index 357 is (3 ⍴ 10) ⊤ 357 which is 3 5 7. This allows us to state the following:

(J⌷,A)≡((⍴A) ⊤ J)⌷A

Pretty neat, huh?