What is an Array?
Roger Hui
 

0. Origin

In a recent e-mail [0], John Scholes reminded me of his last encounter with Ken Iverson, originally described as follows [1]:

Fools rush in where angels fear to tread …
 

1. What is an Array?

An array is a function from a set of indices to numbers, characters, … A rank-n array is one whose function f applies to n-tuples of non-negative integers. A rank-n array is rectangular if there exist non-negative integer maxima  s = (s₀, s₁, …, s_n-1) such that  f(i₀, i₁, …, i_n-1)  is defined (has a value) for all integer i_j such that (0≤i_j)^(i_j<s_j).  s is called the shape of the array. Etc.

2. APL/J Rectangular Arrays

A typical APL/J rectangular array:

   2 2 3 ⍴ 'ABCDEFGHIJKL'
ABC
DEF
   
GHI
JKL

Listing the indices with the corresponding array elements makes the index function more apparent:

0 0 0   A
0 0 1   B
0 0 2   C
0 1 0   D
0 1 1   E
0 1 2   F
1 0 0   G
1 0 1   H
1 0 2   I
1 1 0   J
1 1 1   K
1 1 2   L

APL rectangular arrays to-date have been implemented by enumerating the array elements in row major order (and employ the “implementation trick” of not storing the indices). But there are ways to represent a function other than enumerating the domain and/or range of the function.
 

3. J Sparse Arrays

Sparse arrays were introduced in J in 1999 [2, 3]. In the sparse representation, the indices and values of only the non-“zero” elements are stored.

   ] d=: (?. 3 5 $ 2) * ?. 3 5 $ 100
 0 55 79 0  0
39  0 57 0  0
 0  0 13 0 51

   ] s=: $. d   NB. convert from dense to sparse
0 1 │ 55
0 2 │ 79
1 0 │ 39
1 2 │ 57
2 2 │ 13
2 4 │ 51

   3 + s
0 1 │ 58
0 2 │ 82
1 0 │ 42
1 2 │ 60
2 2 │ 16
2 4 │ 54

Reference [2] has an example of solving a 1e5-by-1e5 tridiagonal sparse matrix in 0.28 seconds.
 

4. Infinite Arrays

Infinite arrays in were described by McDonnell and Shallit [4] and Shallit [5]. Having infinite arrays facilitates working with infinite series and limits of sequences.

   ⍳4
0 1 2 3

   ⍳∞
0 1 2 3 4 5 …

   - ⍳∞
0 ¯1 ¯2 ¯3 ¯4 ¯5 …

   3 * - ⍳∞
1 0.333333 0.111111 0.037037 …

   +/ 3 * - ⍳∞
1.5

   ⌽ ⍳∞
DOMAIN ERROR
   ⌽⍳∞
  ^

Infinite arrays can be implemented by specifying the index function as a function. For example, the index function for ⍳∞ is the identity function, ⊢ or {⍵} .

Let x and y be infinite vectors with index functions fx and fy . If s1 is a scalar monadic function, then s1 x is an infinite vector and its index function is s1∘fx , s1 composed with fx . If s2 is a scalar dyadic function, then x s2 y is an infinite vector and its index function is the fork fx s2 fy , or the dynamic function {(fx ⍵) s2 (fy ⍵)} .

In the following examples, the infinite vectors are listed with the index function, both as an operator expression (tacit function) and as a dynamic function.

   ⍳∞                   │  ⊢
0 1 2 3 4 5 6 7 …       │  {⍵}
                        │
   ∞ ⍴ 2                │  ⊢∘2
2 2 2 2 2 2 2 2 …       │  {2}
                        │
   - ⍳∞                 │  -∘⊢
0 ¯1 ¯2 ¯3 ¯4 ¯5 …      │  {-⍵}
                        │
   3 * - ⍳∞             │  (3∘*)∘-∘⊢
1 0.333333 0.111111 …   │  {3*-⍵}
                        │
   ⎕←x←3*⍳∞             │  3∘*∘⊢
1 3 9 27 81 243 729 …   │  {3*⍵}
                        │
   ⎕←y←(⍳∞)*2           │  *∘2∘⊢
0 1 4 9 16 25 36 …      │  {⍵*2}
                        │
   x+y                  │  3∘*∘⊢ + *∘2∘⊢
1 4 13 36 97 268 765 …  │  {(3*⍵)+(⍵*2)}

5. Dictionaries (Associative Arrays)

The proposed string scalars are suitable for use as indices in dictionaries. For example:

   ⍴⍴Caps
1
   Caps["UK" "China" "France"]←'London' 'Beijing' 'Paris'
   Caps
"UK"     │ London
"China"  │ Beijing
"France" │ Paris
  
   Caps["China"]
 Beijing

   Caps["USA"]
INDEX ERROR
   Caps["USA"]
  ∧

   Caps ⍳ 'Paris' 'Tokyo' 'London'   
"France" λ "UK" 

   ⌽ Caps
DOMAIN ERROR
   ⌽Caps
  ^

References