# What is an array?

# by Roger Hui ([email protected])

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

In Scranton in 1999 during one of the sessions I was sitting next to Ken, and he leaned over and said to me – in his impish way – John, what is an array? Now I knew better than to rush into an answer to Ken. I guess I’m still working on my answers to that question.

Fools rush in where angels fear to tread…

## 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_{0}, s_{1}, …, s_{n-1})
such that
*f *(i_{0}, i_{1}, …, 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.

This definition accommodates:

- APL/J rectangular arrays
- J sparse arrays
- infinite arrays
- dictionaries (associative arrays)

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

## J sparse arrays

Sparse arrays were introduced in J in 1999 [3], [4]. 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 [3] has an example of solving a 1e5-by-1e5 tridiagonal sparse matrix in 0.28 seconds.

## Infinite arrays

Infinite arrays were described by McDonnell and Shallit [5] and Shallit [6]. 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)}

## 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

- Scholes, J.M., e-mail on 2010-10-11 11:41.
- Christensen, G., Ken Iverson in Denmark, Vector, Volume 22, No. 3, 2006-08. http://archive.vector.org.uk/art10002270
- Hui, R.K.W., Sparse Arrays in J, APL99 Conference Proceedings, APL Quote Quad, Volume 29, Number 2, 1999-08-10 to -14.
- Hui, R.K.W., and K.E. Iverson, J Introduction and Dictionary http://www.jsoftware.com/help/dictionary/d211.htm, 2010.
- McDonnell, E.E., and J.O. Shallit, Extending APL to Infinity http://www.jsoftware.com/papers/eem/infinity.htm, APL80 Conference Proceedings, 1980.
- Shallit, J.O., Infinite Arrays and Diagonalizaton, APL81 Conference Proceedings, APL Quote Quad, Volume 12, No. 1, 1981-09.