Cell

From APL Wiki
Revision as of 16:15, 14 November 2019 by Miraheze>Marshall
Jump to navigation Jump to search

In the APL array model and in particular leading axis theory, a cell of an array is a subarray which is formed by selecting a single index along some number of leading axes and the whole of each trailing axis. Cells are classified by their rank, which may be between 0 (scalars) and the array's rank (in which case the cell must be the entire array). Cells with rank k are called k-cells of an array. A major cell is a cell whose rank is one less than the entire array, or a 0-cell of a scalar.

Characterization

The k-cells of an array with rank r share the last k axes with that array, and collapse the first r-k axes by choosing a single index along each of them. Using bracket indexing this can be written

A[3;2; ; ; ]    ⍝ 3-cell of a rank-5 array

while Squad indexing allows a cell to be selected without knowing the argument's rank.

3 2⌷A           ⍝ (r-2)-cell of a rank-r array

Squad indexing thus transforms vectors whose length is at most the rank of an array into cells of than an array. This transformation is an exact correspondence or bijection: each cell has exactly one corresponding vector. For this reason a valid simple numeric left argument to Squad is called the index of a cell.

Cell shape

All cells of a given rank in a particular array have the same shape:

      A ← 5 4 3 2⍴0
      (3 2)(1 4)(2 2)(4 4) {⍴⍺⌷⍵}¨⊂ A
┌───┬───┬───┬───┐
│3 2│3 2│3 2│3 2│
└───┴───┴───┴───┘

This is because the shape of a cell is always a suffix of the shape of the entire array.

      (4 3 2 1)(2 2)(5)(3 1)⍬ {⍴⍺⌷⍵}¨⊂ A
┌┬───┬─────┬───┬───────┐
││3 2│4 3 2│3 2│5 4 3 2│
└┴───┴─────┴───┴───────┘

Because there is only one possible shape for k-cells of an array A, this shape is called the rank-k cell shape for A. The cell shape is an important feature of the Rank operator: every invocation of Rank's left operand receives arrays of the same shape as arguments.

Leading and trailing axes

See also Axis ordering.

The choice to have cells of an array share trailing axes with that array is a central part of leading axis theory, which is named because the leading axes of the array form a structure for the cells called the frame. Functions defined in accordance with leading axis theory behave as though they are acting on an array of cells whose shape is the frame.

In order to create a hierarchy of cells some ordering on the axes of an array must be used, with each smaller cell taking up a subset of the axes of a larger cell. For a particular cell rank, the axes will be split into two halves, with the axes used by the cells forming the cell shape and the other axes forming the frame. The choice to use trailing axes for a cell follows naturally from the ravel order of an array: because cells are handled as individual units but the frame is not, each cell should be contiguous in memory. The only choice which ensures this property is to use the trailing axes, those which are closer together in ravel order, for cells.

The interactive tool at the right displays both trailing-axis cells (those used by APL) and leading-axis cells (the opposite choice). While each trailing-axis cell can be denoted with a single rectangle, leading-axis cells may require multiple rectangles to represent. This fact mirrors the properties of cells in ravel order: each leading-axis cell is a single region in the array's ravel, but in a trailing-axis no two elements are adjacent (except in the degenerate cases of 0-cells, full-rank cells, and length-1 axes).

Hierarchy

In an array of rank r, every cell of rank k is contained in exactly one cell of rank j when . In particular, every 0-cell (and hence every element) is contained in exactly one cell of each rank. This is why the interactive tool at the right can display cells of three different ranks even though only a single element can be pointed at.

Considering cells in terms of their indices makes the reason for this relationship clear. In an array of rank r, a cell of rank k has an index vector I of length r-k (the index selects one index along each axis not in the cell). For j such that , we have , and the cell of rank j which contains our chosen cell has index (r-j)↑I, a prefix of the smaller cell's index.

This construction fails for because the index for a smaller (lower-rank) cell must have extra indices relative to the index for a larger one. There is no way to choose a single index: in fact, as long as the axes of our array all have length greater than 1, there are multiple choices of index and the larger cell contains multiple smaller cells. As an example, a matrix can contain many rows even though a row is only ever contained in exactly one matrix. This fact should not be surprising: it's the main reason why APL uses arrays rather than lists at all!

The cell structure, where a lower-rank cell is contained in exactly one higher-rank cell but a higher-rank cell may contain many lower-rank cells, is a type of tree. The tree nodes at a given depth are all cell of the same rank, and because APL arrays are homogeneous, each has the same number of children. The root node of the tree is the array itself, and its leaf nodes are 0-cells.

Template:APL programming language