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

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, ({: - {.)

smf =: {: - {. smf 1 4
{: - {. 3

   diff =: 2 & (smf\)

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


The examples in this chapter were executed using J version 601 beta. This chapter last updated 14 Jun 2006 .
Copyright © Roger Stokes 2006. This material may be freely reproduced, provided that this copyright notice is also reproduced.


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