From ea4d30020926bd2cb790c11aa311b4722d1fda75 Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Thu, 4 Feb 2021 22:15:24 -0500 Subject: Require sort to be stable for fill elements of elements --- docs/spec/primitive.html | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'docs/spec') diff --git a/docs/spec/primitive.html b/docs/spec/primitive.html index e59188d1..8a7a9a70 100644 --- a/docs/spec/primitive.html +++ b/docs/spec/primitive.html @@ -145,7 +145,7 @@

Find (⍷) indicates positions where 𝕨 appears as a contiguous subarray of a =𝕨-cell of 𝕩. It has one result element for each such subarray of 𝕩, whose value is 1 if that subarray matches 𝕩 and 0 otherwise.

Sorting

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.

-

Sort (∧∨) 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.

+

Sort (∧∨) 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. If it's possible for matching arrays to differ in behavior because of different (including undefined versus defined) fill elements, then these arrays must maintain their ordering (a stable sort is required).

Grade (⍋⍒) 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 ↕≠𝕩. An index i is ordered according to the corresponding major cell iβŠπ•©. 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 i is placed before index j if either iβŠπ•© comes earlier in the ordering than jβŠπ•©, or if they match and i<j.

Bins (⍋⍒) requires the 𝕨 to be ordered in the sense of Sort (with the same direction). Like a dyadic search function, it then works on cells of 𝕩 with the same rank as major cells of 𝕨: the rank of 𝕩 cannot be less than (=𝕨)-1. For each of these, it identifies where in the ordering given by 𝕨 the cell belongs, that is, the index of the first cell in 𝕨 that is ordered later than it, or ≠𝕨 if no such cell exists. An equivalent formulation is that the result value for a cell of 𝕩 is the number of major cells in 𝕨 that match or precede it.

BQN's array ordering is an extension of the number and character ordering given by ≀ 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.

-- cgit v1.2.3