Ch 6: Indexing

| # 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 =: 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)`
     0  1  2
     3  4  5
     6  7  8

     9 10 11
    12 13 14
    15 16 17

    18 19 20
    21 22 23
    24 25 26
    12 13
    15 16

    21 22
    24 25
    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
    12 13

    21 22
    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
    12 13
    21 22
    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 $ 3 12 11 4
Then, using our index-finding verb `f`, the flattening, amending and rebuilding is shown by:
`M` | `LL =: ,M` | `Z =: 10 f } LL` | `($M) $ Z`
     3 12
    11  4
    3 12 11 4
    3 10 10 4
     3 10
    10  4
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` | `10 f M`
     3 12
    11  4
    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) $ 10 (10 f M) } (, M)`
     3 12
    11  4
     3 10
    10  4
Finally, provided `f` delivers linear indices, then `(})` allows the last expression to be abbreviated as:
`M` | `10 f } M`
     3 12
    11  4
     3 10
    10  4
## 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

Copyright © Roger Stokes 2003. This material may be freely reproduced, provided that this copyright notice is also reproduced.

last updated 17 Mar 2004