Ch 17: Patterns of Application

| # Chapter 17: Patterns of Application In this chapter we look at applying a function to an array in various patterns made up of selected elements of the array. ## 17.1 Scanning ### 17.1.1 Prefix Scanning In the expression `(f \ y)` the result is produced by applying verb `f` to successively longer leading sections ("prefixes") of `y`. Choosing `f` as the box verb (`<`) gives easily visible results.
`y =: 'abcde'` | `< \ y`
    abcde
    +-+--+---+----+-----+
    |a|ab|abc|abcd|abcde|
    +-+--+---+----+-----+
Cumulative sums of a numeric vector can be produced:
       +/ \ 0 1 2 3
    0 1 3 6
Various effects can be produced by scanning bit-vectors. The following example shows "cumulative OR", which turns on all bits after the first 1-bit.
       +./\ 0 1 0 1 0
    0 1 1 1 1
### 17.1.2 Infix Scanning In the expression `(x f \ y)` the verb `f` is applied to successive sections ("infixes") of `y`, each of length `x`.
`z =: 1 4 9 16` | `2 < \ z`
    1 4 9 16
    +---+---+----+
    |1 4|4 9|9 16|
    +---+---+----+
If `x` is negative, then the sections are non-overlapping, in which case the last section may not be full-length. For example:
`z` | `_3 < \ z`
    1 4 9 16
    +-----+--+
    |1 4 9|16|
    +-----+--+
