
Chapter 6: IndexingIndexing is the name given to selecting of elements of arrays by position. This topic includes selecting elements, rearranging selected elements to form new arrays, and amending, or updating, selected elements of arrays. 6.1 SelectingThe verb { (leftbrace) is called "From". The expression (x { y) selects elements from y according to positions given by x. For example, recall from Chapter 2 that if L is a list, then the positions of items of L are numbered 0 1 and so on. The expression (0 { L) gives the value of the first item of L and 1 { L gives the second item.
The left argument of { is called the "index". 6.1.1 Common Patterns of Selection.Several items may be selected together:
Items selected from L may be replicated and reordered:
An index value may be negative: a value of _1 selects the last item, _2 selects the nexttolast item and so on. Positive and negative indices may be mixed.
A single element of a table at, say, row 1 column 2 is selected with an index (< 1 ; 2).
We can select from a table all elements in specified rows and columns, to produce a smaller table (called a subarray). To select a subarray consisting of, for example rows 1 and 2 and columns 0 and 1, we use an index (< 1 2; 0 1)
A complete row or rows may be selected from a table. Recall that a table is a list of items, each item being a row. Thus selecting rows from tables is just like selecting items from lists.
To select a complete column or columns, a straightforward way is to select all the rows:
but there are other possibilities: see below. 6.1.2 Take, Drop, Head, Behead, Tail, CurtailNext we look at a group of verbs providing some convenient short forms of indexing. There is a builtin verb {. (left brace dot, called "Take"). The first n items of list L are selected by (n {. L)
If we take n items from L with (n {. L), and n is greater than the length of L, the result is padded to length n, with zeros, spaces or empty boxes as appropriate. For example, suppose we require to make a string of exactly 8 characters from a given string, a description of some kind, which may be longer or shorter than 8. If longer, we shorten. If shorter we pad with spaces.
There is a builtin verb }. (rightbrace dot, called "Drop"). All but the first n items of L are selected by (n }. L).
The last n items of L are selected by (n) {. L. All but the last n are selected by (n) }. L
There are abbreviations of Take and Drop in the special case where n=1. The first item of a list is selected by monadic {. (leftbrace dot, called "Head"). All but the first are selected by }. (rightbrace dot, called "Behead").
The last item of a list is selected by monadic {: (leftbrace colon, called "Tail"). All but the last are selected by }: (rightbrace colon, called "Curtail".
6.2 General Treatment of SelectionIt will help to have some terminology. In general we will have an ndimensional array, but consider a 3dimensional array. A single element is picked out by giving a plane number, a rownumber and a columnnumber. We say that the planes are laid out in order along the first axis, and similarly the rows along the second axis, and the columns along the third. There is no special notation for indexing; rather the left argument of { is a data structure which expresses, or encodes, selections and rearrangements. This data structure can be built in any way convenient. What follows is an explanation of how to build it. 6.2.1 Independent SelectionsThe general expression for indexing is of the form index { array. Here index is an array of scalars. Each scalar in index gives rise to a separate independent selection, and the results are assembled together.
6.2.2 Shape of IndexThe shape of the results depends on the shape of index.
The indices must lie within the range #L to (#L)1:
6.2.3 ScalarsEach scalar in index is either a single number or a box (and of course if one is a box, all are.) If the scalar is a single number it selects an item from array.
If the scalar in index is a box however then it contains a list of selectors which are applied to successive axes. To show where a box is used for this purpose, we can use the name SuAx, say, for the box function. SuAx =: < The following example selects from A the element at row 1, column 0.
6.2.4 Selections on One AxisIn a list of selectors for successive axes, of the form (SuAx p , r, c) say, each of p, r and c is a scalar. This scalar is either a number or a box (and if one is boxed, all are). A number selects one thing on its axis: one plane, row or column as appropriate, as in the last example. However, if the selector is a box it contains a list of selections all applicable to the same axis. To show where a box is used for this purpose we can use the name Sel, say, for the box function. Sel =: < For example, to select from A elements at row 1, columns 0 2:
6.2.5 Excluding ThingsInstead of selecting things on a particular axis, we can exclude things, by supplying a list of thingnumbers enclosed in yet another level of boxing. To show where a box is used for this purpose we can use the name Excl, say, for the box function. Excl =: < For example, to select from A elements at row 0, all columns excluding column 1:
We can select all things on a particular axis by excluding nothing, that is, giving an empty list (0$0) as a list of thingnumbers to exclude. For example, to select from A elements at row 1, all columns:
6.2.6 SimplificationsThe expression (Excl 0$0) denotes a boxed empty list. There is a builtin J abbreviation for this, namely (a:) (lettera colon), which in this context we can think of as meaning "all".
If in any index of the form (SuAx p,q,..., z), the last selector z is the "all" form, (Sel (Excl 0$0)) or (Sel a:), then it can be omitted.
If in any index of the form (SuAx (Sel p),(Sel q),...), the "all" form is entirely absent, then the index can be abbreviated to (SuAx p;q;...). For example, to select elements at row 1, columns 0 and 2:
Finally, as we have already seen, if selecting only one thing on each axis, a simple unboxed list is sufficient. For example to select the element at row 1, column 2:
6.2.7 Shape of the ResultSuppose that B is a 3dimensional array: B =: i. 3 3 3 and we define p to select planes along the first axis of B, and r to select rows along the second axis, and c to select columns along the third axis: p =: 1 2 r =: 1 2 c =: 0 1 We see that, selecting with p;r;c, the shape of the result R is the concatenation of the shapes of p, r and c
B is 3dimensional, and so is R. As we would expect, this concatenationofshapes holds when a selector (r, say} is a list of length one:
and the concatenationofshapes holds when selector r is a scalar:
In this last example, r is a scalar, so the shape of r is an empty list, and so the axis corresponding to r has disappeared, and so the result T is 2dimensional. 6.3 Amending (or Updating) ArraysSometimes we need to compute an array which is the same as an existing array except for new values at a comparatively small number of positions. We may speak of 'updating' or 'amending' an array at selected positions. The J function for amending arrays is } (right brace, called "Amend"). 6.3.1 Amending with an IndexTo amend an array we need three things:
newvalues index } original For example: to amend list L to replace the first item (at index 0) with '*':
} is an adverb, which takes index as its argument to yield the dyadic amending verb (index }). ReplaceFirst =: 0 } '*' ReplaceFirst L *bcdef (index }) is a verb like any other, dyadic and yielding a value in the usual way. Therefore to change an array by amending needs the whole of the result to be reassigned to the old name. Thus amendment often takes place on the pattern: A =: new index } A The J system ensures that this is an efficient computation with no unnecessary movement of data. To amend a table at row 1 column 2, for example:
To amend multiple elements, a list of new values can be supplied, and they are taken in turn to replace a list of values selected by an index
6.3.2 Amending with a VerbSuppose that y is a list of numbers, and we wish to amend it so that all numbers exceeding a given value x are replaced by x. (For the sake of this example, we here disregard the builtin J verb (<.) for this function.) The indices at which y is to be amended must be computed from x and y. Here is a function f to compute the indices: f =: 4 : '(y. > x.) # (i. # y.)'
The amending is done, in the way we have seen above, by supplying indices of (x f y):
The "Amend" adverb } allows the expression (x (x f y) } y) to be abbreviated as (x f } y).
Since } is an adverb, it can accept as argument either the indices (x f y) or the verb f. cap =: f } 10 cap 8 9 10 11 8 9 10 10 Note that if verb f is to be supplied as argument to adverb }, then f must be a dyad, although it may ignore x or y. 6.3.3 Linear IndicesWe have just looked at amending lists with a verb. The purpose of the verb is to find the places at which to amend, that is, to compute from the values in a list the indices at which to amend. With a table rather than a list, the indices would have to be 2 dimensional, and the task of the verb in constructing the indices would be correspondingly more difficult. It would be easier to flatten a table into a linear list, amend it as a list, and rebuild the list into a table again. For example, suppose we have a table: M =: 2 2 $ 3 12 11 4 Then, using our indexfinding verb f, the flattening, amending and rebuilding is shown by:
However, there is a better way. First note that our indexfinding verb f takes as argument, not M but (LL =: , M). Thus information about the original shape of M is not available to the indexfinder f. In this example, this does not matter, but in general we may want the indexfinding to depend upon both the shape and the values in M. It would be better if f took the whole of M as argument. In this case f must do its own flattening. Thus we redefine f: f =: 4 : 0 y. =. , y. (y. > x.) # (i. # y.) )
Now the index finder f takes an array as argument, and delivers indices into the flattened array, socalled "linear indices". The amending process, with this new f, is shown by:
Finally, provided f delivers linear indices, then (}) allows the last expression to be abbreviated as:
6.4 Tree IndexingSo far we have looked at indexing into rectangular arrays. There is also a form of indexing into boxed structures, which we can picture as "trees" having branches and leaves. For example: branch =: < leaf =: < branch0 =: branch (leaf 'J S'),(leaf 'Bach') branch1 =: branch (leaf 1), (leaf 2), (leaf 1777) tree =: branch0,branch1 tree +++ +++++++ J SBach121777 +++++++ +++ Then data can be fetched from the tree by specifying a path from the root. The path is a sequence of choices, given as left argument to the verb {:: (leftbrace colon colon,called "Fetch") The path 0 will fetch the first branch, while the path 0;1 fetches the second leaf of the first branch:
The monadic form {:: tree is called the "Map" of tree. it has the same boxed structure as tree and shows the path to each leaf. {:: tree +++ +++++++ +++++++++++++++ 0001101112 +++++++++++++++ +++++++ +++ This is the end of Chapter 6. 
Copyright © Roger Stokes 2001. This material may be freely reproduced, provided that this copyright notice is also reproduced.
last updated 4 Sep 01