>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  Help  Learning J

Chapter 6: Indexing

Indexing 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 Selecting

The verb { (left-brace) is called "From". The expression (x { y) selects elements from y according to positions given by x. For example, recall from Chapter 02 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.

L =: 'abcdef' 0 { L 1 { L
abcdef a b

The left argument of { is called the "index".

6.1.1 Common Patterns of Selection.

Several items may be selected together:

L 0 2 4 { L
abcdef ace

Items selected from L may be replicated and re-ordered:

L 5 4 4 3 { L
abcdef feed

An index value may be negative: a value of _1 selects the last item, _2 selects the next-to-last item and so on. Positive and negative indices may be mixed.

L _1 { L _2 1 { L
abcdef f eb

A single element of a table at, say, row 1 column 2 is selected with an index (< 1 ; 2).

T =: 3 3 $ 'abcdefghi' (< 1 ; 2) { T
abc
def
ghi
f

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)

T (< 1 2;0 1) { T
abc
def
ghi
de
gh

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.

T 1 { T 2 1 { T
abc
def
ghi
def ghi
def

To select a complete column or columns, a straightforward way is to select all the rows:

T (< 0 1 2 ; 1 ){ T
abc
def
ghi
beh

but there are other possibilities: see below.

6.1.2 Take, Drop, Head, Behead, Tail, Curtail

Next we look at a group of verbs providing some convenient short forms of indexing. There is a built-in verb {. (left brace dot, called "Take"). The first n items of list L are selected by (n {. L)

L 2 {. L
abcdef ab

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.

s =: 'pasta' # s z =: 8 {. s # z
pasta 5 pasta    8

There is a built-in verb }. (right-brace dot, called "Drop"). All but the first n items of L are selected by (n }. L).

L 2 }. L
abcdef cdef

The last n items of L are selected by (-n) {. L. All but the last n are selected by (-n) }. L

L _2 {. L _2 }. L
abcdef ef abcd

There are abbreviations of Take and Drop in the special case where n=1. The first item of a list is selected by monadic {. (left-brace dot, called "Head"). All but the first are selected by }. (right-brace dot, called "Behead").

L {. L }. L
abcdef a bcdef

The last item of a list is selected by monadic {: (left-brace colon, called "Tail"). All but the last are selected by }: (right-brace colon, called "Curtail".

L {: L }: L
abcdef f abcde

6.2 General Treatment of Selection

It will help to have some terminology. In general we will have an n-dimensional array, but consider a 3-dimensional array. A single element is picked out by giving a plane- number, a row-number and a column-number. 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 Selections

The 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.

L 0 1 { L
abcdef ab

6.2.2 Shape of Index

The shape of the results depends on the shape of index.

L index =: 2 2 $ 2 0 3 1 index { L
abcdef 2 0
3 1
ca
db

The indices must lie within the range -#L to (#L)-1:

L #L _7 { L 6 { L
abcdef 6 error error

6.2.3 Scalars

Each 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.

A =: 2 3 $ 'abcdef' 1 { A
abc
def
def

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.

A (SuAx 1 0) { A
abc
def
d

6.2.4 Selections on One Axis

In 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:

A (SuAx (Sel 1), (Sel 0 2)) { A
abc
def
df

6.2.5 Excluding Things

Instead of selecting things on a particular axis, we can exclude things, by supplying a list of thing-numbers 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:

A (SuAx (Sel 0), (Sel (Excl 1))) { A
abc
def
ac

We can select all things on a particular axis by excluding nothing, that is, giving an empty list (0$0) as a list of thing-numbers to exclude. For example, to select from A elements at row 1, all columns:

A (SuAx (Sel 1),(Sel (Excl 0$0))) { A
abc
def
def

6.2.6 Simplifications

The expression (Excl 0$0) denotes a boxed empty list. There is a built-in J abbreviation for this, namely (a:) (letter-a colon, called "Ace"), which in this context we can think of as meaning "all".

A (SuAx (Sel 1),(Sel a:)) { A
abc
def
def

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.

A (SuAx (Sel 1),(Sel a:)) {A (SuAx (Sel 1)) {A
abc
def
def def

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:

A (SuAx (Sel 1),(Sel 0 2)) {A (SuAx 1;0 2) {A
abc
def
df df

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:

A (SuAx 1;2) { A (SuAx 1 2) { A
abc
def
f f

6.2.7 Shape of the Result

Suppose that B is a 3-dimensional array:
   B =: 10 + 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 R =: (< p;r;c) { B $ R ($p),($r),($c)
10 11 12
13 14 15
16 17 18

19 20 21
22 23 24
25 26 27

28 29 30
31 32 33
34 35 36
22 23
25 26

31 32
34 35
2 2 2 2 2 2

B is 3-dimensional, and so is R. As we would expect, this concatenation-of-shapes holds when a selector (r, say) is a list of length one:

r =: 1 $ 1 S =: (< p;r;c){B $ S ($p),($r),($c)
1 22 23

31 32
2 1 2 2 1 2

and the concatenation-of-shapes holds when selector r is a scalar:

r =: 1 T =: (< p;r;c){B $ T ($p),($r),($c) $ r
1 22 23
31 32
2 2 2 2  

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 2-dimensional.

6.3 Amending (or Updating) Arrays

Sometimes 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 Index

To amend an array we need three things:
  • the original array
  • a specification of the position(s) at which the original is to be amended. This can be an index exactly like the index we have seen above for selection with {.
  • new values to replace existing elements at specified positions.
Consequently the J expression to perform an amendment may have the general form:
        newvalues index } original
For example: to amend list L to replace the first item (at index 0) with '*':

L new=:'*' index=:0 new index } L
abcdef * 0 *bcdef

} 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:

A '*' (< 1 2) } A
abc
def
abc
de*

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

L '*#' 1 2 } L
abcdef a*#def

6.3.2 Amending with a Verb

Suppose 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 built-in 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)'
   

X =: 100 Y =: 98 102 101 99 Y > X X f Y
100 98 102 101 99 0 1 1 0 1 2

The amending is done, in the way we have seen above, by supplying indices of (X f Y):

Y X (X f Y) } Y
98 102 101 99 98 100 100 99

The "Amend" adverb } allows the expression (X (X f Y) } Y) to be abbreviated as (X f } Y).

X (X f Y) } Y X f } Y
98 100 100 99 98 100 100 99

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 Indices

We 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 $ 13 52 51 14
Then, using our index-finding verb f, the flattening, amending and rebuilding is shown by:

M LL =: ,M Z =: 50 f } LL ($M) $ Z
13 52
51 14
13 52 51 14 13 50 50 14 13 50
50 14

However, there is a better way. First note that our index-finding verb f takes as argument, not M but (LL =: , M). Thus information about the original shape of M is not available to the index-finder f. In this example, this does not matter, but in general we may want the index-finding 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)
)
   

M 50 f M
13 52
51 14
1 2

Now the index finder f takes an array as argument, and delivers indices into the flattened array, so-called "linear indices". The amending process, with this new f, is shown by:

M ($M) $ 50 (50 f M) } (, M)
13 52
51 14
13 50
50 14

Finally, provided f delivers linear indices, then (}) allows the last expression to be abbreviated as:

M 50 f } M
13 52
51 14
13 50
50 14

6.4 Tree Indexing

So 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 S|Bach|||1|2|1777||
|+---+----+|+-+-+----+|
+----------+----------+
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 {:: (left-brace 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:

0 {:: tree (0;1) {:: tree
+---+----+
|J S|Bach|
+---+----+
Bach

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
+-------------+-------------------+
|+-----+-----+|+-----+-----+-----+|
||+-+-+|+-+-+|||+-+-+|+-+-+|+-+-+||
|||0|0|||0|1|||||1|0|||1|1|||1|2|||
||+-+-+|+-+-+|||+-+-+|+-+-+|+-+-+||
|+-----+-----+|+-----+-----+-----+|
+-------------+-------------------+
This is the end of Chapter 6.

NEXT
Table of Contents
Index


The examples in this chapter were executed using J version j701/beta/2010-11-24/22:45. This chapter last updated 22 Dec 2010
Copyright © Roger Stokes 2010. This material may be freely reproduced, provided that this copyright notice is also reproduced.


>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  Help  Learning J