diff options
| author | Marshall Lochbaum <mwlochbaum@gmail.com> | 2022-06-07 22:16:01 -0400 |
|---|---|---|
| committer | Marshall Lochbaum <mwlochbaum@gmail.com> | 2022-06-07 22:16:01 -0400 |
| commit | bed78fe6147cb7921b7367960d406d28d37cb019 (patch) | |
| tree | 5fd5f3ad00bfbd66b19aabc4a3d688815754be1e /docs/doc/selfcmp.html | |
| parent | 07be54d8179ba799cc55dacd2c79fb2292477030 (diff) | |
The editing is going to end at some point isn't it?
Diffstat (limited to 'docs/doc/selfcmp.html')
| -rw-r--r-- | docs/doc/selfcmp.html | 45 |
1 files changed, 21 insertions, 24 deletions
diff --git a/docs/doc/selfcmp.html b/docs/doc/selfcmp.html index e5a8aa84..05490758 100644 --- a/docs/doc/selfcmp.html +++ b/docs/doc/selfcmp.html @@ -131,7 +131,7 @@ </g> </svg> -<p>BQN has four self-search functions, Classify (<code><span class='Function'>⊐</span></code>), Occurrence Count (<code><span class='Function'>⊒</span></code>), Mark Firsts (<code><span class='Function'>∊</span></code>), and Deduplicate (<code><span class='Function'>⍷</span></code>). Each of these is a monadic function that obtains its result by comparing each major cell of the argument (which must have rank at least 1) to the earlier major cells with <a href="match.html">match</a>. For example, Mark Firsts indicates the cells that don't match any earlier cell, making them the first of their kind.</p> +<p>BQN has four self-search functions, Classify (<code><span class='Function'>⊐</span></code>), Occurrence Count (<code><span class='Function'>⊒</span></code>), Mark Firsts (<code><span class='Function'>∊</span></code>), and Deduplicate (<code><span class='Function'>⍷</span></code>). Each of these is a monadic function that obtains its result by comparing each <a href="array.html#cells">major cell</a> of the argument (which must have rank at least 1) to the earlier major cells with <a href="match.html">match</a>. For example, Mark Firsts indicates the cells that don't match any earlier cell, which might be called the first of their kind.</p> <a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oiKICJhYmFhY2Ii">↗️</a><pre> <span class='Function'>∊</span> <span class='String'>"abaacb"</span> ⟨ 1 1 0 0 1 0 ⟩ </pre> @@ -148,6 +148,22 @@ ⟨ 1 1 0 1 0 ⟩ </pre> <p>The result has one number for each major cell, or in other words is a list with the same length as its argument. Three self-search functions follow this pattern, but Deduplicate (<code><span class='Function'>⍷</span></code>) is different: it returns an array of the same rank but possibly a shorter length than the argument.</p> +<h3 id="deduplicate"><a class="header" href="#deduplicate">Deduplicate</a></h3> +<p>Deduplicate removes every major cell from the argument that matches an earlier cell, resulting in an array with the same rank but possibly a shorter length. It might also be described as returning the unique major cells of the argument, ordered by first occurrence. Deduplicate <a href="under.html">Under</a> <a href="reverse.html">Reverse</a> (<code><span class='Function'>⍷</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span></code>) orders by last occurrence instead.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4o23ID4idGFrZSLigL8iZHJvcCLigL8iZHJvcCLigL8icGljayLigL8idGFrZSLigL8idGFrZSIKCuKNt+KMvuKMvSA+InRha2Ui4oC/ImRyb3Ai4oC/ImRyb3Ai4oC/InBpY2si4oC/InRha2Ui4oC/InRha2Ui">↗️</a><pre> <span class='Function'>⍷</span> <span class='Function'>></span><span class='String'>"take"</span><span class='Ligature'>‿</span><span class='String'>"drop"</span><span class='Ligature'>‿</span><span class='String'>"drop"</span><span class='Ligature'>‿</span><span class='String'>"pick"</span><span class='Ligature'>‿</span><span class='String'>"take"</span><span class='Ligature'>‿</span><span class='String'>"take"</span> +┌─ +╵"take + drop + pick" + ┘ + + <span class='Function'>⍷</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span> <span class='Function'>></span><span class='String'>"take"</span><span class='Ligature'>‿</span><span class='String'>"drop"</span><span class='Ligature'>‿</span><span class='String'>"drop"</span><span class='Ligature'>‿</span><span class='String'>"pick"</span><span class='Ligature'>‿</span><span class='String'>"take"</span><span class='Ligature'>‿</span><span class='String'>"take"</span> +┌─ +╵"drop + pick + take" + ┘ +</pre> <h2 id="classify"><a class="header" href="#classify">Classify</a></h2> <p>Classify is the universal self-search function, in that it preserves all the self-search information in its argument. It gives each different cell value a natural number, ordered by first appearance.</p> <a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqQIDXigL824oC/MuKAvzLigL814oC/MQ==">↗️</a><pre> <span class='Function'>⊐</span> <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'>2</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>1</span> @@ -185,7 +201,7 @@ <span class='Function'>⊐</span> <span class='Function'>⍷</span> <span class='Value'>c</span> ⟨ 0 1 2 ⟩ </pre> -<p>Applying both separately, in contrast, gives completely interesting results. These results contain all information from the original argument, as <code><span class='Function'>⍷</span></code> indicates which cells it contained and <code><span class='Function'>⊐</span></code> indicates where they were located. The function <a href="select.html">Select</a> (<code><span class='Function'>⊏</span></code>) reconstructs the argument from the two values.</p> +<p>Applying both separately is a different story, and gives completely interesting results. These results contain all information from the original argument, as <code><span class='Function'>⍷</span></code> indicates which cells it contained and <code><span class='Function'>⊐</span></code> indicates where they were located. The function <a href="select.html">Select</a> (<code><span class='Function'>⊏</span></code>) reconstructs the argument from the two values.</p> <a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4o23IGMK4oqQIGMKKOKKkGMpIOKKjyAo4o23Yyk=">↗️</a><pre> <span class='Function'>⍷</span> <span class='Value'>c</span> ┌─ ╵"yellow @@ -204,11 +220,10 @@ yellow" ┘ </pre> -<p>One way to view this relationship is to consider an idea from linear algebra, where an idempotent transformation is called a "projection". That means that the argument might be any value but the result is part of a smaller class of values, and any argument from that smaller class is left the same. What arrays do the two functions project to? The result of Deduplicate is an array with no repeated major cells. The result of Classify is a list of natural numbers, but it also has an additional property: each number in the list is at most one higher than the previous numbers, and the first number is zero. This comes from the way Classify numbers the cells of its argument. When it finds a cell that hasn't appeared before (at a lower index), it always chooses the next higher number for it.</p> -<p>Applying both Classify and Deduplicate gives an array that has both properties (this isn't the case for all pairs of projections—we need to know that Classify maintains the uniqueness property for Deduplicate and vice-versa). It has no duplicate major cells, <em>and</em> it's a list of natural numbers that starts with 0 and never goes up by more than one. Taken together, these are a tight constraint! The first element of the argument has to be 0. The next can't be 0 because it's already appeared, but it can't be more than one higher—it has to be 1. The next can't be 0 or 1, and has to be 2. And so on. So the result is always <code><span class='Function'>↕</span><span class='Value'>n</span></code> for some <code><span class='Value'>n</span></code>. In fact it's possible to determine the length as well, by noting that each function preserves the number of unique major cells in its argument. Classify does this because distinct numbers in the output correspond exactly to distinct major cells in the input; Deduplicate does this because it only removes duplicate cells, not distinct ones. So the final result is <code><span class='Function'>↕</span><span class='Value'>n</span></code>, where <code><span class='Value'>n</span></code> is the number of unique major cells in the argument.</p> +<p>One way to view this relationship is from the perspective of linear algebra, where an idempotent transformation is called a "projection". That means that the argument might be any value but the result is part of a smaller class of values, and any argument from that smaller class is left the same. What arrays do the two functions project to? The result of Deduplicate is an array with no repeated major cells. The result of Classify is a list of natural numbers, but it also has an additional property: each number in the list is at most one higher than the previous numbers, and the first number is zero. This comes from the way Classify numbers the cells of its argument. When it finds a cell that hasn't appeared before (at a lower index), it always chooses the next higher number for it.</p> +<p>Applying both Classify and Deduplicate gives an array that has both properties (this isn't the case for all pairs of projections—we need to know that Classify maintains the uniqueness property for Deduplicate and vice-versa). It has no duplicate major cells, <em>and</em> it's a list of natural numbers that starts with 0 and never goes up by more than one. Taken together, these are a tight constraint! The first element of the argument has to be 0. The next can't be 0 because it's already appeared, but it can't be more than one higher—it has to be 1. The next can't be 0 or 1, and has to be 2. And so on. So the result is always <code><span class='Function'>↕</span><span class='Value'>n</span></code> for some <code><span class='Value'>n</span></code>. It's possible to determine the length as well, by noting that each function preserves the number of unique major cells in its argument. Classify does this because distinct numbers in the output correspond exactly to distinct major cells in the input; Deduplicate does this because it only removes duplicate cells, not distinct ones. So the final result is <code><span class='Function'>↕</span><span class='Value'>n</span></code>, where <code><span class='Value'>n</span></code> is the number of unique major cells in the argument.</p> <h3 id="mark-firsts"><a class="header" href="#mark-firsts">Mark Firsts</a></h3> -<p><em>See the <a href="https://aplwiki.com/wiki/Unique_Mask">APL Wiki page</a> on this function as well.</em></p> -<p>Mark Firsts (<code><span class='Function'>∊</span></code>) is the simplest self-search function: it returns <code><span class='Number'>0</span></code> for any major cell of the argument that is a duplicate of an earlier cell and <code><span class='Number'>1</span></code> for a major cell that's the first with its value. To implement <a href="#deduplicate">Deduplicate</a> in terms of Mark Firsts, just <a href="replicate.html">filter</a> out the duplicates with <code><span class='Function'>∊</span><span class='Modifier2'>⊸</span><span class='Function'>/</span></code>.</p> +<p>Mark Firsts (<code><span class='Function'>∊</span></code>) is the simplest numeric self-search function: it returns <code><span class='Number'>0</span></code> for any major cell of the argument that is a duplicate of an earlier cell and <code><span class='Number'>1</span></code> for a major cell that's the first with its value. To implement <a href="#deduplicate">Deduplicate</a> in terms of Mark Firsts, just <a href="replicate.html">filter</a> out the duplicates with <code><span class='Function'>∊</span><span class='Modifier2'>⊸</span><span class='Function'>/</span></code>.</p> <a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oiKICAgM+KAvzHigL804oC/MeKAvzXigL854oC/MuKAvzbigL81CgriiIriirgvIDPigL8x4oC/NOKAvzHigL814oC/OeKAvzLigL824oC/NQ==">↗️</a><pre> <span class='Function'>∊</span> <span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>9</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>6</span><span class='Ligature'>‿</span><span class='Number'>5</span> ⟨ 1 1 1 0 1 1 1 1 0 ⟩ @@ -248,21 +263,3 @@ ⟨ 0 1 0 1 2 0 1 2 3 ⟩ </pre> <p>A more efficient way when <code><span class='Function'>⊒</span></code> doesn't have a fast implementation is <code><span class='Function'>/</span><span class='Paren'>(</span><span class='Number'>¯1</span><span class='Modifier2'>⊸</span><span class='Function'>⊑↕</span><span class='Modifier2'>⊸</span><span class='Function'>-⊏</span><span class='Modifier2'>⟜</span><span class='Function'>»</span><span class='Paren'>)</span><span class='Function'>+</span><span class='Modifier'>`</span></code>, but that's clearly quite a bit more complicated.</p> -<h3 id="deduplicate"><a class="header" href="#deduplicate">Deduplicate</a></h3> -<p><em>There's also an <a href="https://aplwiki.com/wiki/Unique">APL Wiki page</a> on this function.</em></p> -<p>Deduplicate removes every major cell from the argument that matches an earlier cell, resulting in an array with the same rank but possibly a shorter length. It might also be described as returning the unique major cells of the argument, ordered by first occurrence. Deduplicate <a href="under.html">Under</a> Reverse (<code><span class='Function'>⍷</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span></code>) orders by last occurrence instead.</p> -<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4o23ID4idGFrZSLigL8iZHJvcCLigL8iZHJvcCLigL8icGljayLigL8idGFrZSLigL8idGFrZSIKCuKNt+KMvuKMvSA+InRha2Ui4oC/ImRyb3Ai4oC/ImRyb3Ai4oC/InBpY2si4oC/InRha2Ui4oC/InRha2Ui">↗️</a><pre> <span class='Function'>⍷</span> <span class='Function'>></span><span class='String'>"take"</span><span class='Ligature'>‿</span><span class='String'>"drop"</span><span class='Ligature'>‿</span><span class='String'>"drop"</span><span class='Ligature'>‿</span><span class='String'>"pick"</span><span class='Ligature'>‿</span><span class='String'>"take"</span><span class='Ligature'>‿</span><span class='String'>"take"</span> -┌─ -╵"take - drop - pick" - ┘ - - <span class='Function'>⍷</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span> <span class='Function'>></span><span class='String'>"take"</span><span class='Ligature'>‿</span><span class='String'>"drop"</span><span class='Ligature'>‿</span><span class='String'>"drop"</span><span class='Ligature'>‿</span><span class='String'>"pick"</span><span class='Ligature'>‿</span><span class='String'>"take"</span><span class='Ligature'>‿</span><span class='String'>"take"</span> -┌─ -╵"drop - pick - take" - ┘ -</pre> -<p>The relationship between Classify and Deduplicate is discussed <a href="#classify-and-deduplicate">above</a>.</p> |