diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/spec/primitive.html | 10 |
1 files changed, 10 insertions, 0 deletions
diff --git a/docs/spec/primitive.html b/docs/spec/primitive.html index 4e9ef995..61b190b3 100644 --- a/docs/spec/primitive.html +++ b/docs/spec/primitive.html @@ -135,3 +135,13 @@ <li><strong>Progressive Index of</strong> (<code><span class='Function'>β</span></code>) processes non-principal cells in ravel order, and gives the smallest index of a principal argument cell that matches the cell that hasn't already been included in the result. Again <code><span class='Function'>β </span><span class='Value'>π¨</span></code> is returned for a given cell if there is no valid cell.</li> </ul> <p><strong>Find</strong> (<code><span class='Function'>β·</span></code>) indicates positions where <code><span class='Value'>π¨</span></code> appears as a contiguous subarray of a <code><span class='Function'>=</span><span class='Value'>π¨</span></code>-cell of <code><span class='Value'>π©</span></code>. It has one result element for each such subarray of <code><span class='Value'>π©</span></code>, whose value is 1 if that subarray matches <code><span class='Value'>π©</span></code> and 0 otherwise.</p> +<h3 id="sorting">Sorting</h3> +<p>Sorting functions are those that depend on BQN's array ordering. There are three kinds of sorting function, with two functions of each kind: one with an upward-pointing glyph that uses an ascending ordering (these function names are suffixed with "Up"), and one with a downward-pointing glyph and the reverse, descending, ordering ("Down"). Below, these three kinds of function are described, then the ordering rules. Except for the right argument of Bins, all arguments must have rank at least 1.</p> +<p><strong>Sort</strong> (<code><span class='Function'>β§β¨</span></code>) reorders the major cells of its argument so that a major cell with a lower index comes earlier in the ordering than a major cell with a higher index, or matches it.</p> +<p><strong>Grade</strong> (<code><span class='Function'>ββ</span></code>) returns a permutation describing the way the argument array would be sorted. For this reason the reference implementations simply define Sort to be selection by the grade. One way to define Grade is as a sorted version of the index list <code><span class='Function'>ββ </span><span class='Value'>π©</span></code>. An index <code><span class='Value'>i</span></code> is ordered according to the corresponding major cell <code><span class='Value'>i</span><span class='Function'>β</span><span class='Value'>π©</span></code>. However, ties in the ordering are broken by ordering the index values themselves, so that no two indices are ever considered equal, and the result of sorting is well-defined (for Sort this is not an issueβmatching cells are truly interchangeable). This property means that a stable sorting algorithm must be used to implement Grade functions. While cells might be ordered ascending or descending, indices are always ordered ascending, so that for example index <code><span class='Value'>i</span></code> is placed before index <code><span class='Value'>j</span></code> if either <code><span class='Value'>i</span><span class='Function'>β</span><span class='Value'>π©</span></code> comes earlier in the ordering than <code><span class='Value'>j</span><span class='Function'>β</span><span class='Value'>π©</span></code>, or if <code><span class='Value'>i</span><span class='Function'><</span><span class='Value'>j</span></code>.</p> +<p><strong>Bins</strong> (<code><span class='Function'>ββ</span></code>) requires the <code><span class='Value'>π¨</span></code> to be ordered in the sense of Sort (with the same direction). Like a dyadic search function, it then works on cells of <code><span class='Value'>π©</span></code> with the same rank as major cells of <code><span class='Value'>π¨</span></code>: the rank of <code><span class='Value'>π©</span></code> cannot be less than <code><span class='Paren'>(</span><span class='Function'>=</span><span class='Value'>π¨</span><span class='Paren'>)</span><span class='Function'>-</span><span class='Number'>1</span></code>. For each of these, it identifies where in the ordering given by <code><span class='Value'>π¨</span></code> the cell belongs, that is, the index of the first cell in <code><span class='Value'>π¨</span></code> that is ordered later than it, or <code><span class='Function'>β </span><span class='Value'>π¨</span></code> if no such cell exists. An equivalent formulation is that the result value for a cell of <code><span class='Value'>π©</span></code> is the number of major cells in <code><span class='Value'>π¨</span></code> that match or precede it.</p> +<p>BQN's <em>array ordering</em> is an extension of the number and character ordering given by <code><span class='Function'>β€</span></code> to arrays. In this system, any two arrays consisting of only numbers and characters for atoms can be compared with each other. Furthermore, some arrays that contain incomparable atoms (operations) might be comparable, if the result of the comparison can be decided before reaching these atoms. Array ordering does not depend on the fill elements for the two arguments.</p> +<p>Here we define the array ordering using the terms "smaller" and "larger". For functions <code><span class='Function'>β§β</span></code>, "earlier" means "smaller" and "later" means "larger", while <code><span class='Function'>β¨β</span></code> use the opposite definition, reversing the ordering.</p> +<p>To compare two arrays, BQN first attempts to compare elements at corresponding indices, where two indices are considered to correspond if one is a suffix of the other. Elements are accessed in ravel order, that is, beginning at the all-zero index and first increasing the final number in the index, then the second-to-last, and so on. They are compared, using array comparison if necessary, until a non-matching pair of elements is foundβin this case the ordering of this pair determines the ordering of the arraysβor one array has an index with no corresponding index in the other array. For example, comparing <code><span class='Number'>4</span><span class='Ligature'>βΏ</span><span class='Number'>3</span><span class='Ligature'>βΏ</span><span class='Number'>2</span><span class='Function'>β₯</span><span class='Number'>1</span></code> with <code><span class='Number'>2</span><span class='Ligature'>βΏ</span><span class='Number'>5</span><span class='Function'>β₯</span><span class='Number'>1</span></code> stops when index <code><span class='Number'>0</span><span class='Ligature'>βΏ</span><span class='Number'>2</span></code> in <code><span class='Number'>2</span><span class='Ligature'>βΏ</span><span class='Number'>5</span><span class='Function'>β₯</span><span class='Number'>1</span></code> is reached, because the corresponding index <code><span class='Number'>0</span><span class='Ligature'>βΏ</span><span class='Number'>0</span><span class='Ligature'>βΏ</span><span class='Number'>2</span></code> is out of range. The index <code><span class='Number'>0</span><span class='Ligature'>βΏ</span><span class='Number'>2</span><span class='Ligature'>βΏ</span><span class='Number'>0</span></code> in the other array also has no corresponding index, but comes later in the index ordering. In this case, the array that lacks the index in question is considered smaller.</p> +<p>If two arrays have the same shape (ignoring leading <code><span class='Number'>1</span></code>s) and all matching element, or if they are both empty, then the element-by-element comparison will not find any differences. In this case, the arrays are compared first by rank, with the higher-rank array considered larger, and then by shape, beginning with the leading axes.</p> +<p>To compare two atoms, array ordering uses <code><span class='Function'>β€</span></code>: if <code><span class='Value'>π¨</span><span class='Function'>β€</span><span class='Value'>π©</span></code> then <code><span class='Value'>π¨</span></code> matches <code><span class='Value'>π©</span></code> if <code><span class='Value'>π©</span><span class='Function'>β€</span><span class='Value'>π¨</span></code> and otherwise is smaller than <code><span class='Value'>π©</span></code> (and <code><span class='Value'>π©</span></code> is larger than <code><span class='Value'>π¨</span></code>). To compare an atom to an array, the atom is promoted to an array by enclosing it; however, if the enclosed atom matches the array then the atom is considered smaller.</p> |