Some Uses of { and }

Roger Hui

I.P. Sharp Associates Limited
2 First Canadian Place. Suite 1900
Toronto, Ontario M5X 1E3
 

We believe that the design of APL was also affected in important respects by a number of procedures and circumstances. Firstly, from its inception APL has been developed by using it in a succession of areas. This emphasis on application clearly favors practicality and simplicity. The treatment of many different areas fostered generalization …

    — Falkoff and Iverson, The Design of APL
 


0. Introduction

This paper explores uses of the new primitives all, from, select, and merge ({⍵, ⍺{⍵, v}⍵ and ⍺v}⍵). Facilities of K.E. Iverson’s A Dictionary of APL [1986] are exploited. Brief explanations of the less familiar aspects of the notation are in Appendix A.
 

1. A Few Applications

Examples here illustrate the meaning of { } . Some readers may wish to skip to Section 2, which defines { } directly, before returning.

1.1 Short Examples

0{x   The first element of vector x
¯1{x   The last element of x
0 ¯1{x   The first and last element of x
0{m   The first row of matrix m
¯1{m   The last row of m
¯1 0{m   The last and first row of m
¯2 0{a   The penultimate and first major cells of a ;
two ¯1-cells of a
(<i,j){m   The element at row i & column j of m ; m[i;j]
(<i⊃j){m   The element at row i & column j of m
(<(<i),<j){m   The element at row i & column j of m
j{i{m   The element at row i & column j of m
i{j{⍤1 m   The element at row i & column j of m
(<∘⊃¯1){m   The last column of m ; ∘ ←→ <''
¯1{⍉m   The last column of m
¯1{⍤1 m   The last column of m
(<0 0 ¯1 ¯1){a   A ¯4-cell of a
((⌽⍳⌈/x)∘.<x){' ⎕'  A histogram of non-negative integer vector x
(⍋a){a  Sort the major cells of real array a
(b⍋a){a  Sort the major cells of character array a , according to alphabet b
(<<<0){m  all but the first row of m
(<<<0 ¯1){m  all but the first and last rows of m
(<(<<i),<<j)){m  all but the row i & column j of m
(<<¨>i,j){m  all but the row i & column j of m
(<(<i),<<j){m  Row i and all but column j of m
(<(<<i),<j){m  All but row i , and column j of m
i{m  Row i of matrix m
i¨{  A verb selecting row i of a matrix
x i¨{}m  Like m , but row i is x
x i⍤¯}m  Like m , but row i is x
x(<∘⊃i)¨{}m  Like m , but column i is x
x(<∘⊃i)⍤¯}m  Like m , but column i is x
x i¨{}⍤¯1 m  Like m , but column i is x
x i¨{⍤1}m  Like m , but column i is x
x i¨{}¨⍉m  Like m , but column i is x
x i¨{⍤⍉}m  Like m , but column i is x
x(<<<i)¨{m  Like m , but all except row i is x
x 0 0¨⍉}m  Like m , but the diagonal is x
x b/}y  Like y , but the positions selected by b are x
a←1⊢}a  Replace every element of a by 1 ; a[;…;]←1
{(<a),(<b),<c   The cartesian product of a , b , and c
{⍳¨>⍳a   The “position” of each element of a ;
(<⍴a)⊤¨>(⍴a)⍴⍳×/⍴a 
⌽¨>}c   ⍉c , where c is a cube — (⍴c)^.=0{⍴c
>{⍤>/(<⍤0⌽p),<a   Pick a (nested) element of a with path p

1.2 Text Formatting

Carim [1977] and Smith [1979] discussed the text formatting or “paragraphing” problem. Given: a stringof words separated by blanks, and a positive integerof the desired width. Replace appropriate elements ofby the “new line” character nl , so that lines are no wider than , and each line contains all the words that fit within the line. (To focus on essentials, assume words are at mostin length, and adjacent words are separated by exactly one blank.)

Our solution has two constituents, both employing { and both of interest in their own right.

classify: (⍴⍵)⍴(⍴⍺)↓(+\i<⍴⍺) i¨{}i←⍋⍺,,⍵

Non-decreasing vectorpartitions the real numbers into contiguous intervals; classify computes the index of the interval which contains . That is, if z←⍺ classify ⍵ , then ⍴z ←→ ⍴⍵ , and i{z is the least non-negative integer such that (i{⍵)<(i{z){⍺ . (i{z is ⍴⍺ if (i{⍵)≥¯1{⍺ .) Examples:

    ¯1 0 2 4 7.5 classify 2
3
    ¯1 0 2 4 7.5 classify ¯99
0
    ¯1 0 2 4 7.5 classify ¯99 ¯1 99 2 1.5 2.5 6 7 7.5 
0 1 5 3 2 3 4 4 5

The second constituent solves a version of the transitive closure problem.

tc: (x⍳n)↑x←0{⍉{⍀(1 1+n)⍴n⌊⍵,n←⍴⍵

Integer vectorrepresents a directed acyclic graph, whose nodes are labelled ⍳0{⍴⍵ . i{⍵ is the terminus of the arc originating at node i . (If (i{⍵)≥⍴⍵ , node i has no outgoing arc.) tc⍵ computes the nodes reachable from node 0. For examp1e,

    x←1 3 4 6 7 8 9 10 12 13 15 15 15 15 15
    (⍳0{⍴x),¨<x
0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
1  3  4  6  7  8  9 10 12 13 15 15 15 15 15

tc is useful in resolving multiple quotations, overlapping substring occurrences, and others, as well as in text formatting.

Having classify and tc in hand, we are ready to solve the text formatting problem.

fit: nl (¯1+(tc e classify ⍺+s){s)¨{}⍵ ⊣
       e←1↓(s-1),⍴⍵ ⊣ s←(l<¯1↓1,l)/⍳0{⍴⍵ ⊣ l←⍵∊' '

is the maximum width of a line, andis a string. First, compute s , the index of the starting letter of each word; and e , one plus the index of the ending letter of each word. If a line were to start at word i , then the next line starts at the first word which ends beyond i{⍺+s — at word i{e classify ⍺+s . We know the first line starts at word 0 , so the lines (except the first) start at words tc e classify ⍺+s . Replace the character preceding the starts of these words with new-lines (nl), and we are done.

    t
now is the time for all good men to chew up all the 
    foobars in their country. the quick brown fox
    jumps over the lazy dog.

    20 fit t                 25 fit t
now is the time for      now is the time for all
all good men to chew     good men to chew up all 
up all the foobars       the foobars in their
in their country.        country. the quick brown
the quick brown fox      fox jumps over the lazy
jumps over the lazy      dog.
dog.

1.3 Latin Square Analysis of Variance

latin:  n×ss(mean,⍵)-mean+/(>0 1 2⊃1 0 2⊃1 2 0)⍉x←
          ⍵(((0{⍺)⍳⍺),¨>{⍳¨>⍴⍺)¨{}(3⍴n)⍴0 ⊣ n←0{⍴⍺
mean:   (+/⍵)÷¯1{1,⍴⍵
ss:     ⍵+.*2

is a Latin square, a matrix of 0{⍴⍺ symbols where each symbol occurs in a row (column) exactly once. Numeric matrixare data from an experiment with design : (<i,j){⍵ is the datum for row factor i , column factor j , and treatment factor (<i,j){⍺  . Fromand , latin computes the treatments, rows, and columns sums of squares. The rank-3 array x within latin is an expansion of , indicating where the data would fit in a complete block design.

Example: (Mendenhall & Scheaffer [1973])

  sq           data             sq latin data
3 1 2 4      44 41 30 40      626 365 226.5
2 3 4 1      41 42 49 49
1 4 3 2      59 41 59 34
4 2 1 3      58 37 53 59

1.4 Databases

a is a 4-dimensional array implementing a database. The scalar (<i,j,k,l){a is the number of people who
    live in the i-th city,
    are j years old,
    have at least k years of schooling, and
    are in income bracket l.

Three scenarios in the use of this database:

One, index array i0 has been used to analyze the database +/+/a (city vs. age), and index array j0 has been used to analyze the database +⌿+⌿a (education vs. income). The index array i0∘.(,¨>)j0 can be used to explore in greater detail (in database a) the cases analyzed in the previous two studies.

Two, i1 selects all people of age 25 in Toronto or Montreal, and j1 selects high school graduates living in those two cities. i1,j1 selects Torontonians or Montrealers, who are 25 years old or have at least 12 years of education.

Three, people in age range y←25+⍳22 are “in their prime”; having less than s years of schooling is “less than well-educated”; and income brackets 0 through b are “lower income”. Then (<(<∘),(<y),(<<⍳s),<<⍳1+b){a selects Yuppies.

Exercise: Do the above with [;] indexing.

1.5 Lagrange Interpolation Polynomial

lagrange: (×/(⍵∘.-c)÷⍤2 z-⍤¯1 c)+.×fz ⊣ c←(<¨>¨>⍳0{⍴⍺){z ⊣
            z←0{⍉⍺ ⊣ fz←1{⍉z

is a 2-column matrix with distinct rows; each row (z,f z) is a sample from a univariate complex function f . lagrange interpolatesat , using a (¯1+0{⍴⍺)-th degree polynomial.

Examples:

    x← 1  2 ¯6.2
    y←20 ¯5  5.5
    a←x,⍪y

    y ≡ a lagrange x
1
    a lagrange ¯2 ¯1 0 1 2
55.47 50.23 38.41 20 ¯5

    b←y⌹x∘.*⍳0{⍴x
    (¯2 ¯1 0 1 2∘.*⍳0{⍴x)+.×b
55.47 50.23 38.41 20 ¯5

1.6 Triangular Matrix Inversion

A square matrixis upper triangular if (0=⍵)∨c∘.≤c←⍳0{⍴⍵ . There is a simple computation for inverting such a matrix: invert a 2 2 triangular matrix of numbers, without using the commutativity of ×  then generalize to a (conceptual) 2 2 triangular matrix of matrices, substituting +.× for × .

ri: (ai,-ai+.×b+.×di)⍪(c,di) ⊣ 
      ai←⍙(<( <i),<i){⍵ ⊣ b←  (<( <i),<<i){⍵ ⊣
      c←  (<(<<i),<i){⍵ ⊣ di←⍙(<(<<i),<<i){⍵ ⊣ i←⍳⌈n÷2
  : 1≥n←0{⍴⍵
  : ÷⍵

ri quarters : ai , b , c , and di are respectively the inverse of the top left, the top right, the bottom left, and the inverse of the bottom right. The two recursive steps in ri can be performed in parallel; thus ri shows how to compute the inverse of a triangular matrix in (2⍟n)*2 parallel time.

Section 3.3 exhibits a computation for the inverse of a general matrix, also using { .
 

2. Definitions of { and }

{ is a verb; } is a monadic adverb. Here, we define the four cases arising therefrom: {⍵ , ⍺{⍵ , v}⍵ , and ⍺v}⍵ .

2.1 All

{⍵:  (↓⍴¨>⍵)⍴<⍤1⍉(×/k)⍴⍤>⍉¨>((⌽×\⌽1↓k,1),¨>k)⍴¨>⍵ ⊣ k←×/⍤⍴⍤>⍵

{⍵ has rank 1, and computes the Cartesian product of the opened elements of . The result satisfies ⍴{⍵ ←→ ↓⍴¨>⍵ and ⍴¨>⍵ ←→ (⍴{⍵) ←→ (⍴{⍵)⍴<⍴⍵ .

2.2 From

Dyadic { encompasses all computations expressible by [;] indexing of APL\360, as well as the new negative indexing and complementary indexing. The left rank is 0 , the right rank is infinite; i.e. the definition applies to each scalar of and toin toto. Note the key role played by monadic { .

⍺{⍵:  ((<⍴⍵)⊥⍤>{⍺ fi ⍵){,⍵
fi:   (⍴a)⍴(a≡⍤0⊃¨>a)⊖i,¨<(⍳¨>s)~⍤,¨>i←s|⍤>¨>a ⊣
        a←(⊢¨>>⍺),((⍴⍴⍵)-⍴,>⍺)⍴<∘ ⊣ s←⍴⍵

Whereis a vector and ⍺∊⍳⍴⍵ , is primitive.

Otherwise, successive opened elements in >⍺ select along successive axes of . i←>k{,>⍺ is the index for axis k . i may be an array of integers in the range -k{⍴⍵ to ¯1+k{⍴⍵ ; negative i is equivalent to (k{⍴⍵)|i (negative indexing). i may also be boxed; integers therein indicate positions to be excluded (complementary indexing). The noun , having value <'' , is useful in complementary indexing.

It is instructive to consider simpler computations for ⍺{⍵ in two special cases. If each opened element of >⍺ is an integer array,

    ⍺{⍵ ←→ >(s⊥⍤>s|¨>{>⍺){,<⍤(-⍴,>⍺)⍵ ⊣ s←<(⍴,>⍺)↑⍴⍵

Furthermore, ifis an integer, i.e. if ⍺∊(-n)+⍳2×n←0{⍴⍵ , thenselects a major cell of ; and

    ⍺{⍵ ←→ >((0{⍴⍵)|⍺){<⍤¯1 ⍵

2.3 Select

v}⍵:  (v{⍳¨>⍴⍵){⍵

v} has infinite monadic rank. v is applied to {⍳¨>⍴⍵ , the result is then used to select from . v}⍵ is commonly, but not always, equivalent to v⍵ .

2.4 Merge

The dyadic case of the derived verb v} produces a merge of its arguments. Both the left and the right rank are infinite. Positions inselected by v are replaced by . ⍺v}⍵ is a new array; neithernor nor v are affected by the computation of ⍺v}⍵ . Schueler [1986] proposes the following definition. It combines in one phrase {⍵ , ⍺{⍵ , v}⍵ , and ⍺v}⍵ .

⍺v}⍵: ((⌽i,⍤,j)⍳i){⌽⍵,⍤,(⍴j)⍴⍺ ⊣ j←v}i←{⍳¨>⍴⍵

Variable j in the definition indicates positions in selected by v . In this paper, we assume either ⍴⍺ matches ⍴j , oris a scalar.

v , the verbal argument to } , is not restricted to any subclass of verbs. In particular, v need not be a “selection function”.
 

3. Some Primitives in Terms of { and }

In this section, we define some primitives, both old and new, in terms of { } . The intent is to increase understanding of these primitives and of { } , rather than to present a formal system of definitions.

3.1 Old Selection

⌽⍵:   (-1+⍳0{⍴⍵){⍵

⊖⍵:   (-1+⍳0{⍴⍵){⍵

⍺⌽⍵:  ((0{⍴⍵)|⍺+⍳0{⍴⍵){⍵

⍺⊖⍵:  ⍺⌽¨⍉⍵

n⌿⍵:  (((-0∊1↑n)++\(⍳+/n)∊+\n){(0+.=n)↓⍋×n){⍵

n⍀⍵:  (n×+\n){(0{1↑0⍴⍵)⍪>(+/n)⍴<⍤¯1 ⍵

⍉⍵:   (⌽⍳0{⍴⍴⍵)⍉⍵

⍺⍉⍵:  ((>{⍳¨>(⍴⍵)⌊.+¯×~l)+.×(⍴⍵)⊥l){,⍵ ⊣ l←⍺∘.=⍳1+⌈/⍺

3.2 Cuts

Iverson [1983] and [1986] described a family of verbs derived from the phrase n⍤v (adverbwith nounal left argument n and verbal right argument v . All derived verbs in this family apply v to rectangular pieces cut from ; the exact nature of the cut is determined by n . Currently, n∊¯3+⍳7 is permissible.

All cuts have infinite monadic rank and infinite right rank, i.e. apply to all of . 0⍤v , 3⍤v , and ¯3⍤v have left rank 2; the others have left rank 1.

⍺  0⍤v ⍵:  v (<⍺ ci ⍵){⍵

   0⍤v ⍵:  (0 ¯1∘.×⍴⍵) 0⍤v ⍵

⍺  1⍤v ⍵:  (i⍪⍥,⍤0(1↓i,⍴⍺)-i) 0⍤v ⍵ ⊣ i←⍺/⍳0{⍴⍺

   1⍤v ⍵:  (⍵≡⍤¯1 ¯⊢0{⍵) 1⍤v ⍵

  ¯1⍤v     ←→ 1⍤(v⍤(1¨↓))

   2⍤v     ←→ 1⍤(v⍤⊖)¨⊖

  ¯2⍤v     ←→ 2⍤(v⍤(¯1¨↓))

⍺  3⍤v ⍵:  (⍺ ti ⍵) 0⍤v ⍵  :  1≥⍴⍴⍺  :  (⍉1,⍪⍺)⍙⍵

   3⍤v ⍵:  ((⍴⍴⍵)⍴⌊/⍴⍵) 3⍤v ⍵

⍺ ¯3⍤v ⍵:  ((⍺≡⍤(1¨{⍤2)i)⌿i←⍺ ti ⍵) 0⍤v ⍵
        :  1≥⍴⍴⍺
        :  (⍉1,⍪⍺)⍙⍵

  ¯3⍤v ⍵:  ((⍴⍴⍵)⍴⌊/⍴⍵) ¯3⍤v ⍵

ci:  ((lׯ1-s)+(⍴⍵)|0{a)+¨>(¯1*l)ר>⍳¨>|s ⊣ l←0>s ⊣
       s←1{a ⊣ a←⍺,0 1∘.×(1{⍴⍺)↓⍴⍵

ti:  1 0 2⍉i,¨<(×1{⍺)×⍤1(|1{⍺)⌊⍤1(⍴⍵)-⍤1 i ⊣
       i←(0{⍺)×⍤1 l\,>{⍳¨>⌈(l/⍴⍵)÷l/0{⍺ ⊣ l←0≠0{⍺

This dense and dry description imparts little sense of the utility of n⍤v . The usefulness end power of cuts are better illustrated through examples. But, given the title of the current text, such examples are more suitable for another paper. (Stay tuned.)

3.3 Two Primitives from Linear Algebra

u.v⍵:  (0{⍉⍵) u.v ⍙ (<¨>¨>(⍳0{⍴⍵),¨>0){⍵
    :  1=¯1{⍴⍵
    :  u⌿,⍵

Iverson [1976] proposed a generalization of the determinant; Iverson [1982] and [1986] refined the idea. The above is an adaptation of a recursive definition in Hoffman & Kunze [1971], and works by “expansion by minors” along the first column of matrix . The definition demonstrates the key role played by ⍺u.v⍵ , and motivates the choice of u.v⍵ to denote the generalized determinant.

-.× is the ordinary determinant.

⌹⍵:   (adj⍵)÷-.×⍵ : ≠/⍴⍵ : (⌹(+⍉⍵)+.×⍵)+.×+⍉⍵
adj:  ⍉(¯1*+/>i)×-.×(<¨>¨>i){⍵ ⊣ i←{⍳¨>⍴⍵

is a complex matrix; is as in APL\360, but extended to the complex domain; and adj is the “classical adjoint” of mathematics. The above is a grossly inefficient (not to mention numerically unstable) means of computing , but is useful for theoretical investigations. McDonnell & Shallit [1980] employed this definition to assign a meaning to ⌹⍵ where 0=-.×⍵ ; viz., ⌹⍵ ←→ ¯×0≠adj⍵ .
 

4. Further Applications

4.1 Combinations

comb:  (c/k),(-1+⌽↓⍳¨>⌽c){1+(⍺-1)⍙⍵-1 ⊣ c←(⍺-1)!(⍺-1)+⌽k ⊣ 
         k←⍳1+⍵-⍺
    :  0=⍺
    :  1 0 ⍴0

All sizecombinations (subsets) of ⍳⍵ ; combinations and elements therein are in ascending order. This is a restatement, in modern terms, of the algorithm in Hui [1981]. In words, the rows in ⍺ comb ⍵ whose first element is k , are formed by prefixing k to k+1+(⍺-1)comb⍵-k+1 . But the latter is just the last (⍺-1)!⍵-k+1 rows of (⍺-1)comb ⍵-1 , incremented by one.

The phrase (⍉(⍺=+⌿t)t←(⍵⍴2)⊤⍳2*⍵)∘∇'⍺/⍵'⍤1⍳⍵ is equivalent to ⍺comb⍵ , but requires space (and time) exponential in the size of the desired result.

Examples:

  2 comb 4          3 comb 5         4 comb 6
0 1               0 1 2            0 1 2 3
0 2               0 1 3            0 1 2 4
0 3               0 1 4            0 1 2 5
1 2               0 2 3            0 1 3 4
1 3               0 2 4            0 1 3 5
2 3               0 3 4            0 1 4 5
                  1 2 3            0 2 3 4
                  1 2 4            0 2 3 5
                  1 3 4            0 2 4 5
                  2 3 4            0 3 4 5
                                   1 2 3 4
                                   1 2 3 5
                                   1 2 4 5
                                   1 3 4 5
                                   2 3 4 5

4.2 Compositions

comp:  (c/k),((⍺-1)↑⍤0 c/-k)+(-1+⌽↓⍳¨>⌽c){(⍺-1)⍙⍵ ⊣
         c←(⍺-2)!(⍺-2)+⌽k ⊣ k←⍳1+⍵
    :  1≥⍺
    :  ((⍺≥⍤×⍵),⍺)⍴⍵

All sizecompositions of , in ascending order: all vectors x of non-negative integers, such that (⍺=⍴x)^(⍵=+/x) . For example, ⍺comp⍵ are the exponents in the expansion of an-nomial (a+b+…+z , terms) raised to the-th power.

The current definition of comp is a restatement, in modern terms, of the algorithm in Hui [1982]. In words, the rows in ⍺comp⍵ whose first element is k , are formed by prefixing k to (⍺-1)comp⍵-k . But the latter is just the last (⍺-2)!(⍺-2)+1+⍵-k rows of (⍺-1)comp⍵ , with the first column decremented by k .

The phrase ⍉(⍵=+⌿t)/t←(⍺⍴1+⍵)⊤⍳(1+⍵)*⍺ is equivalent to ⍺comp⍵ , but requires space (and time) exponential in the size of the desired result.

Examples:

  2 comp 3          3 comp 3
0 3               0 0 3
1 2               0 1 2
2 1               0 2 1
3 0               0 3 0
                  1 0 2 
                  1 1 1
                  1 2 0
                  2 0 1
                  2 1 0
                  3 0 0

4.3 Permutations

perm:  ⍪⌿k,⍤¯1 (⍙⍵-1){⍤¯ 1 k~⍤1 0 k←⍳⍵
    :  1≥⍵
    :  (1,⍵)⍴0

All permutations of ⍳⍵ , in ascending order. This is a restatement, in modern terms, of the algorithm in Hui [1981]. In words, the rows in perm⍵ whose first element is k , are formed by prefixing k to the result of permuting (⍳⍵)~k by perm⍵-1 ; in other words, (k=0{⍉t)⌿t←perm ⍵ ←→ k,(perm ⍵-1){(⍳⍵)~k .

The phrase (^/(⍳⍵)∊⍤1 t)⌿t←⍉(⍵⍴⍵)⊤⍳⍵*⍵ is equivalent to perm⍵ , but requires space (and time) exponential in the size of the desired result.

Examples:

  perm 3            perm 4
0 1 2             0 1 2 3
0 2 1             0 1 3 2
1 0 2             0 2 1 3
1 2 0             0 2 3 1
2 0 1             0 3 1 2
2 1 0             0 3 2 1
                  1 0 2 3
                  1 0 3 2
                  1 2 0 3
                  1 2 3 0
                   …

sup:  (0,1+t)⍪⍪k⌿,⍤¯1(k∘.≠k)∘∇'⍺\⍵'⍤¯1(¯1+s↑t){⍤¯ 1 e ⊣
        e←k~⍤1 0 k ⊣ k←1↓⍳⍵ ⊣ s←((0{⍉t)⍳1),2-⍵ ⊣ t←⍙ ⍵-1
   :  1≥⍵
   :  (1,⍵)⍴0

All self-upgrading permutations of ⍳⍵ , in ascending order. The algorithm is due to H.A. Rothe (McDonnell [1976]). In words, the rows in sup⍵ whose first element is 0 , are formed by prefixing 0 to 1+sup⍵-1 ; the rows whose first element is k (0≠k) has 0 in column k , the other columns are (sup⍵-2){(⍳⍵)~k,0 .

The phrase (∧/t=⍋⍤1 t)⌿t←perm⍵ is equivalent to sup⍵ , but requires space (and time) exponential in the size of the desired result.

Examples:

  sup 3         sup 4
0 1 2         0 1 2 3
0 2 1         0 1 3 2
1 0 2         0 2 1 3
2 1 0         0 3 2 1
              1 0 2 3
              1 0 3 2
              2 1 0 3
              2 3 0 1
              3 1 2 0
              3 2 1 0

sdp: x⍪⊖⌽x←(⌽m-t),(r⍴⌊⍵÷2),⍤1 t←⍪⌿k,⍤¯1⊂(k∘.≠k)∘∇'⍺\⍵'⍤¯1
       (s↓⍙⍵-4+r){⍤¯ 1 e ⊣ e←((⍳⍵)~0,m,r⍴⌊⍵÷2)~⍤1 k,⍪m-k ⊣
       k←⌽(⌈⍵÷2)+⍳¯1+⌊⍵÷2 ⊣ s←0,⌊(⍵-4)÷2 ⊣ m←⍵-1
   : (1≥⍵)∨2≤r ⊣ r←4|⍵
   : ((1≥⍵),⍵)⍴0

All self-downgrading permutations of ⍳⍵ , in ascending order. The algorithm is due to E.E. McDonnell (McDonnell [1976]), and derives by observing that a choice for the first element of a row immediately determines three other elements of that row. We first generate the upper right corner (local variable t in sdp), whence the full result obtains easily.

The phrase (∧/t=⍒⍤1 t)⌿t←perm⍵ is equivalent to sdp⍵ , but requires space (and time) exponential in the size of the desired result.

Examples:

  sdp 4                  sdp 5
1 3 0 2                1 4 2 0 3
2 0 3 1                3 0 2 4 1

  sdp 8                  sdp 9
1 7 3 5 2 4 0 6        1 8 3 6 4 2 5 0 7
1 7 4 2 5 3 0 6        1 8 5 2 4 6 3 0 7
2 3 7 6 1 0 4 5        2 3 8 7 4 1 0 5 6
2 4 7 1 6 0 3 5        2 5 8 1 4 7 0 3 6
3 2 6 7 0 1 5 4        3 2 7 8 4 0 1 6 5
3 5 1 7 0 6 2 4        3 6 1 8 4 0 7 2 5
4 2 6 0 7 1 5 3        5 2 7 0 4 8 1 6 3
4 5 1 0 7 6 2 3        5 6 1 0 4 8 7 2 3
5 3 0 6 1 7 U 2        6 3 0 7 4 1 8 5 2
5 4 0 1 6 7 3 2        6 5 0 1 4 7 8 3 2
6 0 3 5 2 4 7 1        7 0 3 6 4 2 5 8 1
6 0 4 2 5 3 7 1        7 0 5 2 4 6 3 8 1

≤⍵: ↑,(⍋⌈/t){(t⍳⌈/t)⌽t←⍉{⍀(1 1+⌈/⍵)⍴⍵,(⍳⌈/⍵)~⍵

The cycle representation of a mix (a generalized permutation). For example, ≤4 5 2 1 0 3 ←→ 2 4 0 5 3 1 ; the cycles are 2 , 4 0 , and 5 3 1 . Knuth [1973] has a description of such representations; but here, 1s in c=⌈\c (rather than c=⌊\c) delimit cycles, so that (⍳n)≡≤⍳n . Iverson [1980] contains a similar algorithm for ≤⍵ .

≥⍵:       ((⍋c++\c){⍵)⍵¨{}⍳1+⌈/⍵ ⊣ c←⍵=⌈\⍵
≥⍵:  ((c/⍵)(1⌽c)/}1⌽⍵)⍵¨{}⍳1+⌈/⍵ ⊣ c←⍵=⌈\⍵

≥⍵ is the permutation whose cycle representation is  The first definition is modified from Iverson [1980]; the second is a linear-time computation. For a permutation , ≤≥⍵ ←→ ⍵ ←→ ≥≤⍵ .

In general, ⍋⍵ and ⍒⍵ require time of order ×/(⍴⍵),2⍟0{⍴⍵ , but for permutations , linear-time computations exist:

⍋⍵:  (⍳0{⍴⍵)    ⍵ ¨{}⍵
⍒⍵:  (⍳0{⍴⍵)(-1+⍵)¨{}⍵

4.4 Permutation Groups

perm n , the set of permutations of ⍳n , forms a group under { :

   ∨/(perm n)∧.=p{q          closure
p{q{r  ←→ (p{q){r associativity
(⍳n){p ←→ p identity element
(⍋p){p ←→ ⍳n inverse element

This is the “symmetric group of degree n”. The group table is p∘.({⍤1)p←perm n .

In ordinary arithmetic, the-th power of a number is the product ×⌿⍺⍴⍵ . Similarly, the-th power of a permutationis {⌿(⍺,⍴⍵)⍴⍵ ; or, more concisely, {⌿⍺⌿⍉⍪⍵ .

A subgroup of a group is a subset of group elements which form a group in their own right (under the same operation). The smallest subgroup containing a permutation , the subgroup generated by , is the set of all distinct powers of : ↑{⍀(!⍴⍵)⌿⍉⍪⍵ . This expression, although concise, is rather profligate, as the size of the subgroup is much smaller than !⍴⍵ for 2<⍴⍵ . In fact, the size is exactly the least common multiple of the lengths of the cycles of , ∧⌿1⍤⍴c=⌈\c←≤⍵ . Therefore,

sg: {⍀(∧⌿1⍤⍴c=⌈\c←≤⍵)⌿⍉⍪⍵

  sg 2 5 1 0 3 4        sg 1 4 5 2 0 3
2 5 1 0 3 4           1 4 5 2 0 3
1 4 5 2 0 3           4 0 3 5 1 2
5 3 4 1 2 0           0 1 2 3 4 5
4 0 3 5 1 2
3 2 0 4 5 1
0 1 2 3 4 5

Letbe a set of permutations — a matrix whose rows are permutations. To compute the members of the subgroup generated by , we reason as follows: Since the subgroup must be closed, it contains ⍵∘.({⍤1)⍵ ; or, in standard matrix form, ↑⍪⌿⍵∘.({⍤1)⍵. This process is repeated, until no more new permutations are introduced. Thus we have

sgm: '↑⍪⌿⍵∘.({⍤1)⍵'∇∘. ¯(⍉⍪⍳¯1{⍴⍵)⍪⍵

The “process” is the derived verb '↑⍪⌿⍵∘.({⍤1)⍵'∇∘ ; the augmentation ofby the identity permutation ⍳¯1{⍴⍵ converts a limit computation v. ¯ into the desired closure computation.

In general, no one permutation generates the entire group, else { on permutations would be commutative. Herstein [1975] (Exercise 2.10.11) tells us there exists a generator of size two: p←(⌽⍳2⌊n),2↓⍳n and q←1⌽⍳n suffice to generate p1←p and q1←(1⌽⍳n-1),n-1 , which are like p and q except ¯1{⍵ is invariant under p1{⍵ and q1{⍵ . Therefore,

pqgen:   ((|t)/0<t←(p pqe ⍵),¯1){p,¨<q←1⌽⍳n ⊣ 
           p←(⌽⍳2⌊n),2↓⍳n ⊣ n←0{⍴⍵

pqe:     m shrink (,((|t)/0<t){¯1 0 0,¨<2 ¯1,m-1),k ⊣
           t←(¯1↓k⌽⍺) ⍙ ¯1↓⍵ ⊣ k←m|1+⍺⍳¯1{⍵
   :     2≥m←0{⍴⍵
   :     (⍺≡⍵)↓¯1

shrink:  ⍺ ⍙ (0≠t)/t←((0<l/⍵){¯2,⍺)|l 1⍤(+/) ⍵
      :  ∧/l←s≠¯1↓2,s←×⍵
      :  ⍵

⍵≡{⌿y←pqgen⍵ and (y∧.=p)∧.∨(y∧.=q) for permutation . That is, sgm p,¨<q is the entire permutation group.

What is the significance of permutation groups? Let G be a group table of a finite group of order n . If relabel:(0{t)⍳t←<⍤¯2⍵ , the columns of relabel G are distinct permutations of ⍳n , and

    relabel G ←→ relabel H∘.({⍤1)H←⍉relabel G

In other words, every finite group G of order n is isomorphic to a subgroup H of the permutation group of degree n . This is the finite case of Cayley’s Theorem, named in honor of the English mathematician who first observed the fact (Herstein [1975], Section 2.9).

We illustrate Cayley’s Theorem with an example. Let G be a group table of the group of transpositions (reflections and rotations) of the square. G in this instance is a matrix of boxed literal vectors. (More about the unusual element names later.)

    G
⊢  ⍒  ⍒⍒ ⍋⌽ ⌽  ⍋  ⍋⍒ ⍒⌽    ⊢  identity
⍒  ⍒⍒ ⍋⌽ ⊢  ⍒⌽ ⌽  ⍋  ⍋⍒⍒  rotate ○1÷2 radians
⍒⍒ ⍋⌽ ⊢  ⍒  ⍋⍒ ⍒⌽ ⌽  ⍋ ⍒⍒ rotate ○2÷2 radians
⍋⌽ ⊢  ⍒  ⍒⍒ ⍋  ⍋⍒ ⍒⌽ ⌽ ⍋⌽ rotate ○3÷2 radians
⌽  ⍋  ⍋⍒ ⍒⌽ ⊢  ⍒  ⍒⍒ ⍋⌽⌽  reflect along x-axis
⍋  ⍋⍒ ⍒⌽ ⌽  ⍋⌽ ⊢  ⍒  ⍒⍒⍋  reflect along f:-⍵
⍋⍒ ⍒⌽ ⌽  ⍋  ⍒⍒ ⍋⌽ ⊢  ⍒ ⍋⍒ reflect along y-axis
⍒⌽ ⌽  ⍋  ⍋⍒ ⍒  ⍒⍒ ⍋⌽ ⊢ ⍒⌽ reflect along f:⍵
    ⍴G
8 8

    relabel G
0 1 2 3 4 5 6 7
1 2 3 0 7 4 5 6
2 3 0 1 6 7 4 5
3 0 1 2 5 6 7 4
4 5 6 7 0 1 2 3
5 6 7 4 3 0 1 2
6 7 4 5 2 3 0 1
7 4 5 6 1 2 3 0

    H←⍉relabel G

The columns of relabel G , the rows of H , are distinct permutations of ⍳8 , and H is a subgroup of the permutation group of degree 8. After relabelling, H∘.({⍤1)H , the group table of H , is identical to the relabelled version of G .

    relabel H∘.({⍤1)H
0 1 2 3 4 5 6 7
1 2 3 0 7 4 5 6
2 3 0 1 6 7 4 5
3 0 1 2 5 6 7 4
4 5 6 7 0 1 2 3
5 6 7 4 3 0 1 2
6 7 4 5 2 3 0 1
7 4 5 6 1 2 3 0

    (relabel G)≡relabel H∘.({⍤1)H
1

(The names for the elements of G are due to considerations discovered independently by Thomson [1979], Hui [1981], and Benkard & Seebe [1983]:

(pm:⍵∘.=⍳0{⍴⍵ and mp:⍵⍳1 are an inverse pair, mapping permutations to boolean matrices and vice versa. Let f be a string of ⊢ ⍒ ⍋ ⌽ , a function on permutations; and t be a transposition of the square. Identify f and t , if

    f p ←→ t¨pm p    (←→ mp t pm p)
    t m ←→ f¨mp m    (←→ pm f mp m)

In other words, G may be viewed as a group of transpositions of the square, or isomorphically as a group of functions on permutations. We saw previously that G is also isomorphic to a subgroup of the permutations, by Cayley’s Theorem.

(Table G above is a compact presentation of numerous identities involving the functions ⊢ ⍒ ⍋ ⌽ applied to permutations: The entry (<i,j){G is equivalent to the result of composing (<i,0){G and (<0,j){G . For example, the entry at the intersection of row column ⍋⍒ is , whence ⍒⍋⍒ ←→ ⍋ ; similarly, ⍋⍋ ←→ ⊢ , ⍒⍒⍒ ←→ ⍋⌽ , ⍒⍒⍒⍒ ←→ ⊢ , and so forth.)
 

5. Conclusion

{ has more expressive power than [;] , without the anomalous syntax. Because of this, { can be used in verb phrase; and as the paper shows, derived verbs involving { have many uses.

} allows verbs other than indexing to indicate elements are to be replaced. Unlike “indexed assignment”, } requires no special syntax, and has no side effects.
 

Acknowledgments

It is a pleasure to thank Fred Appleyard, Bob Bernecky, Paul Berry, Maxine Hersch, Ken Iverson, and Henri Schueler, whose comments, criticisms, and corrections led to numerous improvements in the paper.

Ideas herein evolved over many conversations with K.E. Iverson. Any remaining errors, strategic or tactical, stylistic or technical, are of course mine.
 

References

•  Benkard, J. Philip, and Seebe, John N., Reflection on Grades, APL 83 Conference Proceedings, APL Quote-Quad, Volume 13, Number 3, 1993 4 10.
•  Carim, Halit, Contest Number 3: Paragraphics, The I.P. Sharp Newsletter, Volume 5, Number 1, I.P. Sharp Associates Limited, 1977 1.
•  Falkoff, Adin D., and Iverson, Kenneth Eugene, The Design of APL, IBM Journal of Research and Development, Volume 17, Number 4, 1973 7. (Reprinted in McDonnell [1981].)
•  Herstein, Israel Nathan, Topics in Algebra, Second Edition, Xerox College Publishing, 1975.
•  Hoffman, Kenneth Myron, and Kunze, Ray Alden, Linear Algebra, Second Edition, Chapter 5, Prentice-Hall, 1971.
•  Hui, Roger Kwok Wah, The N-Queens Problem, APL Quote-Quad, Volume 11, Number 3, 1981 3.
•  Hui, Roger Kwok Wah, Workspace 880 hui∆util , Sharp APL Service, I.P. Sharp Associates Limited, 1982 12 20.
•  Iverson, Kenneth Eugene, Two Combinatoric Operators, APL 76 Conference Proceedings, 1976 9 22.
•  Iverson, Kenneth Eugene, Notation as a Tool of Thought, 1979 ACM Turing Award Lecture, Communications of the ACM, Volume 92, Number 8, 1980 8.
•  Iverson, Kenneth Eugene, Determinant-Like Functions Produced by the Dot Operator, Sharp APL Technical Notes Number 42, I.P. Sharp Associates Limited, 1982 4 1.
•  Iverson, Kenneth Eugene, Rationalized APL, I.P. Sharp Research Report Number 1, Revision 1, I.P. Sharp Associates Limited, 1983 4 4.
•  Iverson, Kenneth Eugene, A Dictionary of APL, I.P. Sharp Associates Limited, 1986 7.
•  Knuth, Donald Ervin, The Art of Computer Programming, Volume 1: Fundamental Algorithms, Second Edition, Section 1.3.3, Addison-Wesley, 1973.
•  McDonnell, Eugene Edward, Magic Squares and Permutations, APL Quote-Quad, Volume 7, Number 3, 1976 9.
•  McDonnell, Eugene Edward, A Source Book in APL, APL Press, 1981 9.
•  McDonnell, Eugene Edward, and Shallit, Jeffrey Outlaw, Extending APL to Infinity, APL 80 Conference Proceedings, 1980 6 24.
•  Mendenhall, William, and Scheaffer, Richard L., Mathematical Statistics with Applications, Duxbury Press, 1973.
•  Schueler, J. Henri, Messages 2007301 and 2007738, Sharp Internal APL Service, I.P. Sharp Associates Limited, 1986 11 27.
•  Smith, Bob Asa, Paragraphics Perfected, The I.P. Sharp Newsletter, Volume 7, Number 2, I.P. Sharp Associates Limited, 1979 3.
•  Thomson, Norman D., The Geometric Primitives of APL, APL 79 Conference Proceedings, APL Quote-Quad, Volume 9, Number 4, 1979 5 30.

Appendix A: Notation

Brief explanations on less familiar aspects of the notation are given here; full descriptions can be found in A Dictionary of APL (Iverson [1986]). Basically, expressions which would return results in an older APL (such as APL\360) work as before, but some expressions which previously caused errors now return results, The following conventions apply:

  the left   nounal argument of a verb
  the right nounal argument of a verb
m  the left   nounal argument of a verb
n  the right nounal argument of a verb
u  the left   verbal argument of a verb
v  the right verbal argument of a verb
mx  the monadic rank of verb x
lx  the left         rank of verb x
rx  the right       rank of verb x
  self-reference (recursion)

A.1 Direct Definition

A direct definition consists of 2 or 4 parts, separated by colons. Examples:

root:  ⍵*÷⍺
oder:  'nein' : ⍺∨⍵ : 'ja'
fact:  ⍵×⍙⍵-1 : 0=⍵ : 1

3 root 4 5 6 computes the cube roots of 4 5 6 ; 0 oder 0 ist 'nein' ; 1 oder 0 ist 'ja' ; and fact 5 is 120 .

A.2 Rank

The ranks of a verb are three integers mv,lv,rv , the monadic rank, left rank, and right rank, respectively. A verb need only be defined on arguments of rank bounded by its rank(s); the extension to arguments of higher rank is uniform for all verbs. The intrinsic ranks of a verb u may be augmented by the adverb , thus: u⍤n .

For positive rank r , is split into f←(-r)↓⍴⍵ cells, each with shape (-r)↑⍴⍵ . We speak of f as the frame or the outer shape ofrelative to rank r (or relative to v , the verb whose rank is r); and the cells as rank-r cells or simply r-cells. A negative rank indicates the number of leading axes to exclude from the cell shape: the excluded axes become the frame. ¯1-cells are also known as “major cells”. Many verbs are defined in terms of major cells.

v⍵: ⍵ is split into f←(mv)↓⍴⍵ rank-mv cells. The result obtains by applying v to each mv-cell of , with a necessarily common result cell shape c . The overall result has shape f,c .

⍺v⍵: ⍺ is split into fa←(-lv)↓⍴⍺ rank-lv cells; into fb←(-rv)↓⍴⍵ rank-rv cells. One of the following must hold: fa matches fb , or both of fa or fb is empty. If the former, v is applied to corresponding cells ofand to obtain the result cells; if the latter, the single cell for the empty frame is applied against every cell of the other argument, to obtain the result cells. The overall result has shape fa,((0=⍴fa)/fb),c .

The familiar scalar functions and scalar extension of APL\360, are special cases of this cellular verb application and cellular extension, where all ranks 0 .

The preceding is stated more succinctly below. (u⍤>⍵ applies u to the open of each scalar of .)

 u⍤n⍵:  u⍤> (0{r)enc⍵ ⊣ r←⌽3⍴⌽n
⍺u⍤n⍵:  (f⍴a) u⍤> (f⍴b) ⊣ f←(⍴a),(0=⍴⍴a)/⍴b ⊣ 
          a←(1{r)enc⍺ ⊣ b←(2{r)enc⍵ ⊣ r←⌽3⍴⌽n
enc:  (t↓⍴⍵)⍴(t↑⍴⍵)enl,⍵ ⊣ t←-((0≤⍺)×⍺⌊⍴⍴⍵)+(0>⍺)×0⌈⍺+⍴⍴⍵
enl:  (<⍺⍴⍵),⍺⍙(×/⍺)↓⍵  :  ''≡⍵  :  ⍵

Intrinsic ranks of primitive verbs:

Monadic  0       + - × ÷ * ⍟ ⌈ ⌊ | ! ○ ? ⍳ ~ > 
   1   ≤ ≥ ⌽ ⍎ { 
   2    
   ¯   < ⊃ ⍋ ⍒ , ⍪ ⊢ ⊣ ⊖ ⍴ ≠ ↑ ↓ ⍕ ⍉ 
 
Dyadic  0 0   + - × ÷ * ⍟ ⌈ ⌊ | ! ○ ? ∧ ∨ < ≤ = ≥ > ≠ ⍲ ⍱ 
   0 1    
   0 ¯   ∊ { 
   1 0    
   1 ¯   ⍴ ↑ ↓ ⍉ 
   2 ¯    
   ¯ 2    
   ¯ ¯   < ⊃ ⍋ ⍒ , ⍪ ⊢ ⊣ ⊖ ~ ≡ ⊥ ⊤ 

A.3 Nouns

∘     Jot  <''
¯     Infinity  ⌊/⍳0; 0 1 ¯ 2 ←→ 0 1,(⌊/⍳0),2

A.4 Verbs

+⍵   Mate  The complex conjugate of
<⍵   Box  Satisfies (0=⍴⍴<⍵)^(⍵≡><⍵)^(~⍵≡<⍵)
>⍵   Open  <. ¯1  i.e. the inverse of <⍵ . ⍵≡><⍵ for all , but ⍵≡<>⍵ only ifboxed.
≤⍵   Cycle  See Section 4.
≥⍵   Mix  See Section 4.
≠⍵   Sieve  (⍳0{⍴c)=c⍳c←,<⍤¯1 ⍵ ; see ↑⍵
⍺~⍵   Less  (~⍺∊(<⍤¯1) ⍵)⌿⍺ ; the major cells of , less those for
⍺∧⍵   LCM  Equivalent to “and” for boolean ⍺ ⍵
⍺∨⍵   GCD  Equivalent to “or”  for boolean ⍺ ⍵
↑⍵   Nub  (≠⍵)⌿⍵ ; distinct major cells of
⍺↑⍵   Take  If (⍴,⍺)≥⍴⍴⍵ , ⍺↑⍵ is as in APL\360; else ⍺↑⍵ ←→ (⍺,((⍴,⍺)-⍴⍴⍵)↑⍴⍵)↑⍵ .
↓⍵   Raze  >⍪¨>/,⍵ ; the inverse of 1⍤<⍵
⍺↓⍵   Drop  If (⍴,⍺)≥⍴⍴⍵ , ⍺↓⍵ is as in APL\360; else ⍺↓⍵ ←→ ((⍴⍴⍵)↑⍺)↓⍵ .
⊃⍵   Box open  <⍵ ifis open; itself if not
⍺⊃⍵   Link  (<⍺),⊃⍵
⍺⊣⍵   Left 
⊢⍵   Right 
⍺⊢⍵   Right 
{⍵   All  See Section 2.
⍺{⍵   From  See Section 2.
⍺≡⍵   Match  Isidentical to ?
⍪⍵   Table  ((1↑(⍴⍵),1),×/1↓⍴⍵)⍴⍵
⍺⍪⍵   Over  ⍺,[⎕io] ⍵
⍋⍵   Grade  ⍋⍵ is a permutation of ⍳0{⍴⍵ , and (⍋⍵){⍵ is in ascending order.
⍒⍵   Downgrade  ⍒⍵ is a permutation of ⍳0{⍴⍵ , and (⍒⍵){⍵ is in descending order.

A.5 Adverb

n⌿⍵   Replicate  ¯       See Section 3.
u⌿⍵   Down  ¯   (0{⍵) u(1{⍵) u … u(¯1{⍵) 
n/⍵   Replicate  ¯   n⌿¨⍉⍵ 
m¨v⍵   With  rv   m v ⍵ 
u¨n⍵   With  lu   ⍵ u n 
u¨v⍵   Under  mv   v. ¯1 u v ⍵ 
⍺u¨v⍵   Under  mv mv   v. ¯1 (v⍺) u (v⍵) 
⍺v⊂⍵   Swap  rv lv   ⍵ v ⍺ 
v}⍵   Select  ¯   See Section 2.
⍺v}⍵   Merge  ¯ ¯  See Section 2.
⍺m.v⍵   Tie  ¯ ¯  m is a non-negative integer indicating the length of the prefixes in the frames of andwhich must agree, with the other axes free to contribute to the result shape. m may also be ; ∘.v ←→ 0 .v
u.n⍵   Ply  mu  For n≥0 : u.0⍵ ←→ ⍵ ; u.(k+1) ←→ u u.k ⍵ ; and u. ¯⍵ ←→ u.k⍵ where k is the least positive integer such that (u.k⍵)≡u.(k+1)⍵ .
For n<0 : u.n ←→ v.(|n) , where v is the inverse of u .
u.v⍵   Alternant  2   See Section 3.
m∇n⍵   Define  ¯  ⍎m (a gross simplication)
⍺m∇n⍵   Define  ¯ ¯  ⍎n (a gross simplication)
m⍤v   Cut    See Section 3.
u⍤n   Rank  n   See Section A.2 above.
u⍤v⍵   On  mv   u v ⍵ 
⍺u⍤v⍵   On  mv mv   (v⍺) u (v⍵) 
u⍥v⍵   Upon  mv   u v ⍵ 
⍺u⍥v⍵   Upon  lv rv   u ⍺ v ⍵ 

Appendix B: Annotated Examples

⍺{⍵ , “from”, begins with the primitive notion of selecting an element from a vector — 1=⍴⍴⍵ and ⍺∊⍳⍴⍵ .

    x←31 41 59 26 53 58 97 93

    0{x              7{x              3{x
31               93                26

⍺{⍵ is defined for scalar and array . (The extension to with higher rank will be explained later.) >⍺ must be a scalar or a vector, and the length of ,>⍺ must be no greater than the rank of . >k(,>⍺ is the index for axis k .

    ⊢m←4 5⍴⍳12
 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19

    (<(<1),<2){m
7

    (<(<1 2),<4 3 2){m
 9  8  7
14 13 12

The left argument to { can be simplified by exploiting the permissiveness of monadic > on open arrays. (An open array is one which is not boxed.) Dyadicmay also be useful in this regard. The last two examples can be restated thus:

    (<1 2){m
7

    (<1 2⊃4 3 2){m
 9  8  7
14 13 12

In (<1 2){m , 1 ←→ >0{,><1 2 is the index for axis 0 (rows); 2 ←→ >0{,><1 2 is the index for axis 1 (columns). In (<1 2⊃4 3 2){m , 1 2 ←→ >0{,><1 2⊃4 3 2 are row indices and 4 3 2 ←→ >1{,><1 2⊃4 3 2 are column indices.

Where the left argument of ⍺{⍵ is open, “major cells” ofare selected. Major cells of are the subarrays of rank ¯1+⍴⍴⍵ along the leading axis of .

    2{m
10 11 12 13 14

    0{m
0 1 2 3 4

2{m is row 2 of m , because 2 ←→ >0{,>2 is the index for axis 0; 0{m is row 0 of m because 0 ←→ >0{,>0 .

Indices i for an axis of length l may be integers in the range -l to ¯1+l ; negative i is equivalent to l|i . As indices ¯1 ←→ ¯1+l , ¯2 ←→ ¯2+l , and s0 on.

    (<0 ¯1){m
4

    (<¯1⊃0 ¯1 1){m
15 19 16

    ¯2{m
10 11 12 13 14

The left rank of ⍺{⍵ is 0 , and the right rank is infinite: each scalar ofis applied against all of , to get an individual result with shape c ; the overall result of ⍺{⍵ has shape (⍴⍺),c . This produces “scattered indexing“, an effect not directly computable with [;] indexing of APL\360.

    (0 1⊃¯1 ¯1){m
1 19

    (<¯1⊃0 ¯1 1){m
15 19 16

    (2 2⍴0 1⊃¯1 ¯1⊃¯1 0⊃0 ¯2){m
 1 19
15  3

    2 0 ¯1{m
10 11 12 13 14
 0  1  2  3  4
15 16 17 18 19


    (2 2⍴2 0 ¯1 3){m
10 11 12 13 14
 0  1  2  3  4

15 16 17 18 19
15 16 17 18 19

    ((<1⊃2 3),<2 3⊃1){m
 7  8
11 16

      x←3 1 4 1 5 9 2 7
      ((⌽⍳⌈/x)∘.<x){'.⎕'
.....⎕..
.....⎕..
.....⎕.⎕
.....⎕.⎕
....⎕⎕.⎕
..⎕.⎕⎕.⎕
⎕.⎕.⎕⎕.⎕
⎕.⎕.⎕⎕⎕⎕
⎕⎕⎕⎕⎕⎕⎕⎕

In all the examples above. >k{,>⍺ are integer arrays. >k{,>⍺ may also be boxed; integers therein indicate positions to be excluded. This is “complementary indexing”.

    (<(<1),<2){m           row 1, column 2
7

    (<(<1),<<2){m          row 1, excluding column 2
5 6 8 9

    (<(<<1),<2){m          column 2, excluding row 1
2 12 17

    (<(<<1),<<2){m         excluding row 1 & column 2
0   1  3  4
10 11 13 14
15 16 18 19

    (<(<<¯1),<2){m         column 2, excluding row ¯1 
2 7 12

    (<(<<''),<2){m         column 2, excluding nothing
2 7 12 17

    (<(<∘),<2){m           ∘ ←→ <''
2 7 12 17

    (<∘⊃2){m               ∘⊃2 ←→ (<∘),<2
2 7 12 17

    i←0 1
    j←0 1 2

    m
 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19

    (<(<i),<j){m                 (<(<i),<<j){m 
0 1 2                        3 4
5 6 7                        8 9

    (<(<<i),<j){m                (<(<<i),<<j){m 
10 11 12                     13 14
15 16 17                     18 19

In Section 3.3, we use complementary and scattered indexing in concert, to produce succinct definitions for the generalized determinant and for ⌹⍵ .

The following are examples of [;] indexing, and expressions using { which compute the same result. Recall that ∘ ←→ <'' .

    a[i]              i{a
    a[i;]             i{a
    a[i;;]            i{a
    a[i;j;k]          (<i⊃j⊃k){a
    a[i;j;k;;;]       (<i⊃j⊃k){a
    a[i;j;]           (<i⊃j){a
    a[i;;j]           (<i⊃∘⊃j){a
    a[;;j]            (<∘⊃∘⊃j){a 

{⍵ , “all”, computes the cartesian product of the opened elements of its vector argument .

    {1 2⊃4 5 6 7
┌───┬───┬───┬───┐
│1 4│1 5│1 6│1 7│
├───┼───┼───┼───┤
│2 4│2 5│2 6│2 7│
└───┴───┴───┴───┘

   {'cr'⊃'ao'⊃'dmntw'
┌───┬───┬───┬───┬───┐
│cad│cam│can│cat│caw│
├───┼───┼───┼───┼───┤
│cod│com│con│cot│cow│
└───┴───┴───┴───┴───┘

┌───┬───┬───┬───┬───┐
│rad│ram│ran│rat│raw│
├───┼───┼───┼───┼───┤
│rod│rom│ron│rot│row│
└───┴───┴───┴───┴───┘

{⍵ is closely related to selecting from rectangular arrays. For example, ⍺{⍵ (Section 2.2) and ⍺⍉⍵ (Section 3.1) are both defined in terms of monadic { .

In particular, the phrase {⍳¨>⍴⍵ plays a key role in the definition of ⍺v}⍵ (“merge”). ⍴{⍳¨>⍵ ←→ ⍴⍵ ; each opened element is the “position” of an element of , a number represented in base ⍴⍵ .

    ⊢a←2 3 4⍴⍳24
 1  2  3  4
 5  6  7  8
 9 10 11 12
           
13 14 15 16
17 18 19 20
21 22 23 24

    ⍳¨⍴a
┌───┬─────┬───────┐
│0 1│0 1 2│0 1 2 3│
└───┴─────┴───────┘

    {⍳¨>⍴a
┌─────┬─────┬─────┬─────┐
│0 0 0│0 0 1│0 0 2│0 0 3│
├─────┼─────┼─────┼─────┤
│0 1 0│0 1 1│0 1 2│0 1 3│
├─────┼─────┼─────┼─────┤
│0 2 0│0 2 1│0 2 2│0 2 3│
└─────┴─────┴─────┴─────┘

┌─────┬─────┬─────┬─────┐
│1 0 0│1 0 1│1 0 2│1 0 3│
├─────┼─────┼─────┼─────┤
│1 1 0│1 1 1│1 1 2│1 1 3│
├─────┼─────┼─────┼─────┤
│1 2 0│1 2 1│1 2 2│1 2 3│
└─────┴─────┴─────┴─────┘

⍺v}⍵ produces a “merge” ofand ; positions (v i){i←{⍳¨>⍴⍵ in are replaced by . In words, the verb v is applied to i←{⍳¨>⍴⍵ , the result is then used to select from i , to obtain positions into be replaced by . In this paper, we assumeis either a scalar, or ⍴⍺ ←→ (v i){i .

    1 0{3 1 4 1 5 9
1 3

    1 0¨{3 1 4 1 5 9
1 3

    (¯1 8) 1 0¨{3 1 4 1 5 9
8 ¯1 4 1 5 9

    (¯1 ¯2 ¯3) 1 1 1¨{}3 1 4 1 5 9
3 ¯3 4 1 5 9

The phrase n¨v is a monadic verb derived from the dyadic adverb ¨ (“with”), array n , and verb v ; n¨v ⍵ ←→ n v ⍵ . n¨v is a verb, and therefore can be used as argument to adverbs such as } ; n v on the other hand is a sentence fragment, being neither a noun nor a verb nor an adverb nor punctuation.

⍺v}⍵ is a new array; neithernornor v are affected by the computation of ⍺v}⍵ . We could of course assign the result to any name.

    m
 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19

    ¯1 (<1 2)¨{}m             a single element
 0  1  2  3  4
 5  6 ¯1  8  9
10 11 12 13 14
15 16 17 18 19

    (¯1 ¯2 ¯3 ¯4 ¯5) 1¨{}m    row 1
 0  1  2  3  4
¯1 ¯2 ¯3 ¯4 ¯5
10 11 12 13 14
15 16 17 18 19

    ¯1 (<∘⊃2)¨{}m             column 2
 0  1 ¯1  3  4
 5  6 ¯1  8  9
10 11 ¯1 13 14
15 16 ¯1 18 19

    ¯1 ¯2 ¯3 ¯4 ¯5 (0 1⊃¯1 ¯1⊃¯1 0⊃0 ¯2}¨{}m
 0 ¯1  2 ¯4  4
 5  6  7  8  9
10 11 12 13 14
¯3 16 17 18 ¯2

The last example, “scattered replacement”, is not directly computable with [;] indexing.

    ¯1 (<(<1),<2)¨{}m
 0  1  2  3  4
 5  6 ¯1  8  9
10 11 12 13 14
15 16 17 18 19

    ¯1 (<(<1),<<2)¨{}m
 0  1  2  3  4
¯1 ¯1  7 ¯1 ¯1
10 11 12 13 14
15 16 17 18 19

    ¯1 (<(<<1),<2)¨{}m
 0  1 ¯1  3  4
 5  6  7  8  9
10 11 ¯1 13 14
15 16 ¯1 18 19

    ¯1 (<(<<1),<<2)¨{}m
¯1 ¯1  2 ¯1 ¯1
 5  6  7  8  9
¯1 ¯1 12 ¯1 ¯1
¯1 ¯1 17 ¯1 ¯1

v, the verbal argument to } , need not involve { . In fact, v need not be a “selection function” at all.

    (¯1) ¯2 ¯3¨↑}4 5⍴99
99 99 99 99 99
99 99 99 99 99
99 99 ¯1 ¯1 ¯1
99 99 ¯1 ¯1 ¯1

    (¯1 ¯2 ¯3 ¯4) 0 0¨⍉}m
¯1  1  2  3  4
 5 ¯2  7  8  9
10 11 ¯3 13 14
15 16 17 ¯4 19

    (¯1 ¯2 ¯3 ¯4) 0 0¨⍉⍤⊖}m
 0  1  2 ¯4  4
 5  6 ¯3  8  9
10 ¯2 12 13 14
¯1 16 17 18 19

    '*' 0 0¨⍉} '⍟' 0 0¨⍉⍤⊖}5 5⍴'.'
*...⍟
.*.⍟.
..*..
.⍟.*.
⍟...*

   '⍟' (' '=x)/}x←'cogito, ergo sum'
cogito,⍟ergo⍟sum

In the last example, / is an adverb; hence (' '=x)/ is a verb, and is the argument to } .


Errata

3.1    The expression for ⍺⍉⍵ fails for scalar . Replace ⍳1+⌈/⍺ by ⍳0⌈1+⌈/⍺ .
References  APL Quote-Quad should be APL Quote Quad.
Appendix B  The array a should be 2 3 4⍴1+⍳24 instead of 2 3 4⍴⍳24 .


Originally appeared in the APL 87 Proceedings, APL Quote Quad, Volume 17, Number 4, 1987-05.

created:  2010-04-26 09:25
updated:2020-05-08 10:50