Fifty Shades of J/Chapter 1

From J Wiki
Jump to: navigation, search

Table of Contents ... Glossary ... Next Chapter

every, each, and a little bit of rank

Principal Topics

& (compose) &. (under) @ (atop). ” (rank conjunction) , fill characters, ragged arrays, heterogenous arrays, inner product.

Every and Each

In APL2 there was just one primitive symbol, double-dot (¨) for ‘each’ – the ‘pepper’ effect is well imprinted on those with long memories, although that is not what APL looks like these days. In spite of J being considerably richer in primitives than APL, it does not include ‘each’ as a primitive. Instead J recognizes that there are two types of ‘each’, both defined as adverbs in the standard vocabulary and both using Open (>)

   every=.&>        NB. uses compose
   each=.&.>        NB. uses under

The definitions of the conjunctions & and & giving rise to the verbs u∧v and u&.v in mathematical terms as (uv) and (v⁻¹uv) show that the rule:

   (f every) -: >@(f each)

is completely general, and so only one of ‘each’ and ‘every’ is ever logically necessary. ‘each’ has the general merit of greater compactness through generating what APL2 users would recognise as ragged arrays. On the other hand ‘every’ has the merit of avoiding, or at least reducing, boxing on display, but often at the expense of requiring greater numbers of fill characters to achieve global homogeneity. In writing J it can be handy to have a ‘rule of thumb’ appreciation of how ‘each’ and ‘every’ work without having to consider the semantic details of box and open at every point of use. Thinking in terms of lists is helpful in using ‘each’ and ‘every’ effectively, as is sensitivity to the ways in which argument rank works. J has a wealth of algorithms pre-implemented for its users within its interpreters. Effective use of these requires an understanding that Data = Values + Structure and that ‘each’ and ‘every’ allow algorithms to apply to different levels of the structure. For example, given

   h=.i.2 3        NB. two 3-lists, rank = 2

compare the following

   h,every 6 7      NB. one 2-list, items=3 2-lists, rank=3
0 6
1 6
2 6

3 7 
4 7 
5 7

   h,each 6 7       NB. 2 3-lists, items=2-lists, rank=2
┌───┬───┬───┐
│0 6│1 6│2 6│
├───┼───┼───┤
│3 7│4 7│5 7│
└───┴───┴───┘

Applying the general rule above h,every 6 7 is identical to >h,each 6 7, or to put it in another way, the two displays above show the same six 2-lists, in one case individually boxed, in the other integrated into a structure of higher rank.

Using either 'each' or 'every' with a dyadic verb often requires the user to box one of the arguments to achieve a desired result through bringing about correct argument matching. Often this consists of a simple boxing of one of the arguments as in:

   x=.6 7;8;9 10 11 12
   (<h),each x     NB. left rank 0, right rank 1, result rank 1
┌─────┬─────┬──────────┐
│0 1 2│0 1 2│0  1  2  0│
│3 4 5│3 4 5│3  4  5  0│
│6 7 0│8 8 8│9 10 11 12│
└─────┴─────┴──────────┘

The result is a 3-list of scalars (and so of rank 1) each made from the same scalar (<h) joined to each item of a 3-list, with everything opened and boxed following the (v⁻¹uv) rule which defines &. (under). There is a local fill character in the first box, a local scalar expansion in the second, and the third containing two fill characters in the final column has a different shape ($) from the other two. Compare this with:

   (<h),every x    NB. left rank 0, right rank 1, result rank 3
0   1   2   0
3   4   5   0
6   7   0   0

0   1   2   0
3   4   5   0
8   8   8   0

0   1   2   0
3   4   5   0
9  10  11  12

where there is no v⁻¹ boxing. Again the result is a 3-list, but now not of scalars but of three filled lists, each of which is a 4-list of scalars after filling. APL2 talked about ‘ragged’ and ‘heterogeneous’ arrays – a more appropriate differentiation in J is between locally- and globally-filled lists, corresponding to each and every. Using "0 as an alternative gives a result rank between those of every and each :

  (<h),"0 x      NB. left rank 0, right rank 1, result rank 2
┌─────┬──────────┐
│0 1 2│6 7       │
│3 4 5│          │
├─────┼──────────┤
│0 1 2│8         │
│3 4 5│          │
├─────┼──────────┤
│0 1 2│9 10 11 12│
│3 4 5│          │
└─────┴──────────┘

Here the scalar left argument gives rise to scalar replication, and the result is a 3-list of non-homogeneous 2-lists without fill characters, that is, it is only the display which is rectangular not the result object itself, as is made explicit by

   $each (<h),"0 x
┌───┬─┐
│2 3│2│
├───┼─┤
│2 3│ │
├───┼─┤
│2 3│4│
└───┴─┘

In order to avoid monotonous repetition, subsequent examples will use just one of each or every, the other case being covered by the general rule (f every) -: (>f each) . Consideration of rank is almost always a preliminary to well-considered usage of each. There are no overall rank rules because these depend on the semantics of each individual f . In the next set of examples three figures in square brackets in a comment give the left, right and result ranks of the verb |. or |.each .

Consider first the basic case of the verb Rotate (|.) with a rank 1 argument on the left and a rank 2 argument on the right:

   0 1|.h        NB. 0-rotate rows ,: 1-rotate cols    [1 2 2]
1 2 0
4 5 3

Applying each with box on either right or left changes the ranks:

    0 1 |.each <h  NB. 0-rotate on h ; 1-rotate on h    [1 0 1]
┌─────┬─────┐
│0 1 2│3 4 5│
│3 4 5│0 1 2│
└─────┴─────┘
   (<0 1)|.each h NB. (<0 1)-rotate on items of h     [0 2 2]
