What is an Array?
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
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 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
|