1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
|
<head>
<link href="../favicon.ico" rel="shortcut icon" type="image/x-icon"/>
<link href="../style.css" rel="stylesheet"/>
<title>BQN: Ordering functions</title>
</head>
<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">doc</a></div>
<h1 id="ordering-functions"><a class="header" href="#ordering-functions">Ordering functions</a></h1>
<p>BQN has six functions that order arrays as part of their operation (the <a href="arithmetic.html#comparisons">comparison functions</a> <code><span class='Function'>≤<>≥</span></code> only order atoms, so they aren't included). These come in three pairs, where one of each pair uses an ascending ordering and the other uses a descending ordering.</p>
<ul>
<li><code><span class='Function'>∨∧</span></code>, Sort, puts major cells of <code><span class='Value'>𝕩</span></code> in order</li>
<li><code><span class='Function'>⍒⍋</span></code>, Grade, outputs the permutation that Sort would use to rearrange <code><span class='Value'>𝕩</span></code></li>
<li><code><span class='Function'>⍒⍋</span></code>, Bins, takes an ordered <code><span class='Value'>𝕨</span></code> and determines where each cell of <code><span class='Value'>𝕩</span></code> fits in this ordering.</li>
</ul>
<p>The array ordering shared by all six is described last. For lists it's "dictionary ordering": two lists are compared one element at a time until one runs out, and the shorter one comes first in case of a tie. Operation values aren't ordered, so if an argument to an ordering function has a function or modifier somewhere in it then it will fail unless all the orderings can be decided without checking that value.</p>
<p>You can't provide a custom ordering function to Sort. The function would have to be called on one pair of cells at a time, which is contrary to the idea of array programming, and passing in a function with side effects could lead to implementation-specific behavior. Instead, build another array that will sort in the order you want (for example, by selecting or deriving the property you want to sort on). Then Grade it, and use the result to select from the original array.</p>
<h2 id="sort"><a class="header" href="#sort">Sort</a></h2>
<p>You've probably seen it before. Sort Up (<code><span class='Function'>∧</span></code>) reorders the <a href="array.html#cells">major cells</a> of its argument to place them in ascending order, and Sort Down (<code><span class='Function'>∨</span></code>) puts them in descending order. Every ordering function follows this naming convention—there's an "Up" version pointing up and a "Down" version going the other way.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oinICJkZWx0YSLigL8iYWxwaGEi4oC/ImJldGEi4oC/ImdhbW1hIgoK4oioICLOtM6xzrLOsyI=">↗️</a><pre> <span class='Function'>∧</span> <span class='String'>"delta"</span><span class='Ligature'>‿</span><span class='String'>"alpha"</span><span class='Ligature'>‿</span><span class='String'>"beta"</span><span class='Ligature'>‿</span><span class='String'>"gamma"</span>
⟨ "alpha" "beta" "delta" "gamma" ⟩
<span class='Function'>∨</span> <span class='String'>"δαβγ"</span>
"δγβα"
</pre>
<p>Sort Down always <a href="match.html">matches</a> Sort Up <a href="reverse.html">reversed</a>, <code><span class='Function'>⌽</span><span class='Modifier2'>∘</span><span class='Function'>∧</span></code>. The reason for this is that BQN's array ordering is a <a href="https://en.wikipedia.org/wiki/Total_order">total order</a>, meaning that if one array doesn't come earlier or later than another array in the ordering then the two arrays match. Since any two non-matching argument cells are strictly ordered, they will have one ordering in <code><span class='Function'>∧</span></code> and the opposite ordering in <code><span class='Function'>∨</span></code>. After the reverse, any pair of non-matching cells are ordered the same way in <code><span class='Function'>⌽</span><span class='Modifier2'>∘</span><span class='Function'>∧</span></code> and <code><span class='Function'>∨</span></code>. Since these two results have the same major cells in the same order, they match. However, note that the results will not always behave identically because Match doesn't take <a href="fill.html">fill elements</a> into account (if you're curious, take a look at <code><span class='Function'>⊑</span><span class='Modifier'>¨</span><span class='Function'>∨</span><span class='Bracket'>⟨</span><span class='Function'>↕</span><span class='Number'>0</span><span class='Separator'>,</span><span class='String'>""</span><span class='Bracket'>⟩</span></code> versus <code><span class='Function'>⊑</span><span class='Modifier'>¨</span><span class='Function'>⌽</span><span class='Modifier2'>∘</span><span class='Function'>∧</span><span class='Bracket'>⟨</span><span class='Function'>↕</span><span class='Number'>0</span><span class='Separator'>,</span><span class='String'>""</span><span class='Bracket'>⟩</span></code>).</p>
<h2 id="grade"><a class="header" href="#grade">Grade</a></h2>
<svg viewBox='-186 -13.6 486 193.12'>
<g font-family='BQN,monospace' font-size='22px' text-anchor='middle'>
<rect class='code' stroke-width='1.5' rx='12' x='-108' y='0' width='330' height='165.92'/>
<g class='lilac' stroke-width='2' stroke-linecap='round'>
<line x1='55.2' x2='4.8' y1='54.4' y2='95.2'/>
<line x1='115.2' x2='64.8' y1='54.4' y2='95.2'/>
<line x1='9.6' x2='110.4' y1='54.4' y2='95.2'/>
<line x1='180' x2='180' y1='54.4' y2='95.2'/>
</g>
<g fill='currentColor' font-size='22'>
<g class='String'>
<text dy='0.32em' x='0' y='40.8'>'s'</text>
<text dy='0.32em' x='60' y='40.8'>'o'</text>
<text dy='0.32em' x='120' y='40.8'>'r'</text>
<text dy='0.32em' x='180' y='40.8'>'t'</text>
</g>
<g class='Number'>
<text dy='0.32em' x='0' y='108.8'>1</text>
<text dy='0.32em' x='60' y='108.8'>2</text>
<text dy='0.32em' x='120' y='108.8'>0</text>
<text dy='0.32em' x='180' y='108.8'>3</text>
</g>
<g class='String'>
<text dy='0.32em' x='0' y='138.72'>'o'</text>
<text dy='0.32em' x='60' y='138.72'>'r'</text>
<text dy='0.32em' x='120' y='138.72'>'s'</text>
<text dy='0.32em' x='180' y='138.72'>'t'</text>
</g>
</g>
<g fill='currentColor' font-size='14' opacity='0.8'>
<g class='Number'>
<text dy='0.32em' x='0' y='18.36'>0</text>
<text dy='0.32em' x='60' y='18.36'>1</text>
<text dy='0.32em' x='120' y='18.36'>2</text>
<text dy='0.32em' x='180' y='18.36'>3</text>
</g>
</g>
<g font-size='18px' text-anchor='end'>
<text dy='0.32em' x='-48' y='40.8'><tspan class='Value'>𝕩</tspan></text>
<text dy='0.32em' x='-48' y='108.8'><tspan class='Function'>⍋</tspan><tspan class='Value'>𝕩</tspan></text>
<text dy='0.32em' x='-48' y='138.72'><tspan class='Function'>∧</tspan><tspan class='Value'>𝕩</tspan></text>
</g>
</g>
</svg>
<p>Grade is more abstract than Sort. Rather than rearranging the argument's cells immediately, it returns a list of <a href="indices.html">indices</a> (more precisely, a permutation) giving the ordering that would sort them.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGwg4oaQICJwbGFuZXQi4oC/Im1vb24i4oC/InN0YXIi4oC/ImFzdGVyb2lkIgoK4oinIGwKCuKNiyBs">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>l</span> <span class='Gets'>←</span> <span class='String'>"planet"</span><span class='Ligature'>‿</span><span class='String'>"moon"</span><span class='Ligature'>‿</span><span class='String'>"star"</span><span class='Ligature'>‿</span><span class='String'>"asteroid"</span>
⟨ "planet" "moon" "star" "asteroid" ⟩
<span class='Function'>∧</span> <span class='Value'>l</span>
⟨ "asteroid" "moon" "planet" "star" ⟩
<span class='Function'>⍋</span> <span class='Value'>l</span>
⟨ 3 1 0 2 ⟩
</pre>
<p>Given our list <code><span class='Value'>l</span></code> of things in a solar system, Sort Up orders them by size, or maybe alphabetically. What does <code><span class='Function'>⍋</span><span class='Value'>l</span></code> do? Its result also orders these items, but instead of listing them directly, each element is the <em>index</em> of that cell in the argument. So the way to read it is that the first item in sorted order is cell <code><span class='Number'>3</span></code> of the argument, <code><span class='String'>"asteroid"</span></code>. The second is cell <code><span class='Number'>1</span></code>, <code><span class='String'>"moon"</span></code>, and the third—forget this, we made programming languages for a reason.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGwg4oaQICJwbGFuZXQi4oC/Im1vb24i4oC/InN0YXIi4oC/ImFzdGVyb2lkIgoo4o2LbCkg4oqPIGw=">↗️</a><pre> <span class='Paren'>(</span><span class='Function'>⍋</span><span class='Value'>l</span><span class='Paren'>)</span> <span class='Function'>⊏</span> <span class='Value'>l</span>
⟨ "asteroid" "moon" "planet" "star" ⟩
</pre>
<h3 id="ordinals"><a class="header" href="#ordinals">Ordinals</a></h3>
<svg viewBox='-186 -13.6 486 231.2'>
<g font-family='BQN,monospace' font-size='22px' text-anchor='middle'>
<rect class='code' stroke-width='1.5' rx='12' x='-108' y='0' width='330' height='204'/>
<g class='lilac' stroke-width='2' stroke-linecap='round'>
<line x1='55.2' x2='4.8' y1='54.4' y2='95.2'/>
<line x1='115.2' x2='64.8' y1='54.4' y2='95.2'/>
<line x1='9.6' x2='110.4' y1='54.4' y2='95.2'/>
<line x1='180' x2='180' y1='54.4' y2='95.2'/>
<line x1='110.4' x2='9.6' y1='122.4' y2='163.2'/>
<line x1='4.8' x2='55.2' y1='122.4' y2='163.2'/>
<line x1='64.8' x2='115.2' y1='122.4' y2='163.2'/>
<line x1='180' x2='180' y1='122.4' y2='163.2'/>
</g>
<g fill='currentColor' font-size='22'>
<g class='String'>
<text dy='0.32em' x='0' y='40.8'>'s'</text>
<text dy='0.32em' x='60' y='40.8'>'o'</text>
<text dy='0.32em' x='120' y='40.8'>'r'</text>
<text dy='0.32em' x='180' y='40.8'>'t'</text>
</g>
<g class='Number'>
<text dy='0.32em' x='0' y='108.8'>1</text>
<text dy='0.32em' x='60' y='108.8'>2</text>
<text dy='0.32em' x='120' y='108.8'>0</text>
<text dy='0.32em' x='180' y='108.8'>3</text>
</g>
<g class='String'>
<text dy='0.32em' x='0' y='176.8'>2</text>
<text dy='0.32em' x='60' y='176.8'>0</text>
<text dy='0.32em' x='120' y='176.8'>1</text>
<text dy='0.32em' x='180' y='176.8'>3</text>
</g>
</g>
<g fill='currentColor' font-size='14' opacity='0.8'>
<g class='Number'>
<text dy='0.32em' x='0' y='18.36'>0</text>
<text dy='0.32em' x='57.9' y='18.36'>1</text>
<text dy='0.32em' x='115.8' y='18.36'>2</text>
<text dy='0.32em' x='173.7' y='18.36'>3</text>
</g>
<g class='String'>
<text dy='0.32em' x='0' y='86.36'>0</text>
<text dy='0.32em' x='57.9' y='86.36'>1</text>
<text dy='0.32em' x='115.8' y='86.36'>2</text>
<text dy='0.32em' x='173.7' y='86.36'>3</text>
</g>
<g class='Number'>
<text dy='0.32em' x='0' y='154.36'>0</text>
<text dy='0.32em' x='57.9' y='154.36'>1</text>
<text dy='0.32em' x='115.8' y='154.36'>2</text>
<text dy='0.32em' x='173.7' y='154.36'>3</text>
</g>
</g>
<g font-size='18px' text-anchor='end'>
<text dy='0.32em' x='-48' y='40.8'><tspan class='Value'>𝕩</tspan></text>
<text dy='0.32em' x='-48' y='108.8'><tspan class='Function'>⍋</tspan><tspan class='Value'>𝕩</tspan></text>
<text dy='0.32em' x='-48' y='176.8'><tspan class='Function'>⍋⍋</tspan><tspan class='Value'>𝕩</tspan></text>
</g>
</g>
</svg>
<p>So the elements of the Grade of an array correspond to the cells of that array after it's sorted. It's tempting if you don't have the sorted list handy to try to match them up with major cells of the original array, but this never makes sense—there's no relationship. However, applying Grade <em>twice</em> gives us a list that does correspond to the original argument quite usefully: it says, for each major cell of that argument, what rank it has relative to the others (smallest is 0, next is 1, and so on, breaking ties in favor of which cell comes earlier in the argument). Experienced APL programmers call this pattern the "ordinals" idiom.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGwg4oaQICJwbGFuZXQi4oC/Im1vb24i4oC/InN0YXIi4oC/ImFzdGVyb2lkIgpsIOKJjSDijYvijYsgbA==">↗️</a><pre> <span class='Value'>l</span> <span class='Function'>≍</span> <span class='Function'>⍋⍋</span> <span class='Value'>l</span>
┌─
╵ "planet" "moon" "star" "asteroid"
2 1 3 0
┘
</pre>
<p>How does it work? First, let's note that <code><span class='Function'>⍋</span><span class='Value'>l</span></code> is a <em>permutation</em>: it contains exactly the numbers <code><span class='Function'>↕≠</span><span class='Value'>l</span></code>, possibly in a different order. In other words, <code><span class='Function'>∧⍋</span><span class='Value'>l</span></code> is <code><span class='Function'>↕≠</span><span class='Value'>l</span></code>. Permuting an array rearranges the cells but doesn't remove or duplicate any. This implies it's always invertible: given a permutation <code><span class='Value'>p</span></code>, some other permutation <code><span class='Value'>q</span></code> will have <code><span class='Value'>𝕩</span> <span class='Function'>≡</span> <span class='Value'>q</span><span class='Function'>⊏</span><span class='Value'>p</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code> for every <code><span class='Value'>𝕩</span></code> of the right length. This would mean that while <code><span class='Function'>⍋</span><span class='Value'>l</span></code> transforms <code><span class='Value'>l</span></code> to <code><span class='Function'>∧</span><span class='Value'>l</span></code>, the inverse of <code><span class='Function'>⍋</span><span class='Value'>l</span></code> transforms <code><span class='Function'>∧</span><span class='Value'>l</span></code> back into <code><span class='Value'>l</span></code>. That's what we want: for each cell of <code><span class='Value'>l</span></code>, the corresponding number in the inverse of <code><span class='Function'>⍋</span><span class='Value'>l</span></code> is what index that cell has after sorting.</p>
<p>But what's the inverse <code><span class='Value'>q</span></code> of a permutation <code><span class='Value'>p</span></code>? Our requirement is that <code><span class='Value'>𝕩</span> <span class='Function'>≡</span> <span class='Value'>q</span><span class='Function'>⊏</span><span class='Value'>p</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code> for any <code><span class='Value'>𝕩</span></code> with the same length as <code><span class='Value'>p</span></code>. Setting <code><span class='Value'>𝕩</span></code> to <code><span class='Function'>↕≠</span><span class='Value'>p</span></code> (the identity permutation), we have <code><span class='Paren'>(</span><span class='Function'>↕≠</span><span class='Value'>p</span><span class='Paren'>)</span> <span class='Function'>≡</span> <span class='Value'>q</span><span class='Function'>⊏</span><span class='Value'>p</span></code>, because <code><span class='Value'>p</span><span class='Function'>⊏↕≠</span><span class='Value'>p</span></code> is just <code><span class='Value'>p</span></code>. But if <code><span class='Value'>p</span></code> is a permutation then <code><span class='Function'>∧</span><span class='Value'>p</span></code> is <code><span class='Function'>↕≠</span><span class='Value'>p</span></code>, so our requirement could also be written <code><span class='Paren'>(</span><span class='Function'>∧</span><span class='Value'>p</span><span class='Paren'>)</span> <span class='Function'>≡</span> <span class='Value'>q</span><span class='Function'>⊏</span><span class='Value'>p</span></code>. Now it's all coming back around again. We know exactly how to get <code><span class='Value'>q</span></code>! Defining <code><span class='Value'>q</span><span class='Gets'>←</span><span class='Function'>⍋</span><span class='Value'>p</span></code>, we have <code><span class='Value'>q</span><span class='Function'>⊏</span><span class='Value'>p</span> <span class='Value'>↔</span> <span class='Paren'>(</span><span class='Function'>⍋</span><span class='Value'>p</span><span class='Paren'>)</span><span class='Function'>⊏</span><span class='Value'>p</span> <span class='Value'>↔</span> <span class='Function'>∧</span><span class='Value'>p</span> <span class='Value'>↔</span> <span class='Function'>↕≠</span><span class='Value'>p</span></code>, and <code><span class='Value'>q</span><span class='Function'>⊏</span><span class='Value'>p</span><span class='Function'>⊏</span><span class='Value'>𝕩</span> <span class='Value'>↔</span> <span class='Paren'>(</span><span class='Value'>q</span><span class='Function'>⊏</span><span class='Value'>p</span><span class='Paren'>)</span><span class='Function'>⊏</span><span class='Value'>𝕩</span> <span class='Value'>↔</span> <span class='Paren'>(</span><span class='Function'>↕≠</span><span class='Value'>p</span><span class='Paren'>)</span><span class='Function'>⊏</span><span class='Value'>𝕩</span> <span class='Value'>↔</span> <span class='Value'>𝕩</span></code>.</p>
<p>The fact that Grade Up inverts a permutation is useful in itself. Note that this applies to Grade Up specifically, and not Grade Down. This is because the identity permutation is ordered in ascending order. Grade Down would invert the reverse of a permutation, which is unlikely to be useful. So the ordinals idiom that goes in the opposite direction is actually not <code><span class='Function'>⍒⍒</span></code> but <code><span class='Function'>⍋⍒</span></code>. The initial grade is different, but the way to invert it is the same.</p>
<h3 id="stability"><a class="header" href="#stability">Stability</a></h3>
<p>When sorting an array, we usually don't care how matching cells are ordered relative to each other (although as mentioned above it's possible to detect it by using fill elements carefully. They maintain their ordering). Grading is a different matter, because often the grade of one array is used to order another one.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIHQg4oaQIFsgImRvZyLigL80LCAiYW50IuKAvzYsICJwaWdlb24i4oC/MiwgInBpZyLigL80IF0KCjEg4oqPy5ggdAoKKDHiio/LmHQpIOKNi+KKuOKKjyB0">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>t</span> <span class='Gets'>←</span> <span class='Bracket'>[</span> <span class='String'>"dog"</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Separator'>,</span> <span class='String'>"ant"</span><span class='Ligature'>‿</span><span class='Number'>6</span><span class='Separator'>,</span> <span class='String'>"pigeon"</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Separator'>,</span> <span class='String'>"pig"</span><span class='Ligature'>‿</span><span class='Number'>4</span> <span class='Bracket'>]</span>
┌─
╵ "dog" 4
"ant" 6
"pigeon" 2
"pig" 4
┘
<span class='Number'>1</span> <span class='Function'>⊏</span><span class='Modifier'>˘</span> <span class='Value'>t</span>
⟨ 4 6 2 4 ⟩
<span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>⊏</span><span class='Modifier'>˘</span><span class='Value'>t</span><span class='Paren'>)</span> <span class='Function'>⍋</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span> <span class='Value'>t</span>
┌─
╵ "pigeon" 2
"dog" 4
"pig" 4
"ant" 6
┘
</pre>
<p>Here we order a table by its second column. Maybe in this case it's not a problem if "dog" and "pig" trade places. But unpredictability is never good—would you get the same results with a different implementation of BQN? And for many other applications of Grade the ordering of equal elements is important. So BQN specifies that matching cells are always ordered by their indices. The same rule applies for Grade Down, so that for example the grade in <em>either</em> direction of an array <code><span class='Value'>𝕩</span></code> where all cells are the same is <code><span class='Function'>↕≠</span><span class='Value'>𝕩</span></code>. One effect is that <code><span class='Function'>⍋</span><span class='Value'>𝕩</span></code> is not always the same as <code><span class='Function'>⌽⍒</span><span class='Value'>𝕩</span></code>, even though <code><span class='Function'>∧</span><span class='Value'>𝕩</span></code> always matches <code><span class='Function'>⌽∨</span><span class='Value'>𝕩</span></code>. And in the table below we can see that the numbers are all reversed but "dog" and "pig" stay in the same order.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIHQg4oaQIFsgImRvZyLigL80LCAiYW50IuKAvzYsICJwaWdlb24i4oC/MiwgInBpZyLigL80IF0KKDHiio/LmHQpIOKNkuKKuOKKjyB0">↗️</a><pre> <span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>⊏</span><span class='Modifier'>˘</span><span class='Value'>t</span><span class='Paren'>)</span> <span class='Function'>⍒</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span> <span class='Value'>t</span>
┌─
╵ "ant" 6
"dog" 4
"pig" 4
"pigeon" 2
┘
</pre>
<p>To see some of the possibilities of Grade, you might pick apart the following expression, which is used to reverse elements of the right argument in groups of the given length.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=KOKMveKNki8z4oC/NOKAvzUpIOKKjyAiMDEyYWJjZEFCQ0RFIg==">↗️</a><pre> <span class='Paren'>(</span><span class='Function'>⌽⍒/</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Paren'>)</span> <span class='Function'>⊏</span> <span class='String'>"012abcdABCDE"</span>
"210dcbaEDCBA"
</pre>
<h2 id="bins"><a class="header" href="#bins">Bins</a></h2>
<svg viewBox='-168 -13.6 570 258.4'>
<g font-family='BQN,monospace' font-size='22px' text-anchor='middle'>
<rect class='code' stroke-width='1.5' rx='12' x='-108' y='0' width='450' height='231.2'/>
<g class='lilac' stroke-width='2' stroke-linecap='round'>
<line x1='23.238' x2='0.762' y1='70.72' y2='129.2'/>
<line x1='141.333' x2='62.667' y1='70.72' y2='129.2'/>
<line x1='-31.048' x2='115.048' y1='70.72' y2='129.2'/>
<line x1='28.952' x2='175.048' y1='70.72' y2='129.2'/>
<line x1='30.857' x2='233.143' y1='70.72' y2='129.2'/>
<line x1='207.048' x2='296.952' y1='70.72' y2='129.2'/>
<line x1='0' x2='0' y1='156.4' y2='183.6'/>
<line x1='60' x2='60' y1='156.4' y2='183.6'/>
<line x1='120' x2='120' y1='156.4' y2='183.6'/>
<line x1='180' x2='180' y1='156.4' y2='183.6'/>
<line x1='240' x2='240' y1='156.4' y2='183.6'/>
<line x1='300' x2='300' y1='156.4' y2='183.6'/>
</g>
<path class='green' style='fill:none' stroke-width='2' stroke-linecap='round' opacity='0.9' d='M-66.6 51h7.2m6 0h7.2m6 0h24m6 -18v21m0 -3h54m6 -18v21m0 -3h54m6 -18v21m0 -3h54m6 -18v21m0 -3h60m6 0h7.2m6 0h7.2'/>
<g fill='currentColor' font-size='22'>
<g class='String'>
<text dy='0.32em' x='-15' y='34'>"</text>
<text dy='0.32em' x='195' y='34'>"</text>
<text dy='0.32em' x='0' y='34'>b</text>
<text dy='0.32em' x='60' y='34'>i</text>
<text dy='0.32em' x='120' y='34'>n</text>
<text dy='0.32em' x='180' y='34'>s</text>
</g>
<g class='String'>
<text dy='0.32em' x='-15' y='142.8'>"</text>
<text dy='0.32em' x='315' y='142.8'>"</text>
<text dy='0.32em' x='0' y='142.8'>g</text>
<text dy='0.32em' x='60' y='142.8'>r</text>
<text dy='0.32em' x='120' y='142.8'>a</text>
<text dy='0.32em' x='180' y='142.8'>d</text>
<text dy='0.32em' x='240' y='142.8'>e</text>
<text dy='0.32em' x='300' y='142.8'>s</text>
</g>
<g class='Number'>
<text dy='0.32em' x='0' y='197.2'>1</text>
<text dy='0.32em' x='60' y='197.2'>3</text>
<text dy='0.32em' x='120' y='197.2'>0</text>
<text dy='0.32em' x='180' y='197.2'>1</text>
<text dy='0.32em' x='240' y='197.2'>1</text>
<text dy='0.32em' x='300' y='197.2'>4</text>
</g>
</g>
<g fill='currentColor' font-size='16' opacity='0.8' class='Number'>
<text dy='0.32em' x='-36' y='60.52'>0</text>
<text dy='0.32em' x='24' y='60.52'>1</text>
<text dy='0.32em' x='84' y='60.52'>2</text>
<text dy='0.32em' x='144' y='60.52'>3</text>
<text dy='0.32em' x='204' y='60.52'>4</text>
</g>
<g font-size='18px' text-anchor='end'>
<text dy='0.32em' x='-48' y='34'><tspan class='Value'>𝕨</tspan></text>
<text dy='0.32em' x='-48' y='142.8'><tspan class='Value'>𝕩</tspan></text>
<text dy='0.32em' x='-48' y='197.2'><tspan class='Value'>𝕨</tspan><tspan class='Function'>⍋</tspan><tspan class='Value'>𝕩</tspan></text>
</g>
</g>
</svg>
<p>The two Bins functions are written with the same symbols <code><span class='Function'>⍋</span></code> and <code><span class='Function'>⍒</span></code> as Grade, but take two arguments instead of one. More complicated? A little, but once you understand Bins you'll find that it's a basic concept that shows up in the real world all the time.</p>
<p>Bins behaves like a <a href="search.html">search function</a> with respect to rank: it looks up <a href="array.html#cells">cells</a> from <code><span class='Value'>𝕩</span></code> relative to major cells of <code><span class='Value'>𝕨</span></code>. However, there's an extra requirement: the left argument to Bins must already be sorted according to whichever ordering is used. If it isn't, you'll get an error.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=NeKAvzbigL8y4oC/NOKAvzEg4o2LIDMKCjDigL8z4oC/NOKAvzfigL85IOKNkiAz">↗️</a><pre> <span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>6</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>1</span> <span class='Function'>⍋</span> <span class='Number'>3</span>
<span class='Error'>Error: ⍋: 𝕨 must be sorted</span>
<span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>7</span><span class='Ligature'>‿</span><span class='Number'>9</span> <span class='Function'>⍒</span> <span class='Number'>3</span>
<span class='Error'>Error: ⍒: 𝕨 must be sorted in descending order</span>
</pre>
<p>Given this, the simplest definition of <code><span class='Value'>𝕨</span><span class='Function'>⍋</span><span class='Value'>𝕩</span></code> (or <code><span class='Value'>𝕨</span><span class='Function'>⍒</span><span class='Value'>𝕩</span></code>) is that for each cell in <code><span class='Value'>𝕩</span></code> of rank <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>, it counts the number of major cells from <code><span class='Value'>𝕨</span></code> that come earlier in the ordering, or match that cell.</p>
<p>Why would that be useful? How about an example. A pinball machine has some high scores on it. You play, and your rank is the number of scores higher than yours (in this case, if you tie someone's score, you won't unseat them).</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=aHMg4oaQIDFlN8OXNjI34oC/NTgx4oC/NTc44oC/NTUz4oC/NTIwICAjIEhpZ2ggc2NvcmVzCgpocyDijZIgMWU3w5c1NjXigL8zMjLigL83ODjigL82Mjc=">↗️</a><pre> <span class='Value'>hs</span> <span class='Gets'>←</span> <span class='Number'>1e7</span><span class='Function'>×</span><span class='Number'>627</span><span class='Ligature'>‿</span><span class='Number'>581</span><span class='Ligature'>‿</span><span class='Number'>578</span><span class='Ligature'>‿</span><span class='Number'>553</span><span class='Ligature'>‿</span><span class='Number'>520</span> <span class='Comment'># High scores
</span>
<span class='Value'>hs</span> <span class='Function'>⍒</span> <span class='Number'>1e7</span><span class='Function'>×</span><span class='Number'>565</span><span class='Ligature'>‿</span><span class='Number'>322</span><span class='Ligature'>‿</span><span class='Number'>788</span><span class='Ligature'>‿</span><span class='Number'>627</span>
⟨ 3 5 0 1 ⟩
</pre>
<p>A score of <code><span class='Number'>565e7</span></code> sits between <code><span class='Number'>578e7</span></code> and <code><span class='Number'>553e7</span></code> at rank 3, <code><span class='Number'>322e7</span></code> wouldn't make the list, <code><span class='Number'>788e7</span></code> would beat everyone, and <code><span class='Number'>627e7</span></code> would tie the high score but not beat it. The same principles apply to less spring-loaded things like character indices and line numbers (<code><span class='Value'>𝕨</span></code> is the index of the start of each line), or percentage scores and letter grades on a test (<code><span class='Value'>𝕨</span></code> is the minimum score possible for each grade). In each case, it's better to think of Bins not as a counting exercise but as finding "what bin" something fits into.</p>
<h2 id="array-ordering"><a class="header" href="#array-ordering">Array ordering</a></h2>
<p>Most of the time you won't need to worry about the details of how BQN arrays are ordered. It's documented here because, well, that's what documentation does.</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 <a href="array.html">arrays</a>. In this system, any two arrays that have only numbers and characters for atoms can be compared with each other. Furthermore, some arrays that contain incomparable atoms (operations or namespaces) might be comparable, if the result of the comparison can be decided before reaching these atoms. Array ordering never depends on <a href="fill.html">fill elements</a>. If comparing two arrays succeeds, there are three possibilities: the first array is smaller, the second is smaller, or the two arrays <a href="match.html">match</a>. All of the "Up" ordering functions use this ordering directly, so that smaller arrays come earlier, and the "Down" ones use the opposite ordering, with larger arrays coming earlier.</p>
<p>Comparing two atoms is defined to work the same way as the <a href="arithmetic.html#comparisons">comparison functions</a> <code><span class='Function'>≤<>≥</span></code>. 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.</p>
<p>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.</p>
<p>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.</p>
<svg viewBox='-168 -68 594 272'>
<rect class='code' stroke-width='1.5' rx='12' x='-72' y='-54.4' width='402' height='244.8'/>
<g class='bluegreen' stroke-width='2' opacity='0.4'><rect x='-30' y='-34' width='180' height='204'/></g>
<g class='yellow' stroke-width='2' opacity='0.4'><rect x='-12' y='-20.4' width='300' height='136'/></g>
<g font-family='BQN,monospace' font-size='22px' text-anchor='middle'>
<g class='bluegreen'>
<text dy='0.32em' x='0' y='0'>a</text>
<text dy='0.32em' x='60' y='0'>b</text>
<text dy='0.32em' x='120' y='0'>c</text>
<text dy='0.32em' x='0' y='68'>d</text>
<text dy='0.32em' x='60' y='68'>e</text>
<text dy='0.32em' x='120' y='68'>f</text>
<text dy='0.32em' x='0' y='136'>g</text>
<text dy='0.32em' x='60' y='136'>h</text>
<text dy='0.32em' x='120' y='136'>i</text>
</g>
<g class='yellow'>
<text dy='0.32em' x='18' y='13.6'>a</text>
<text dy='0.32em' x='78' y='13.6'>b</text>
<text dy='0.32em' x='138' y='13.6'>d</text>
<text dy='0.32em' x='198' y='13.6'>e</text>
<text dy='0.32em' x='258' y='13.6'>g</text>
<text dy='0.32em' x='18' y='81.6'>h</text>
<text dy='0.32em' x='78' y='81.6'>j</text>
<text dy='0.32em' x='138' y='81.6'>l</text>
<text dy='0.32em' x='198' y='81.6'>p</text>
<text dy='0.32em' x='258' y='81.6'>o</text>
</g>
</g>
<rect class='lilac' stroke-width='3' x='-12' y='-20.4' width='162' height='54.4'/>
<circle class='red' stroke-width='3' style='fill:none' r='22' cx='129' cy='6.8'/>
<g font-size='14' text-anchor='middle' fill='currentColor'>
<text dy='0.32em' x='69' y='42.16'>≤3 compared values</text>
<text dy='0.32em' x='-12' y='170'>3×3</text>
<text dy='0.32em' x='264' y='-20.4'>2×5</text>
</g>
</svg>
<p>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 <code><span class='Function'>⊑</span></code>) elements. So a shape <code><span class='Bracket'>⟨</span><span class='Number'>4</span><span class='Bracket'>⟩</span></code> array will match up with the first row of a shape <code><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>3</span></code> 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 <code><span class='Number'>1</span></code>s 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 <code><span class='Bracket'>⟨</span><span class='Number'>4</span><span class='Bracket'>⟩</span></code> and <code><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>3</span></code>, 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 <code><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>3</span></code> array would be considered smaller without even looking at its other four rows.</p>
<p>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 <code><span class='Number'>1</span></code>s 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.</p>
|
