3 min read

APL a Day #5: Indexing into Arrays

By now, clearly a shape and vector of values precisely determines an array. All APL functions operate over arrays; they describe new arrays in terms of its arguments. What about describing a sub-array of another array? Indexing provides a means of identifying specific elements of an array. Some people might call this addressing elements of the array.

Given an array A with shape ⍴A and elements ,A, a valid index I into array A is a vector whose length matches ⍴A, stated formally as follows:

⍴I ←→ ⍴⍴A ⍝ Shape of Index matches rank of A 

An index describes the location of an element when arranged according to the shape. That is, an index encodes the position of an element according to the shape. Consider a matrix of shape 5 3 filled with the first 15 natural numbers:

    5 3⍴⍳15
 0  1  2
 3  4  5
 6  7  8
 9 10 11
12 13 14
    ⍳15
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Notice that the elements of ⍳15 correspond to their position in the element vector of 5 3⍴⍳15, expressed notationally as ⍳15 ←→ ,5 3⍴⍳15. It feels awkwards to refer to the element in the third row and second column of a matrix as the 7th element of the matrix. True, the element in row 3 and column 2 does indeed correspond to the 7th element of the array as counted by its ravel (recall that the term ravel means the element vector), but no one wishes to do the necessary mental computation to make this happen. A key advantage to multi-dimensional arrays begins with the ability to reference elements relative to their arrangement according to shape, rather than positionally in the ravel.

Instead of referring to the 7th element in a matrix of shape 5 3, the index 2 1 means the same thing. All indexing and counting in Co-dfns and this blog begins with zero, rather than 1. (A long standing debate concerning the origin of counting, be it 1 or 0, continues to gently ruffle programmer feathers within the APL community, but zero-based indexing holds the crown for most modern computer science concerns, and this series uses an index origin of 0.) Thus, the index 2 1 refers to the element at the third row and second column of the matrix.

All elements of an index must fall within the range described by the corresponding dimension of the shape of the array indexed. That is, the index 2 1 means something for an array of shape 5 3, but refers to a non-existent element in an array of shape 2 2. Such invalid indexes trigger INDEX ERROR in the APL interpreter. The following equivalence formalizes the requirement for elements of an index to fall within valid ranges, where ∧/ means "for all":

∧/(0<I)∧I<⍴A ⍝ Index between 0 and shape of array indexed

Certain APL functions allow an array and valid index into that array to describe the corresponding element indexed in the array. Writing I⌷A gives the scalar element of A indexed by I. To understand this relationship, the following picture helps:

┌→─────────┬─────────────┐
│┌→─┬──┬──┐│┌→──┬───┬───┐│
│↓0 │1 │2 ││↓0 0│0 1│0 2││
│├~→┼~→┼~→┤│├~─→┼~─→┼~─→┤│
││3 │4 │5 │││1 0│1 1│1 2││
│├~→┼~→┼~→┤│├~─→┼~─→┼~─→┤│
││6 │7 │8 │││2 0│2 1│2 2││
│├~→┼~→┼~→┤│├~─→┼~─→┼~─→┤│
││9 │10│11│││3 0│3 1│3 2││
│├~→┼~→┼~→┤│├~─→┼~─→┼~─→┤│
││12│13│14│││4 0│4 1│4 2││
│└~→┴~→┴~→┘↓└~─→┴~─→┴~─→┘↓
└─────────→┴────────────→┘

The array above shows the correspondence between positions in the element vector and the indexes that refer to these positions in a 5 3 matrix. See how the elements are arranged by position in row-major order on the left. Notice the row-major order evident in the progression of the indexes on the right. The upper left hand corner of the matrix is 0 0 while the lower right hand corner will always be (⍴A)-1. In this case, the shape is 5 3 so 4 2≡(⍴A)-1.

The power to generate the right hand side of the above picture rests firmly in your hands already. While ⍳N serves as a nice method for generating natural numbers, the monadic function actually accepts any valid shape as an argument. Given a shape S, the expression ⍳S describes an array of shape S whose elements are the indexes corresponding to the element position. Thus, the above right hand side is a picture displayed by the APL session for ⍳5 3:

    ⍳5 3
┌→──┬───┬───┐
↓0 0│0 1│0 2│
├~─→┼~─→┼~─→┤
│1 0│1 1│1 2│
├~─→┼~─→┼~─→┤
│2 0│2 1│2 2│
├~─→┼~─→┼~─→┤
│3 0│3 1│3 2│
├~─→┼~─→┼~─→┤
│4 0│4 1│4 2│
└~─→┴~─→┴~─→┘

So, indexing into the array 5 3⍴⍳15 using 2 1 should give 7:

    2 1⌷5 3⍴⍳15
7

You now know how to reference any element in an array based on that element's index into the array. Furthermore, a simple exploration of this reveals how to extract the Nth element from any array:

    N⌷,A ⍝ The Nth element of array A

In the above example, it holds that 7⌷,5 3⍴⍳15 ←→ 2 1⌷5 3⍴⍳15. Clearly, now, the expression ⍳S degenerates into ⍳N when S describes a vector. A vector's indexes are natural numbers.

The next session with further explore the interesting relationship between an index and the element corresponding to it.

Please support my work via GitTip.