We can compute the differences between succesive items, by choosing 2 for the section-length, and applying to each section a verb "second-minus-first", that is, `({: - {.)`
`f =: {: - {.` | `f 1 4`
    {: - {.
    3
       diff =: 2 & (f\)
`,. z` | `,. diff z` | `,. diff diff z`
     1
     4
     9
    16
    3
    5
    7
    2
    2
### 17.1.3 Suffix Scanning In the expression `(f \. y )` the result is produced by applying `f` to successively shorter trailing sections ("suffixes") of y .
`y` | `< \. y`
    abcde
    +-----+----+---+--+-+
    |abcde|bcde|cde|de|e|
    +-----+----+---+--+-+
### 17.1.4 Outfix In the expression `(x f \. y)` the verb `f` is applied to the whole of `y` with successive sections removed, each removed section being of length `x`. If `x` is negative, then the removed sections are non-overlapping, in which case the last removed section may not be full-length.
`y` | `2 < \. y` | `_2 < \. y`
    abcde
    +---+---+---+---+
    |cde|ade|abe|abc|
    +---+---+---+---+
    +---+---+----+
    |cde|abe|abcd|
    +---+---+----+
## 17.2 Cutting The conjunction `;.` (semicolon dot) is called "Cut". If `u` is a verb and `n` a small integer, then `(u ;. n)` is a verb which applies `u` in various patterns as specified by `n`. The possible values for `n` are `_3 _2 _1 0 1 2 3`. We will look some but not all of these cases. ### 17.2.1 Reversing In the expression `(u ;. 0 y)`, the verb `u` is applied to `y` reversed along all axes. In the following example, we choose `u` to be the identity-verb (`[`).
`M =: 3 3 $ 'abcdefghi'` | `[ ;. 0 M`
    abc
    def
    ghi
    ihg
    fed
    cba
### 17.2.2 Blocking Given an array, we can pick out a smaller subarray inside it, and apply a verb to just the subarray. The subarray is specified by a two-row table. In the first row is the index of the cell which will become the first of the subarray. In the second row is the shape of the subarray. For example, to specify a subarray starting at row `1` column `1` of the original array, and of shape `2 2`, we write:
       spec =: 1 1 ,: 2 2
Then we can apply, say, the identity-verb `([)` to the specified subarray as follows:
`M` | `spec` | `spec [ ;. 0 M`
    abc
    def
    ghi
    1 1
    2 2
    ef
    hi
The general scheme is that for a verb `u`, the expression `(x u ;. 0 y)` applies verb `u` to a subarray of `y` as specified by `x`. In the specifier `x`, a negative value in the shape (the second row) will cause reversal of the elements of `M` along the corresponding axis. For example:
       spec =: 1 1 ,: _2 2
`M` | `spec` | `spec [ ;. 0 M`
    abc
    def
    ghi
     1 1
    _2 2
    hi
    ef
### 17.2.3 Fretting Suppose that we are interested in dividing a line of text into separate words. Here is an example of a line of text:
       y =: 'what can be said'
For the moment, suppose we regard a word as being terminated by a space. (There are other possibilities, which we will come to.) Immediately we see that in `y` above, the last word `'said'` is not followed by a space, so the first thing to do is to add a space at the end:
       y =: y , ' '
Now if `u` is a verb, and `y` ends with a space, the expression `(u ;. _2 y)` will apply verb `u` separately to each space-terminated word in `y`. For example we can identify the words in `y` by applying `<`, the box function:
`y` | `< ;. _2 y`
    what can be said
    +----+---+--+----+
    |what|can|be|said|
    +----+---+--+----+
We can count the letters in each word by applying the `#` verb:
`y` | `# ;. _2 y`
    what can be said
    4 3 2 4
The meaning of `_2` for the right argument of `;.` is that the words are to be terminated by occurrences of the last character in `y` (the space), and furthermore that the words do not include the spaces. More generally, we say that a list may be divided into "intervals" marked by the occurrence of "frets". The right argument `(n)` of `;.` specifies how we choose to define intervals and frets as follows. There are four cases. n = 1 : Each interval begins with a fret. The first item of `y` is taken to be a fret, as are any other items of `y` equal to the first. Intervals include frets. n = _1 : As for `(n = 1)` except that intervals exclude frets. n = 2 : Each interval ends with a fret. The last item of `y` is taken to be a fret, as are any other items of `y` equal to the last. Intervals include frets. n = _2 : As for `(n = 2)`, except that intervals exclude frets. For example, the four cases are shown by:
       z =: 'abdacd'
`z` | `< ;. 1 z` | `< ;. _1 z` | `< ;. 2 z` | `< ;. _2 z`
    abdacd
    +---+---+
    |abd|acd|
    +---+---+
    +--+--+
    |bd|cd|
    +--+--+
    +---+---+
    |abd|acd|
    +---+---+
    +--+--+
    |ab|ac|
    +--+--+
For another example, here is a way of entering tables of numbers. We enter a table row by row following `0 : 0`
          T =: 0 : 0
     1   2  3
     4   5  6
    19  20 21
    )
`T` is a character-string with 3 embedded line-feed characters, one at the end of each line:
`$ T` | `+/ T = LF`
    30
    3
The idea now is to cut `T` into lines. Each line is a character-string representing a J expression (for example the characters `'1 2 3'`). Such character-strings can be evaluated by applying the verb `".` (double-quote dot, "Do" or "Execute"). The result is, for each line, a list of 3 numbers.
`TABLE =: (". ;. _2) T` | `$ TABLE`
     1  2  3
     4  5  6
    19 20 21
    3 3
The verb `(". ;. _2)` was introduced as the utility-function `ArrayMaker` in Chapter 2. ### 17.2.4 Punctuation For processing text it would be useful to regard words as terminated by spaces or by various punctuation-marks. Suppose we choose our frets as any of four characters:
       frets =: ' ?!.'
Given some text we can compute a bit-vector which is true at the location of a fret:
`t =: 'How are you?'` | `v =: t e. frets`
    How are you?
    0 0 0 1 0 0 0 1 0 0 0 1
Here we make use of the built-in verb `e.` ("Member"). The expression `x e. y` evaluates to true if `x` is a member of the list `y`. Now the bitvector `v` can be used to specify the frets:
`t` | `v` | `v < ;. _2 t`
    How are you?
    0 0 0 1 0 0 0 1 0 0 0 1
    +---+---+---+
    |How|are|you|
    +---+---+---+
For another example, consider cutting a numeric vector into intervals such that each is in ascending sequence, that is, an item less than the previous must start a new interval. Suppose our data is:
       data =: 3 1 4 1 5 9
Then a bitvector can be computed by scanning infixes of length 2, applying `>/` to each pair of items. Where we get `1`, the second item of the pair is the beginning of a new interval. We make sure the first item of all is 1.
         bv =: 1 , 2 >/ \ data
`data` | `data ,: bv` | `bv < ;. 1 data`
    3 1 4 1 5 9
    3 1 4 1 5 9
    1 1 0 1 0 0
    +-+---+-----+
    |3|1 4|1 5 9|
    +-+---+-----+
### 17.2.5 Word Formation There is a built-in function `;:` (semicolon colon, called "Word Formation"). It analyses a string as a J expression, according to the rules of the J language, to yield a boxed list of strings, the separate constituents of the J expression. For example:
`y =: 'z =: (p+q) - 1'` | `;: y`
    z =: (p+q) - 1
    +-+--+-+-+-+-+-+-+-+
    |z|=:|(|p|+|q|)|-|1|
    +-+--+-+-+-+-+-+-+-+
### 17.2.6 Lines in Files Let us begin by creating a file, to serve in the examples which follow. (See Chapter 26 for details of file-handling functions).
       text =: 0 : 0
    What can be said
    at all
    can be said
    clearly.
    )

       text (1 !: 2) < 'c:\foo.txt'
