aboutsummaryrefslogtreecommitdiff
path: root/docs/doc/shift.html
diff options
context:
space:
mode:
authorMarshall Lochbaum <mwlochbaum@gmail.com>2021-07-16 18:23:52 -0400
committerMarshall Lochbaum <mwlochbaum@gmail.com>2021-07-16 18:24:01 -0400
commit2010e8b2897a5741e211980c9f8ec9177299c939 (patch)
tree4b3476744be928724da2fd5d83b0bf2e9a8ba502 /docs/doc/shift.html
parente3366f9e18a8791c43110e080b9ea45cfceefed8 (diff)
Finish links and editing documentation pass
Diffstat (limited to 'docs/doc/shift.html')
-rw-r--r--docs/doc/shift.html34
1 files changed, 20 insertions, 14 deletions
diff --git a/docs/doc/shift.html b/docs/doc/shift.html
index 0d162721..c4b142c6 100644
--- a/docs/doc/shift.html
+++ b/docs/doc/shift.html
@@ -5,8 +5,8 @@
</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="shift-functions">Shift functions</h1>
-<p>The shift functions <code><span class='Function'>«</span></code> and <code><span class='Function'>»</span></code> are two new primitives added to BQN based on a pattern used heavily in the compiler and a reasonable amount everywhere else. Shifts resemble but are more general than the bit-based shift operations used in low-level languages. They replace the APL pattern of a 2-wise reduction after appending or prepending an element (APL's <code><span class='Number'>2</span><span class='Function'>≠/</span><span class='Number'>0</span><span class='Separator'>,</span><span class='Value'>v</span></code> translates to <code><span class='Function'>»</span><span class='Modifier2'>⊸</span><span class='Function'>≠</span><span class='Value'>v</span></code>), one of the more common uses of 2-wise reduction.</p>
-<p>The result of a shift function always has the same shape as its right argument. The function adds major cells to the beginning (<code><span class='Function'>»</span></code>) or end (<code><span class='Function'>«</span></code>) of <code><span class='Value'>𝕩</span></code>, moving the cells already in <code><span class='Value'>𝕩</span></code> to accomodate them. Some cells on the opposite side from those added will &quot;fall off&quot; and not be included in the result.</p>
+<p>The shift functions <code><span class='Function'>«</span></code> and <code><span class='Function'>»</span></code> add major cells to one side an array, displacing cells on the opposite side and moving those in between. Shifts resemble but are more general than the bit-based shift operations used in low-level languages. They replace the APL pattern of a 2-wise reduction after appending or prepending an element (APL's <code><span class='Number'>2</span><span class='Function'>≠/</span><span class='Number'>0</span><span class='Separator'>,</span><span class='Value'>v</span></code> translates to <code><span class='Function'>»</span><span class='Modifier2'>⊸</span><span class='Function'>≠</span><span class='Value'>v</span></code>), one of the more common uses of 2-wise reduction.</p>
+<p>The result of a shift function always has the same shape as <code><span class='Value'>𝕩</span></code>. The function adds major cells to the beginning (<code><span class='Function'>»</span></code>) or end (<code><span class='Function'>«</span></code>) of <code><span class='Value'>𝕩</span></code>, moving the cells already in <code><span class='Value'>𝕩</span></code> to accomodate them. Some cells on the opposite side from those added will &quot;fall off&quot; and not be included in the result.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=MOKAvzAgwrsgM+KAvzLigL8xICAgICAgICAgICAgICMgU2hpZnQgQmVmb3JlCiJlbmQiIMKrICJhZGQgdG8gdGhlICIgICAjIFNoaWZ0IEFmdGVy">↗️</a><pre> <span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0</span> <span class='Function'>»</span> <span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>1</span> <span class='Comment'># Shift Before
</span>⟨ 0 0 3 ⟩
<span class='String'>&quot;end&quot;</span> <span class='Function'>«</span> <span class='String'>&quot;add to the &quot;</span> <span class='Comment'># Shift After
@@ -20,7 +20,7 @@
</pre>
<p>If <code><span class='Value'>𝕨</span></code> is longer than <code><span class='Value'>𝕩</span></code>, some cells from <code><span class='Value'>𝕨</span></code> will be discarded, as well as all of <code><span class='Value'>𝕩</span></code>. In this case <code><span class='Value'>𝕨</span><span class='Function'>»</span><span class='Value'>𝕩</span></code> is <code><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕨</span></code> and <code><span class='Value'>𝕨</span><span class='Function'>«</span><span class='Value'>𝕩</span></code> is <code><span class='Paren'>(</span><span class='Function'>-≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕨</span></code>. For similar reasons, nudging an array of length 0 returns it unchanged.</p>
<h2 id="sequence-processing-with-shifts">Sequence processing with shifts</h2>
-<p>When working with a sequence of data such as text, daily measurements, or audio data, shift functions are generally the best way to handle the concept of &quot;next&quot; or &quot;previous&quot; in the data. In the following example <code><span class='Value'>s</span></code> is shown alongside the shifted-right data <code><span class='Function'>»</span><span class='Value'>s</span></code>, and each element is compared to the previous with <code><span class='Function'>-</span><span class='Modifier2'>⟜</span><span class='Function'>»</span></code>, which we see is the inverse of <code><span class='Function'>+</span><span class='Modifier'>`</span></code>.</p>
+<p>When working with a sequence of data such as text, daily measurements, or audio data, shift functions are generally the best way to handle the concept of &quot;next&quot; or &quot;previous&quot;. In the following example <code><span class='Value'>s</span></code> is shown alongside the shifted-right data <code><span class='Function'>»</span><span class='Value'>s</span></code>, and each element is compared to the previous with <code><span class='Function'>-</span><span class='Modifier2'>⟜</span><span class='Function'>»</span></code>, which we see is the inverse of Plus <a href="scan.html">Scan</a> <code><span class='Function'>+</span><span class='Modifier'>`</span></code>.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=cyDihpAgMeKAvzLigL8y4oC/NOKAvzPigL814oC/NgpzIOKJjSDCu3MKLeKfnMK7IHMKCitgIC3in5zCuyBz">↗️</a><pre> <span class='Value'>s</span> <span class='Gets'>←</span> <span class='Number'>1</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'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>6</span>
<span class='Value'>s</span> <span class='Function'>≍</span> <span class='Function'>»</span><span class='Value'>s</span>
┌─
@@ -34,8 +34,9 @@
⟨ 1 2 2 4 3 5 6 ⟩
</pre>
<p>In this way <code><span class='Function'>»</span></code> refers to a sequence containing the previous element at each position. By default the array's fill is used for the element before the first, and a right argument can be given to provide a different one.</p>
-<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oieIMK7IHMK4oqP4oq4wrsgcw==">↗️</a><pre> <span class='Number'>∞</span> <span class='Function'>»</span> <span class='Value'>s</span>
+<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oieIMK7IHMKCuKKj+KKuMK7IHM=">↗️</a><pre> <span class='Number'>∞</span> <span class='Function'>»</span> <span class='Value'>s</span>
⟨ ∞ 1 2 2 4 3 5 ⟩
+
<span class='Function'>⊏</span><span class='Modifier2'>⊸</span><span class='Function'>»</span> <span class='Value'>s</span>
⟨ 1 1 2 2 4 3 5 ⟩
</pre>
@@ -76,17 +77,19 @@
</span>⟨ 1 1 1 1 0 0 1 1 ⟩
</pre>
<h2 id="other-examples">Other examples</h2>
-<p>In Take (<code><span class='Function'>↑</span></code>), there's no way to specify the fill element when the result is longer than the argument. To take along the first axis with a specified, constant fill value, you can use Shift Before instead, where the right argument is an array of fills with the desired final shape.</p>
+<p>In <a href="take.html">Take</a> (<code><span class='Function'>↑</span></code>), there's no way to specify the fill element when the result is longer than the argument. To take along the first axis with a specified, constant fill value, you can use Shift Before instead, where the right argument is an array of fills with the desired final shape.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ImFiYyIgwrsgNeKliidGJw==">↗️</a><pre> <span class='String'>&quot;abc&quot;</span> <span class='Function'>»</span> <span class='Number'>5</span><span class='Function'>⥊</span><span class='String'>'F'</span>
"abcFF"
</pre>
-<p>When using Scan (<code><span class='Modifier'>`</span></code>), the result at a particular index is obtained from values up to and including the one at that index. But it's common to want to use the values up to but not including that one instead. This can be done either by joining or shifting in that value before scanning. The difference is that with Join the result is longer than the argument. Either form might be wanted depending on how it will be used.</p>
-<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=K2AgMeKAvzHigL8x4oC/MQoyICtg4oiY4oi+IDHigL8x4oC/MeKAvzEKMiArYOKImMK7IDHigL8x4oC/MeKAvzE=">↗️</a><pre> <span class='Function'>+</span><span class='Modifier'>`</span> <span class='Number'>1</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'>1</span>
-⟨ 1 2 3 4 ⟩
- <span class='Number'>2</span> <span class='Function'>+</span><span class='Modifier'>`</span><span class='Modifier2'>∘</span><span class='Function'>∾</span> <span class='Number'>1</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'>1</span>
-⟨ 2 3 4 5 6 ⟩
- <span class='Number'>2</span> <span class='Function'>+</span><span class='Modifier'>`</span><span class='Modifier2'>∘</span><span class='Function'>»</span> <span class='Number'>1</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'>1</span>
-⟨ 2 3 4 5 ⟩
+<p>When using <a href="scan.html">Scan</a> (<code><span class='Modifier'>`</span></code>), the result at a particular index is obtained from values up to and including the one at that index. But it's common to want to use the values up to but not including that one instead. This can be done either by <a href="join.html#join-to">joining</a> or shifting in that value before scanning. The difference is that with Join the result is longer than the argument. Either form might be wanted depending on how it will be used.</p>
+<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=MiArYCAx4oC/MOKAvzHigL8wICAgICMgSW5pdGlhbCB2YWx1ZSBub3QgcmV0YWluZWQKCjIgK2DiiJjiiL4gMeKAvzDigL8x4oC/MCAgIyBBbGwgdmFsdWVzCgoyICtg4oiYwrsgMeKAvzDigL8x4oC/MCAgIyBGaW5hbCB2YWx1ZSBub3QgY3JlYXRlZA==">↗️</a><pre> <span class='Number'>2</span> <span class='Function'>+</span><span class='Modifier'>`</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='Comment'># Initial value not retained
+</span>⟨ 3 3 4 4 ⟩
+
+ <span class='Number'>2</span> <span class='Function'>+</span><span class='Modifier'>`</span><span class='Modifier2'>∘</span><span class='Function'>∾</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='Comment'># All values
+</span>⟨ 2 3 3 4 4 ⟩
+
+ <span class='Number'>2</span> <span class='Function'>+</span><span class='Modifier'>`</span><span class='Modifier2'>∘</span><span class='Function'>»</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='Comment'># Final value not created
+</span>⟨ 2 3 3 4 ⟩
</pre>
<p>The <em>strides</em> of an array are the distances between one element and the next along any given axis. It's the product of all axis lengths below that axis, since these are all the axes that have to be &quot;skipped&quot; to jump along the axis. The strides of an array <code><span class='Value'>𝕩</span></code> are <code><span class='Paren'>(</span><span class='Function'>×</span><span class='Modifier'>`</span><span class='Number'>1</span><span class='Function'>»⊢</span><span class='Paren'>)</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span><span class='Modifier2'>∘</span><span class='Function'>≢</span><span class='Value'>𝕩</span></code>.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=KMOXYDHCu+KKoinijL7ijL0gNeKAvzLigL804oC/Mw==">↗️</a><pre> <span class='Paren'>(</span><span class='Function'>×</span><span class='Modifier'>`</span><span class='Number'>1</span><span class='Function'>»⊢</span><span class='Paren'>)</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span> <span class='Number'>5</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'>3</span>
@@ -94,13 +97,14 @@
</pre>
<h2 id="higher-rank">Higher rank</h2>
<p>Shifting always works on the first axis of <code><span class='Value'>𝕩</span></code> (which must have rank 1 or more), and shifts in major cells. A left argument can have rank equal to <code><span class='Value'>𝕩</span></code>, or one less than it, in which case it becomes a single cell of the result. With no left argument, a cell of fills <code><span class='Number'>1</span><span class='Function'>↑</span><span class='Number'>0</span><span class='Function'>↑</span><span class='Value'>𝕩</span></code> is nudged in.</p>
-<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGEg4oaQIOKliuKfnCjihpXDl8K0KSA04oC/MwrCuyBhICAgICAgICAgICAgICAgICMgTnVkZ2UgYWRkcyBhIGNlbGwgb2YgZmlsbHMKIm9uZSIgwqsgYSAgICAgICAgICAjIFNoaWZ0IGluIGEgY2VsbAooInR3byLiiY0iY2VsIikgwqsgYSAgIyBTaGlmdCBpbiBtdWx0aXBsZSBjZWxscw==">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>a</span> <span class='Gets'>←</span> <span class='Function'>⥊</span><span class='Modifier2'>⟜</span><span class='Paren'>(</span><span class='Function'>↕×</span><span class='Modifier'>´</span><span class='Paren'>)</span> <span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span>
+<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGEg4oaQIOKliuKfnCjihpXDl8K0KSA04oC/MwoKwrsgYSAgICAgICAgICAgICAgICAjIE51ZGdlIGFkZHMgYSBjZWxsIG9mIGZpbGxzCgoib25lIiDCqyBhICAgICAgICAgICMgU2hpZnQgaW4gYSBjZWxsCgooInR3byLiiY0iY2VsIikgwqsgYSAgIyBTaGlmdCBpbiBtdWx0aXBsZSBjZWxscw==">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>a</span> <span class='Gets'>←</span> <span class='Function'>⥊</span><span class='Modifier2'>⟜</span><span class='Paren'>(</span><span class='Function'>↕×</span><span class='Modifier'>´</span><span class='Paren'>)</span> <span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span>
┌─
╵ 0 1 2
3 4 5
6 7 8
9 10 11
+
<span class='Function'>»</span> <span class='Value'>a</span> <span class='Comment'># Nudge adds a cell of fills
</span>┌─
╵ 0 0 0
@@ -108,6 +112,7 @@
3 4 5
6 7 8
+
<span class='String'>&quot;one&quot;</span> <span class='Function'>«</span> <span class='Value'>a</span> <span class='Comment'># Shift in a cell
</span>┌─
╵ 3 4 5
@@ -115,6 +120,7 @@
9 10 11
'o' 'n' 'e'
+
<span class='Paren'>(</span><span class='String'>&quot;two&quot;</span><span class='Function'>≍</span><span class='String'>&quot;cel&quot;</span><span class='Paren'>)</span> <span class='Function'>«</span> <span class='Value'>a</span> <span class='Comment'># Shift in multiple cells
</span>┌─
╵ 6 7 8
@@ -125,5 +131,5 @@
</pre>
<h2 id="definition">Definition</h2>
<p>In any instance of <code><span class='Function'>»</span></code> or <code><span class='Function'>«</span></code>, <code><span class='Value'>𝕩</span></code> must have rank at least 1.</p>
-<p>For a dyadic shift function, <code><span class='Value'>𝕨</span></code> must be Join-compatible with <code><span class='Value'>𝕩</span></code> (that is, <code><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Value'>𝕩</span></code> completes without error) and cannot have greater rank than <code><span class='Value'>𝕩</span></code>. Then Shift Before (<code><span class='Function'>»</span></code>) is <code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> and Shift After (<code><span class='Function'>«</span></code>) is <code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>-≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕩</span><span class='Function'>∾</span><span class='Value'>𝕨</span><span class='Brace'>}</span></code></p>
+<p>For a dyadic shift function, <code><span class='Value'>𝕨</span></code> must be <a href="join.html#join-to">Join</a>-compatible with <code><span class='Value'>𝕩</span></code> (that is, <code><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Value'>𝕩</span></code> completes without error) and cannot have greater rank than <code><span class='Value'>𝕩</span></code>. Then Shift Before (<code><span class='Function'>»</span></code>) is <code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> and Shift After (<code><span class='Function'>«</span></code>) is <code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>-≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕩</span><span class='Function'>∾</span><span class='Value'>𝕨</span><span class='Brace'>}</span></code></p>
<p>When called monadically, the default argument is a cell of fills <code><span class='Number'>1</span><span class='Function'>↑</span><span class='Number'>0</span><span class='Function'>↑</span><span class='Value'>𝕩</span></code>. That is, Nudge (<code><span class='Function'>»</span></code>) is <code><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>↑</span><span class='Number'>0</span><span class='Function'>↑⊢</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>»</span></code> and Nudge Back (<code><span class='Function'>«</span></code>) is <code><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>↑</span><span class='Number'>0</span><span class='Function'>↑⊢</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>«</span></code>. This default argument always satisfies the compatibility requirement above and so the only conditions for nudge are that <code><span class='Value'>𝕩</span></code> has rank at least 1 and has a fill element.</p>