aboutsummaryrefslogtreecommitdiff
path: root/docs/doc/order.html
diff options
context:
space:
mode:
authorMarshall Lochbaum <mwlochbaum@gmail.com>2021-08-11 17:21:31 -0400
committerMarshall Lochbaum <mwlochbaum@gmail.com>2021-08-11 17:25:04 -0400
commit2afb23928e1984d475cc460e1672e8f6fa0e4dbe (patch)
treeebd2cc514294d30b6fa4b36c2ee638326f06ef72 /docs/doc/order.html
parenteac61ca02074c218667754d5f4ef562e780bae85 (diff)
Allow clicking on header to get fragment link
Diffstat (limited to 'docs/doc/order.html')
-rw-r--r--docs/doc/order.html14
1 files changed, 7 insertions, 7 deletions
diff --git a/docs/doc/order.html b/docs/doc/order.html
index 1737ebd1..bd13f64a 100644
--- a/docs/doc/order.html
+++ b/docs/doc/order.html
@@ -4,7 +4,7 @@
<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">Ordering functions</h1>
+<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'>≤&lt;&gt;≥</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, rearranges the argument to order it</li>
@@ -13,7 +13,7 @@
</ul>
<p>The array ordering shared by all six is described last. For lists it's &quot;dictionary ordering&quot;: 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">Sort</h2>
+<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 major cells 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 &quot;Up&quot; version pointing up and a &quot;Down&quot; 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'>&quot;delta&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;alpha&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;beta&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;gamma&quot;</span>
⟨ "alpha" "beta" "delta" "gamma" ⟩
@@ -22,7 +22,7 @@
"δγβα"
</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 that 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>. With 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'>&quot;&quot;</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'>&quot;&quot;</span><span class='Bracket'>⟩</span></code>).</p>
-<h2 id="grade">Grade</h2>
+<h2 id="grade"><a class="header" href="#grade">Grade</a></h2>
<p><em>See the <a href="https://aplwiki.com/wiki/Grade">APL Wiki page</a> for a few more examples. BQN only has the monadic form.</em></p>
<p>Grade is more abstract than Sort. Rather than rearranging the argument's cells immediately, it returns a list of indices (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'>&quot;planet&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;moon&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;star&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;asteroid&quot;</span>
@@ -38,7 +38,7 @@
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=KOKNi2wpIOKKjyBs">↗️</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">Ordinals</h3>
+<h3 id="ordinals"><a class="header" href="#ordinals">Ordinals</a></h3>
<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 &quot;ordinals&quot; idiom.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=bCDiiY0g4o2L4o2LIGw=">↗️</a><pre> <span class='Value'>l</span> <span class='Function'>≍</span> <span class='Function'>⍋⍋</span> <span class='Value'>l</span>
┌─
@@ -49,7 +49,7 @@
<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 actually 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">Stability</h3>
+<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 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=4oqiIHQg4oaQID7in6ggImRvZyLigL80LCAiYW50IuKAvzYsICJwaWdlb24i4oC/MiwgInBpZyLigL80IOKfqQoKMSDiio/LmCB0CgooMeKKj8uYdCkg4o2L4oq44oqPIHQ=">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>t</span> <span class='Gets'>←</span> <span class='Function'>&gt;</span><span class='Bracket'>⟨</span> <span class='String'>&quot;dog&quot;</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Separator'>,</span> <span class='String'>&quot;ant&quot;</span><span class='Ligature'>‿</span><span class='Number'>6</span><span class='Separator'>,</span> <span class='String'>&quot;pigeon&quot;</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Separator'>,</span> <span class='String'>&quot;pig&quot;</span><span class='Ligature'>‿</span><span class='Number'>4</span> <span class='Bracket'>⟩</span>
┌─
@@ -83,7 +83,7 @@
<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'>&quot;012abcdABCDE&quot;</span>
"210dcbaEDCBA"
</pre>
-<h2 id="bins">Bins</h2>
+<h2 id="bins"><a class="header" href="#bins">Bins</a></h2>
<p><em>There's also an <a href="https://aplwiki.com/wiki/Interval_Index">APL Wiki page</a> on this function, but be careful as the Dyalog version has subtle differences.</em></p>
<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 cells 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 is already sorted according to whichever ordering is used. If it isn't, you'll get an error.</p>
@@ -100,7 +100,7 @@ ERROR
⟨ 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 &quot;what bin&quot; something fits into.</p>
-<h2 id="array-ordering">Array ordering</h2>
+<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>The array ordering defines some arrays to be smaller or larger than others. All of the &quot;Up&quot; ordering functions use this ordering directly, so that smaller arrays come earlier, and the &quot;Down&quot; ones use the opposite ordering, with larger arrays coming earlier. For arrays consisting only of characters and numbers, with arbitrary nesting, the ordering is always defined. If an array contains an operation, trying to order it relative to another array might give an error. 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>.</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'>≤&lt;&gt;≥</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 enclosing 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>