Cell: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
Miraheze>Adám Brudzewsky
No edit summary
Miraheze>Marshall
No edit summary
Line 1: Line 1:
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#Index along an axis|index]] along some number of leading [[Axis|axes]] and the whole of each trailing axis. Cells are classified by their [[rank]], which may be between 0 ([[scalar]]s) and the array's rank (in which case the cell must be the entire array). Cells with rank <source lang=apl inline>k</source> 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 ==
{{#css:
{{#css:
svg * {cursor:crosshair}
svg * {cursor:crosshair}
Line 5: Line 9:


</div>
</div>
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#Index along an axis|index]] along some number of leading [[Axis|axes]] and the whole of each trailing axis. Cells are classified by their [[rank]], which may be between 0 ([[scalar]]s) and the array's rank (in which case the cell must be the entire array). Cells with rank <source lang=apl inline>k</source> 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]].
== Leading and trailing axes ==


The k-cells of an array with [[rank]] <source lang=apl inline>r</source> share the last <source lang=apl inline>k</source> [[Axis|axes]] with that array, and collapse the first <source lang=apl inline>r-k</source> axes by choosing a single [[Index#Index along an axis|index]] along each of them. Using [[bracket indexing]] this can be written
The k-cells of an array with [[rank]] <source lang=apl inline>r</source> share the last <source lang=apl inline>k</source> [[Axis|axes]] with that array, and collapse the first <source lang=apl inline>r-k</source> axes by choosing a single [[Index#Index along an axis|index]] along each of them. Using [[bracket indexing]] this can be written
Line 18: Line 19:
</source>
</source>
</div>
</div>
Squad indexing thus transforms [[vector]]s whose length is at most the [[rank]] of an array into cells of than an array. This transformation is an exact correspondence or [[wikipedia:bijection|bijection]]: each cell has exactly one corresponding vector. For this reason a valid [[simple]] [[numeric]] left argument to Squad is called the [[Index#Index of a cell|index of a cell]].
=== Cell shape ===
All cells of a given rank in a particular array have the same [[shape]]:
<source lang=apl>
      A ← 5 4 3 2⍴0
      (3 2)(1 4)(2 2)(4 4) {⍴⍺⌷⍵}¨⊂ A
┌───┬───┬───┬───┐
│3 2│3 2│3 2│3 2│
└───┴───┴───┴───┘
</source>
This is because the shape of a cell is always a [[suffix]] of the shape of the entire array.
<source lang=apl>
      (4 3 2 1)(2 2)(5)(3 1)⍬ {⍴⍺⌷⍵}¨⊂ A
┌┬───┬─────┬───┬───────┐
││3 2│4 3 2│3 2│5 4 3 2│
└┴───┴─────┴───┴───────┘
</source>
Because there is only one possible shape for k-cells of an array <source lang=apl inline>A</source>, this shape is called the rank-k '''cell shape''' for <source lang=apl inline>A</source>. 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 [[argument]]s.
== 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 [[Axis|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 <source lang=apl inline>r</source>, every cell of rank <source lang=apl inline>k</source> is contained in exactly one cell of rank <source lang=apl inline>j</source> when <math>r \ge j \ge k \ge 0</math>. 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 [[Index#Index of a cell|indices]] makes the reason for this relationship clear. In an array of rank <source lang=apl inline>r</source>, a cell of rank <source lang=apl inline>k</source> has an index vector <source lang=apl inline>I</source> of length <source lang=apl inline>r-k</source> (the index selects one index along each axis ''not'' in the cell). For <source lang=apl inline>j</source> such that <math>r \ge j \ge k</math>, we have <math>r-j \le r-k</math>, and the cell of rank <source lang=apl inline>j</source> which contains our chosen cell has index <source lang=apl inline>(r-j)↑I</source>, a [[prefix]] of the smaller cell's index.
This construction fails for <math>j < k</math> 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 [[wikipedia:Tree structure|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.


{{APL programming language}}
{{APL programming language}}

Revision as of 16:15, 14 November 2019

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