┌─┬─┬─┐
│0│1│2│
├─┼─┼─┤
│3│4│5│
└─┴─┴─┘

Between these extremes is the possibly more useful case of ‘left rank 1, right rank 1’:

   0 1|.each<"1 h   NB. 0-rotate 1st row;1-rotate 2nd     [1 1 1]
┌─────┬─────┐
│0 1 2│4 5 3│
└─────┴─────┘

Next, given the laminated rank 3 object:

   ]hlam=.(i.2 3),:10+i.2 3
 0  1  2
 3  4  5

10 11 12 
13 14 15

here are the effects of four rather similar expressions, along with annotated descriptions which attempt to explain the differences between them. What is the best medium for such descriptions? Why J, of course, hence the comments which follow each of the four executable lines supply matching equivalent statements

   (<0 1)|.each <"2 hlam NB. (0 1|.h);(0 1|.h+10)       [0 1 1]
┌─────┬────────┐
│1 2 0│11 12 10│
│4 5 3│14 15 13│
└─────┴────────┘
   0 1|. each <"2 hlam    NB. (0|.h);(1|.h+10)           [1 1 1]
┌─────┬────────┐
│0 1 2│13 14 15│
│3 4 5│10 11 12│
└─────┴────────┘
   0 1|. each <"1 hlam    NB. (0|. each H<"1 h),:(1|. each <"1 h+10)
┌────────┬────────┐
│0 1 2   │3 4 5   │
├────────┼────────┤
│11 12 10│14 15 13│
└────────┴────────┘

This example is also equivalent to 2 2$0 0 1 1|. each H,<"1 hlam , since ,<"1 hlam is a 4-list whose items are 3-lists such as 0 1 2.

The next example illustrates how "0 means apply a rotate at the scalar level which is necessarily a ‘do nothing’ operation.

   (0 1)|."0<"2 hlam     NB. equivalent to <"2 hlam     [1 1 1]
┌─────┬────────┐
│0 1 2│10 11 12│
│3 4 5│13 14 15│
└─────┴────────┘

A further set of examples illustrates what happens with characters. g is a pair of 2-lists and thus has the same shape as h, only its items are characters lists rather numbers.

   ]g=.2 3$'ant';'bee';'cat';'dog';'elk';'frog'
┌───┬───┬────┐
│ant│bee│cat │
├───┼───┼────┤
│dog│elk│frog│
└───┴───┴────┘

Where items are characters lists, there are necessarily possible ambiguities between genuine space characters and space fill characters, something which is clarified in

      1 |. each g             NB. 1-rotate items   ranks=[0 2 2]
┌───┬───┬────┐
│nta│eeb│atc │
├───┼───┼────┤
│ogd│lke│rogf│
└───┴───┴────┘

The next example shows simultaneous opening of both arguments followed by v⁻¹ boxing:

   (<0 1)|. each <g           NB. <0 1|.g,     ranks=[0 0 0]
┌──────────────┐
│┌───┬────┬───┐│
││bee│cat │ant││
│├───┼────┼───┤│
││elk│frog│dog││
│└───┴────┴───┘│
└──────────────┘

The next example is one in which the result rank is less than an argument rank:

   0 1|. each <g              NB. (<0|.g),(<1|.g),ranks=[1 0 0]
┌──────────────┬──────────────┐
│┌───┬───┬────┐│┌───┬───┬────┐│
││ant│bee│cat │││dog│elk│frog││
│├───┼───┼────┤│├───┼───┼────┤│
││dog│elk│frog│││ant│bee│cat ││
│└───┴───┴────┘│└───┴───┴────┘│
└──────────────┴──────────────┘

the final example in this set the shapes of the items within the two outer boxes are not identical, thus resolving an ambiguity between fill- and genuine space characters which each would not have shown:

   0 1|. each <"1 g         NB.(<0|.0{g),(<1|.1{g),ranks=[1 1 1]
┌─────────────┬──────────────┐
│┌───┬───┬───┐│┌───┬────┬───┐│
││ant│bee│cat│││elk│frog│dog││
│└───┴───┴───┘│└───┴────┴───┘│
└─────────────┴──────────────┘

However, given that each by definition reduces one level of boxing in every case, it often gives less fussy-looking results than each where character lists are involved.

The examples so far have been chosen to illustrate the principles of each and every. An example of a practical problem involving each is that of evaluating linear expressions such as x + 2y - z over separate ranges of values of their variables. The results in this simple example are easy to check.

   t3=.1 2;3 4 5;6            NB. x={1,2} y={3 4 5} z={6}
   {t3                        NB. catalog gives all combinations
┌─────┬─────┬─────┐
│1 3 6│1 4 6│1 5 6│
├─────┼─────┼─────┤
│2 3 6│2 4 6│2 5 6│
└─────┴─────┴─────┘
   ip=.+/ .* every            NB. 6 inner products with 1 2 _1
   ({t3)ip <1 2 _1
1 3 5
2 4 6
   ip=.+/ .* each
   ({t3)ip <1 2 _1
┌─┬─┬─┐
│1│3│5│
├─┼─┼─┤
│2│4│6│
└─┴─┴─┘

The advent of ‘each’ (¨) and ragged arrays in APL2 breathed new life into that language. J deals with such matters more subtly by forcing choices between the two possibilities ‘each’ or ‘every’. In broad terms each allows raggedness and reduces homogeneity to a local level, every reduces boxing at the cost of imposing greater homogeneity through globally applied fill characters.

Code Summary

every=.&>
each =.&.>
ip=.+/ .*

Script

File:Fsojc01.ijs