From 7c2cb08e4dc64a42a4276664ba5ce8502919ed36 Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Sun, 3 Jul 2022 21:43:06 -0400 Subject: Overlay diagram for comparison of differently-shaped arrays --- docs/doc/order.html | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) (limited to 'docs/doc') diff --git a/docs/doc/order.html b/docs/doc/order.html index 35d30894..15111965 100644 --- a/docs/doc/order.html +++ b/docs/doc/order.html @@ -272,5 +272,43 @@

Comparing two atoms is defined to work the same way as the comparison functions ≤<>≥. Numbers come earlier than characters and otherwise these two types are ordered in the obvious way. To compare an atom to an array, the atom is enclosed and then compared with the array ordering defined below. The result of this comparison is used except when the two arrays match: in that case, the atom is considered smaller.

Two arrays of the same shape are compared by comparing all their corresponding elements, in index order. This comparison stops at the first pair of different elements (which allows later elements to contain operations without causing an error). If any elements were different, then they decide the result of the comparison. If all the elements matched, then by definition the two arrays match.

The principle for arrays of different shapes is the same, but there are two factors that need to be taken into account. First, it's not obvious any more what it means to compare corresponding elements—what's the correspondence? Second, the two arrays can't match because they have different shapes. So even if all elements end up matching one of them needs to come earlier.

+ + + + + + + a + b + c + d + e + f + g + h + i + + + a + b + d + e + g + h + j + l + p + o + + + + + + ≤3 compared values + 3×3 + 2×5 + + +

Let's discuss correspondence first. One way to think about how BQN makes arrays correspond is that they're simply laid on top of each other, lining up the first (as in ⊑) elements. So a shape ⟨4⟩ array will match up with the first row of a shape 5‿3 array, but have an extra element off the end. A simple way to think about this is to say that the lower rank array is brought up to a matching rank by putting 1s in front of the shape, and then lengths along each axis are matched up by padding the shorter array along that axis with a special "nothing" element. This "nothing" element will be treated as smaller than any actual array, because this rule recovers the "dictionary ordering" rule that a word that's a prefix of a longer word comes before that word. In the case of the shapes ⟨4⟩ and 5‿3, if the three overlapping elements match then the fourth element comes from the first row and is present in the first array but not the second. So the shape 5‿3 array would be considered smaller without even looking at its other four rows.

It can happen that two arrays of different shape have all matching elements with this procedure: either because one array's shape is the same as the other's but with some extra 1s at the beginning, or because both arrays are empty. 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.

-- cgit v1.2.3