aboutsummaryrefslogtreecommitdiff
path: root/docs/doc/group.html
diff options
context:
space:
mode:
authorMarshall Lochbaum <mwlochbaum@gmail.com>2021-07-06 22:18:20 -0400
committerMarshall Lochbaum <mwlochbaum@gmail.com>2021-07-06 22:18:20 -0400
commit4d602ea36183e62e463cea08900a16ea6240a03f (patch)
treef21aef763d907d7e1b093cf633c544cfcdd0a085 /docs/doc/group.html
parent97e31a20cefe21c1627f33057d20d7970511754f (diff)
Editing and links
Diffstat (limited to 'docs/doc/group.html')
-rw-r--r--docs/doc/group.html20
1 files changed, 10 insertions, 10 deletions
diff --git a/docs/doc/group.html b/docs/doc/group.html
index 37d5a5ed..a6f4b341 100644
--- a/docs/doc/group.html
+++ b/docs/doc/group.html
@@ -5,7 +5,7 @@
</head>
<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../index.html">main</a> / <a href="index.html">doc</a></div>
<h1 id="group">Group</h1>
-<p>BQN replaces the <a href="https://aplwiki.com/wiki/Key">Key</a> operator from J or Dyalog APL, and <a href="https://aplwiki.com/wiki/Partition_representations">many forms of partitioning</a>, with a single (ambivalent) Group function <code><span class='Function'>⊔</span></code>. This function is somewhat related to the K function <code><span class='Function'>=</span></code> of the same name, but results in an array rather than a dictionary.</p>
+<p>BQN replaces the Key operator from J or Dyalog APL, and <a href="https://aplwiki.com/wiki/Partition_representations">many forms of partitioning</a>, with a single (ambivalent) Group function <code><span class='Function'>⊔</span></code>. This function is somewhat related to the K function <code><span class='Function'>=</span></code> of the same name, but results in an array rather than a dictionary.</p>
<svg viewBox='-344 -121.8 640 226.8'>
<g text-anchor='middle' font-family='BQN,monospace'>
<rect class='code' stroke-width='1' rx='12' x='-280' y='-102.2' width='512' height='204.4'/>
@@ -103,7 +103,7 @@
</pre>
<p>Here, the index 2 appears at indices 0 and 3 while the index 3 appears at index 1.</p>
<h3 id="multidimensional-grouping">Multidimensional grouping</h3>
-<p>Dyadic Group allows the right argument to be grouped along multiple axes by using a nested left argument. In this case, the left argument must be a list of numeric lists, and the result has rank <code><span class='Function'>≠</span><span class='Value'>𝕨</span></code> while its elements—as always—have the same rank as <code><span class='Value'>𝕩</span></code>. The result shape is <code><span class='Number'>1</span><span class='Function'>+⌈</span><span class='Modifier'>´¨</span><span class='Value'>𝕨</span></code>, while the shape of element <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code> is <code><span class='Value'>i</span><span class='Function'>+</span><span class='Modifier'>´</span><span class='Modifier2'>∘</span><span class='Function'>=</span><span class='Modifier'>¨</span><span class='Value'>𝕨</span></code>. If every element of <code><span class='Value'>𝕨</span></code> is sorted ascending and contains only non-negative numbers, we have <code><span class='Value'>𝕩</span><span class='Function'>≡∾</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code>, that is, Join is the inverse of Partition.</p>
+<p>Dyadic Group allows the right argument to be grouped along multiple axes by using a nested left argument. In this case, the left argument must be a list of numeric lists, and the result has rank <code><span class='Function'>≠</span><span class='Value'>𝕨</span></code> while its elements—as always—have the same rank as <code><span class='Value'>𝕩</span></code>. The result shape is <code><span class='Number'>1</span><span class='Function'>+⌈</span><span class='Modifier'>´¨</span><span class='Value'>𝕨</span></code>, while the shape of element <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code> is <code><span class='Value'>i</span><span class='Function'>+</span><span class='Modifier'>´</span><span class='Modifier2'>∘</span><span class='Function'>=</span><span class='Modifier'>¨</span><span class='Value'>𝕨</span></code>. If every element of <code><span class='Value'>𝕨</span></code> is sorted ascending and contains only non-negative numbers, we have <code><span class='Value'>𝕩</span><span class='Function'>≡∾</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code>, that is, <a href="join.html#join">Join</a> is the inverse of Partition.</p>
<p>Here we split up a rank-2 array into a rank-2 array of rank-2 arrays. Along the first axis we simply separate the first pair and second pair of rows—a partition. Along the second axis we separate odd from even indices.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4p+oMOKAvzDigL8x4oC/MSww4oC/MeKAvzDigL8x4oC/MOKAvzHigL8w4p+pIOKKlCAoMTDDl+KGlTQpK+KMnOKGlTc=">↗️</a><pre> <span class='Bracket'>⟨</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Separator'>,</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Bracket'>⟩</span> <span class='Function'>⊔</span> <span class='Paren'>(</span><span class='Number'>10</span><span class='Function'>×↕</span><span class='Number'>4</span><span class='Paren'>)</span><span class='Function'>+</span><span class='Modifier'>⌜</span><span class='Function'>↕</span><span class='Number'>7</span>
┌─
@@ -120,25 +120,25 @@
<p>Each group <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code> is composed of the cells <code><span class='Value'>j</span><span class='Function'>&lt;</span><span class='Modifier'>¨</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code> such that <code><span class='Value'>i</span><span class='Function'>≢</span><span class='Value'>j</span><span class='Function'>⊑</span><span class='Modifier'>¨</span><span class='Value'>𝕨</span></code>. The groups retain their array structure and ordering along each argument axis. Using multidimensional Replicate we can say that <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code> is <code><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>=</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Function'>/</span><span class='Value'>𝕩</span></code>.</p>
<p>The monadic case works similarly: Group Indices always satisfies <code><span class='Function'>⊔</span><span class='Value'>𝕩</span> <span class='Gets'>←→</span> <span class='Value'>𝕩</span><span class='Function'>⊔↕≠</span><span class='Modifier2'>⚇</span><span class='Number'>1</span><span class='Value'>𝕩</span></code>. As with <code><span class='Function'>↕</span></code>, the depth of the result of Group Indices is always one greater than that of its argument. A depth-0 argument is not allowed.</p>
<h2 id="properties">Properties</h2>
-<p>Group is closely related to the inverse of Indices, <code><span class='Function'>/</span><span class='Modifier'>⁼</span></code>. In fact, inverse Indices called on the index argument gives the length of each group:</p>
+<p>Group is closely related to the <a href="replicate.html#inverse">inverse of Indices</a>, <code><span class='Function'>/</span><span class='Modifier'>⁼</span></code>. In fact, inverse Indices called on the index argument gives the length of each group:</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4omgwqjiipQgMuKAvzPigL8x4oC/Mgov4oG84oinIDLigL8z4oC/MeKAvzI=">↗️</a><pre> <span class='Function'>≠</span><span class='Modifier'>¨</span><span class='Function'>⊔</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>2</span>
⟨ 0 1 2 1 ⟩
<span class='Function'>/</span><span class='Modifier'>⁼</span><span class='Function'>∧</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>2</span>
⟨ 0 1 2 1 ⟩
</pre>
-<p>A related fact is that calling Indices on the result of Group sorts all the indices passed to Group (removing any ¯1s). This is a kind of counting sort.</p>
+<p>A related fact is that calling Indices on the result lengths of Group sorts all the indices passed to Group (removing any ¯1s). This is a kind of counting sort.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=L+KJoMKo4oqUIDLigL8z4oC/MeKAv8KvMeKAvzI=">↗️</a><pre> <span class='Function'>/≠</span><span class='Modifier'>¨</span><span class='Function'>⊔</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>¯1</span><span class='Ligature'>‿</span><span class='Number'>2</span>
⟨ 1 2 2 3 ⟩
</pre>
-<p>Called dyadically, Group sorts the right argument according to the left and adds some extra structure. If this structure is removed with Join, Group can be thought of as a kind of sorting.</p>
+<p>Called dyadically, Group sorts the right argument according to the left and adds some extra structure. If this structure is removed with <a href="join.html#join">Join</a>, Group can be thought of as a kind of sorting.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oi+IDLigL8z4oC/MeKAv8KvMeKAvzIg4oqUICJhYmNkZSIKMuKAvzPigL8x4oC/wq8x4oC/MiB7RuKGkCgw4omk8J2VqCniirgvIOKLhCDwnZWo4o2L4oq44oqP4peLRvCdlal9ICJhYmNkZSI=">↗️</a><pre> <span class='Function'>∾</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>¯1</span><span class='Ligature'>‿</span><span class='Number'>2</span> <span class='Function'>⊔</span> <span class='String'>&quot;abcde&quot;</span>
"caeb"
<span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>¯1</span><span class='Ligature'>‿</span><span class='Number'>2</span> <span class='Brace'>{</span><span class='Function'>F</span><span class='Gets'>←</span><span class='Paren'>(</span><span class='Number'>0</span><span class='Function'>≤</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>/</span> <span class='Separator'>⋄</span> <span class='Value'>𝕨</span><span class='Function'>⍋</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span><span class='Modifier2'>○</span><span class='Function'>F</span><span class='Value'>𝕩</span><span class='Brace'>}</span> <span class='String'>&quot;abcde&quot;</span>
"caeb"
</pre>
-<p>Group can even be implemented with the same techniques as a bucket sort, which can be branchless and fast.</p>
+<p>Group can even be implemented with the same <a href="../implementation/primitive/sort.html#counting-and-bucket-sort">techniques</a> as a bucket sort, making it branchless and fast.</p>
<h2 id="applications">Applications</h2>
-<p>The obvious application of Group is to group some values according to a known or computed property. If this property isn't an integer, it can be turned into one using Classify (monadic <code><span class='Function'>⊐</span></code>, identical to <code><span class='Function'>⍷</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span></code>). Classify numbers the unique values in its argument by first occurrence.</p>
+<p>The obvious application of Group is to group some values according to a known or computed property. If this property isn't a natural number, it can be turned into one using <a href="selfcmp.html#classify">Classify</a> (<code><span class='Function'>⊐</span></code>), which numbers the unique values in its argument by first occurrence.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=bG4g4oaQICJQaGVscHMi4oC/IkxhdHluaW5hIuKAvyJCasO4cmdlbiLigL8iQW5kcmlhbm92IuKAvyJCasO4cm5kYWxlbiIKY28g4oaQICJVUyIgICAg4oC/IlNVIiAgICAgIOKAvyJOTyIgICAgIOKAvyJTVSIgICAgICAg4oC/Ik5PIgriiY3LmCBjbyDiipDiirjiipQgbG4=">↗️</a><pre> <span class='Value'>ln</span> <span class='Gets'>←</span> <span class='String'>&quot;Phelps&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;Latynina&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;Bjørgen&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;Andrianov&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;Bjørndalen&quot;</span>
<span class='Value'>co</span> <span class='Gets'>←</span> <span class='String'>&quot;US&quot;</span> <span class='Ligature'>‿</span><span class='String'>&quot;SU&quot;</span> <span class='Ligature'>‿</span><span class='String'>&quot;NO&quot;</span> <span class='Ligature'>‿</span><span class='String'>&quot;SU&quot;</span> <span class='Ligature'>‿</span><span class='String'>&quot;NO&quot;</span>
<span class='Function'>≍</span><span class='Modifier'>˘</span> <span class='Value'>co</span> <span class='Function'>⊐</span><span class='Modifier2'>⊸</span><span class='Function'>⊔</span> <span class='Value'>ln</span>
@@ -148,7 +148,7 @@
⟨ "Bjørgen" "Bjørndalen" ⟩
</pre>
-<p>If we would like a particular index to key correspondence, we can use a fixed left argument to Index Of.</p>
+<p>If we would like a particular index to key correspondence, we can use a fixed left argument to <a href="search.html#index-of">Index Of</a>.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=Y291bnRyaWVzIOKGkCAiSVQi4oC/IkpQIuKAvyJOTyLigL8iU1Ui4oC/IlVTIgpjb3VudHJpZXMg4omNy5ggY28gY291bnRyaWVz4oq44oqQ4oq44oqUIGxu">↗️</a><pre> <span class='Value'>countries</span> <span class='Gets'>←</span> <span class='String'>&quot;IT&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;JP&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;NO&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;SU&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;US&quot;</span>
<span class='Value'>countries</span> <span class='Function'>≍</span><span class='Modifier'>˘</span> <span class='Value'>co</span> <span class='Value'>countries</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span><span class='Modifier2'>⊸</span><span class='Function'>⊔</span> <span class='Value'>ln</span>
┌─
@@ -172,7 +172,7 @@
</pre>
<h3 id="partitioning">Partitioning</h3>
-<p>In examples we have been using a list of strings stranded together. Often it's more convenient to write the string with spaces, and split it up as part of the code. In this case, the index corresponding to each word (that is, each letter in the word) is the number of spaces before it. We can get this number of spaces from a prefix sum on the boolean list which is 1 at each space.</p>
+<p>In examples we have been using a list of strings stranded together. Often it's more convenient to write the string with spaces, and split it up as part of the code. In this case, the index corresponding to each word (that is, each letter in the word) is the number of spaces before it. We can get this number of spaces from a Plus-<a href="scan.html">Scan</a> on the boolean list which is 1 at each space.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=JyAnKCtg4oiYPeKKlOKKoikiQlFOIHVzZXMgbm90YXRpb24gYXMgYSB0b29sIG9mIHRob3VnaHQi">↗️</a><pre> <span class='String'>' '</span><span class='Paren'>(</span><span class='Function'>+</span><span class='Modifier'>`</span><span class='Modifier2'>∘</span><span class='Function'>=⊔⊢</span><span class='Paren'>)</span><span class='String'>&quot;BQN uses notation as a tool of thought&quot;</span>
⟨ "BQN" " uses" " notation" " as" " a" " tool" " of" " thought" ⟩
</pre>
@@ -185,7 +185,7 @@
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=JyAnKCjiiqIty5zCrMOXK2Ap4oiYPeKKlOKKoikiICBzdHJpbmcgd2l0aCAgc3BhY2VzICAgIg==">↗️</a><pre> <span class='String'>' '</span><span class='Paren'>((</span><span class='Function'>⊢-</span><span class='Modifier'>˜</span><span class='Function'>¬×+</span><span class='Modifier'>`</span><span class='Paren'>)</span><span class='Modifier2'>∘</span><span class='Function'>=⊔⊢</span><span class='Paren'>)</span><span class='String'>&quot; string with spaces &quot;</span>
⟨ ⟨⟩ ⟨⟩ "string" "with" ⟨⟩ "spaces" ⟩
</pre>
-<p>Trailing spaces are ignored because Group with equal-length arguments never produces trailing empty groups—to intentionally include them you'd replace <code><span class='Function'>=</span></code> with <code><span class='Paren'>(</span><span class='Function'>=∾</span><span class='Number'>0</span><span class='Modifier'>˙</span><span class='Paren'>)</span></code>. But in string processing we probably want to avoid empty words anywhere. To make this happen, we should increase the word index only once per group of spaces. We can do this by taking the prefix sum of a list that is 1 only for a space with no space before it. To make such a list, we can use the <a href="shift.html">Shift Before</a> function, giving a list of previous elements. To treat the first element as if it's before a space (so that leading spaces have no effect rather than creating an initial empty group), we shift in a 1.</p>
+<p>Trailing spaces are ignored because Group with equal-length arguments never produces trailing empty groups—to intentionally include them you'd replace <code><span class='Function'>=</span></code> with <code><span class='Paren'>(</span><span class='Function'>=∾</span><span class='Number'>0</span><span class='Modifier'>˙</span><span class='Paren'>)</span></code>. But in string processing we probably want to avoid empty words anywhere. To make this happen, we should increase the word index only once per group of spaces. We can do this by applying Plus Scan to a list that is 1 only for a space with no space before it. This list is produced using <a href="shift.html">Shift Before</a> to get a list of previous elements. To treat the first element as though it's before a space (so that leading spaces have no effect rather than creating an initial empty group), we shift in a 1.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=KOKKouKJjTHiirjCuzziiqIpICcgJz0iICBzdHJpbmcgd2l0aCAgc3BhY2VzICAgIiAgIyBBbGwsIHRoZW4gZmlsdGVyZWQsIHNwYWNlcwriiY3in5wo4oqiLcucwqzDl8K3K2Ax4oq4wrs84oqiKScgJz0iICBzdHJpbmcgd2l0aCAgc3BhY2VzICAgIiAgIyBNb3JlIHByb2Nlc3NpbmcKJyAnKCjiiqIty5zCrMOXwrcrYDHiirjCuzziiqIp4oiYPeKKlOKKoikiICBzdHJpbmcgd2l0aCAgc3BhY2VzICAgIiAgIyBGaW5hbCByZXN1bHQKCicgJygowqwty5ziiqLDl8K3K2DCu+KKuD4p4oiY4omg4oqU4oqiKSIgIHN0cmluZyB3aXRoICBzcGFjZXMgICAiICAjIFNsaWdodGx5IHNob3J0ZXI=">↗️</a><pre> <span class='Paren'>(</span><span class='Function'>⊢≍</span><span class='Number'>1</span><span class='Modifier2'>⊸</span><span class='Function'>»&lt;⊢</span><span class='Paren'>)</span> <span class='String'>' '</span><span class='Function'>=</span><span class='String'>&quot; string with spaces &quot;</span> <span class='Comment'># All, then filtered, spaces
</span>┌─
╵ 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1