Now, if we are interested in cutting a file of text into lines, we can read the file into a string-variable and cut the string. On the assumption that each line ends with a line-terminating character, then the last character in the file will be our fret. Here is an example.
       string =: (1 !: 1) < 'c:\foo.txt'  NB. read the file

       lines =: (< ;. _2) string          NB. cut into lines

       lines
    +----------------+------+-----------+--------+
    |What can be said|at all|can be said|clearly.|
    +----------------+------+-----------+--------+
There are two things to be aware of when cutting files of text into lines. Firstly, in some systems lines in a file are terminated by a single line-feed character (`LF`). In other systems each line may be terminated by the pair of characters carriage-return (`CR`) followed by line-feed (`LF`). J follows the convention of the single `LF` regardless of the system on which J is running. However, we should be prepared for `CR` characters to be present. To get rid of `CR` characters from `string`, we can reduce it with the bitvector `(string notequal CR)`, where `notequal` is the built-in verb `~:`, thus:
       string =: (string ~: CR) # string
Secondly, depending on how the file of text was produced, we may not be able to guarantee that its last line is actually terminated. Thus we should be prepared to supply the fret character (`LF`) ourselves if necessary, by appending `LF` to the string. A small function to tidy up a string, by supplying a fret and removing `CR` characters, can be written as:
       tidy =: 3 : 0
    y. =. y. , (LF ~: {: y.) # LF   NB. supply LF
    (y. ~: CR) # y.                 NB. remove CR
    )

       (< ;. _2) tidy string
    +----------------+------+-----------+--------+
    |What can be said|at all|can be said|clearly.|
    +----------------+------+-----------+--------+
### 17.2.7 Tiling In the expression `(x u ;. 3 y)` the verb `u` is applied separately to each of a collection of subarrays extracted from `y`. These subarrays may be called tiles. The size and arrangement of the tiles are defined by the value of `x`. Here is an example. Suppose that `y` is
       y =: 4 4 $ 'abcdefghijklmnop'
and our tiles are to be of shape `2 2`, each offset by 2 along each axis from its neighbour. That is, the offset is to be `2 2`. We specify the tiling with a table: the first row is the offset, the second the shape'
       spec =: > 2 2 ; 2 2  NB.  offset, shape
and so we see
`y` | `spec` | `spec < ;. 3 y`
    abcd
    efgh
    ijkl
    mnop
    2 2
    2 2
    +--+--+
    |ab|cd|
    |ef|gh|
    +--+--+
    |ij|kl|
    |mn|op|
    +--+--+
The specified tiling may leave incomplete pieces ("shards") at the edges. Shards can be included or excluded by giving a right argument to "Cut" of `3` or `_3` .
       sp =: > 3 3 ; 3 3
`y` | `sp` | `sp < ;. 3 y` | `sp < ;. _3 y`
    abcd
    efgh
    ijkl
    mnop
    3 3
    3 3
    +---+-+
    |abc|d|
    |efg|h|
    |ijk|l|
    +---+-+
    |mno|p|
    +---+-+
    +---+
    |abc|
    |efg|
    |ijk|
    +---+
This is the end of Chapter 17.

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 5 Aug 2003