aboutsummaryrefslogtreecommitdiff
path: root/docs/doc/scan.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/scan.html
parente3366f9e18a8791c43110e080b9ea45cfceefed8 (diff)
Finish links and editing documentation pass
Diffstat (limited to 'docs/doc/scan.html')
-rw-r--r--docs/doc/scan.html10
1 files changed, 5 insertions, 5 deletions
diff --git a/docs/doc/scan.html b/docs/doc/scan.html
index 1f572239..cc806de6 100644
--- a/docs/doc/scan.html
+++ b/docs/doc/scan.html
@@ -59,8 +59,8 @@
</svg>
<p>The 1-modifier Scan (<code><span class='Modifier'>`</span></code>) moves along the first axis of the array <code><span class='Value'>𝕩</span></code>, building up an array of results by applying <code><span class='Function'>𝔽</span></code> repeatedly beginning with <code><span class='Value'>𝕨</span></code> or <code><span class='Function'>⊏</span><span class='Value'>𝕩</span></code>. It's related to the fold modifiers, and most closely resembles the <a href="fold.html#apl2-reduction">APL2-style reduction</a> <code><span class='Modifier'>¨˝</span></code>, but it traverses the array in forward rather than reverse index order, and includes all intermediate results of <code><span class='Function'>𝔽</span></code> in its output instead of just the final one.</p>
-<p>BQN's Scan is ordered differently from Scan in APL. Both include one result for each non-empty prefix of <code><span class='Value'>𝕩</span></code>. In BQN this is a left-to-right fold, so that each new result requires one application of <code><span class='Function'>𝔽</span></code>. APL uses a right-to-left ordering, which matches with reduction, but requires starting over at the end for each new prefix, except in special cases. If needed, this definition can be obtained with a fold on each <a href="prefixes.html">prefix</a> except the first (which is empty). In the particular case of <code><span class='Function'>-</span><span class='Value'>⍀</span></code>, that nested solution isn't needed: negate odd-indexed elements and then apply <code><span class='Function'>+</span><span class='Modifier'>`</span></code>.</p>
-<p>Scan also differs from Fold or Insert in that it never depends on <code><span class='Function'>𝔽</span></code>'s identity element, because scanning over an empty array simply returns that array.</p>
+<p>BQN's Scan is ordered differently from Scan in APL. Both include one result for each non-empty prefix of <code><span class='Value'>𝕩</span></code>. In BQN this is a left-to-right fold, so that each new result requires one application of <code><span class='Function'>𝔽</span></code>. APL uses right-to-left folds, which matches with reduction, but requires starting over at the end for each new prefix, except in special cases. If needed, this definition can be obtained with a fold on each <a href="prefixes.html">prefix</a> except the first (which is empty). In the particular case of <code><span class='Function'>-</span><span class='Value'>⍀</span></code>, that nested solution isn't needed: negate odd-indexed elements and then apply <code><span class='Function'>+</span><span class='Modifier'>`</span></code>.</p>
+<p>Scan also differs from Fold or Insert in that it never depends on <code><span class='Function'>𝔽</span></code>'s <a href="fold.html#identity-values">identity value</a>, because scanning over an empty array simply returns that array.</p>
<h2 id="lists">Lists</h2>
<p>The best-known use of Scan is the <a href="https://en.wikipedia.org/wiki/Prefix_sum">prefix sum</a> of a list, in which each element of the result is the sum of that element and all the ones before it. With a <a href="shift.html">shift</a> this can be modified to sum the previous elements only.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=K2AgMuKAvzTigL8z4oC/MQoKK2DCuzLigL804oC/M+KAvzEgICMgRXhjbHVzaXZlIHByZWZpeCBzdW0=">↗️</a><pre> <span class='Function'>+</span><span class='Modifier'>`</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'>1</span>
@@ -69,7 +69,7 @@
<span class='Function'>+</span><span class='Modifier'>`</span><span class='Function'>»</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'>1</span> <span class='Comment'># Exclusive prefix sum
</span>⟨ 0 2 6 9 ⟩
</pre>
-<p>The pattern is generalized to any function <code><span class='Function'>𝔽</span></code>. With an operand of <code><span class='Function'>×</span></code>, it can find the first <em>n</em> factorials. With <code><span class='Function'>⌈</span></code>, it returns the largest element so far.</p>
+<p>The pattern is generalized to any function <code><span class='Function'>𝔽</span></code>. With an operand of <code><span class='Function'>×</span></code>, it can find the first <em>n</em> factorials. With <a href="arithmetic.html#additional-arithmetic">Maximum</a> (<code><span class='Function'>⌈</span></code>), it returns the largest element so far.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=w5dgIDEr4oaVNgoK4oyIYCDCrzHigL/CrzLigL8w4oC/NOKAvzLigL8x4oC/NeKAv8KvMg==">↗️</a><pre> <span class='Function'>×</span><span class='Modifier'>`</span> <span class='Number'>1</span><span class='Function'>+↕</span><span class='Number'>6</span>
⟨ 1 2 6 24 120 720 ⟩
@@ -94,7 +94,7 @@
<span class='Value'>c</span>
9
</pre>
-<p>Some other useful scans apply to boolean lists. The function <code><span class='Function'>∨</span><span class='Modifier'>`</span></code> tests whether this or any previous element is 1, so that the result starts at 0 but permanently switches to 1 as soon as the first 1 is found. Similarly, <code><span class='Function'>∧</span><span class='Modifier'>`</span></code> turns all instances of 1 after the first 0 to 0.</p>
+<p>Some other useful scans apply to boolean lists. The function <code><span class='Function'>∨</span><span class='Modifier'>`</span></code> (with <a href="logic.html">Or</a>) tests whether this or any previous element is 1, so that the result starts at 0 but permanently switches to 1 as soon as the first 1 is found. Similarly, <code><span class='Function'>∧</span><span class='Modifier'>`</span></code> turns all instances of 1 after the first 0 to 0.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oioYCAw4oC/MOKAvzHigL8w4oC/MOKAvzHigL8w4oC/MQoK4oinYCAx4oC/MeKAvzHigL8w4oC/MOKAvzHigL8w4oC/MQ==">↗️</a><pre> <span class='Function'>∨</span><span class='Modifier'>`</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'>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'>0</span><span class='Ligature'>‿</span><span class='Number'>1</span>
⟨ 0 0 1 1 1 1 1 1 ⟩
@@ -109,7 +109,7 @@
"ab\rs\\"
</pre>
<h2 id="reverse-scan">Reverse scan</h2>
-<p>We've discussed how the scan moves forward along <code><span class='Value'>𝕩</span></code>, so that each time <code><span class='Function'>𝔽</span></code> takes an old result as <code><span class='Value'>𝕨</span></code> and a new value as <code><span class='Value'>𝕩</span></code>. This means that results correspond to prefixes and go left to right on each one. Since the most important scans have associative, commutative operands, the left-to-right ordering often doesn't make a difference. But sometimes a suffix rather than prefix scan is wanted. For these cases, Scan Under <a href="reverse.html">Reverse</a> (<code><span class='Modifier'>`</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span></code>) does the trick.</p>
+<p>We've discussed how the scan moves forward along <code><span class='Value'>𝕩</span></code>, so that each time <code><span class='Function'>𝔽</span></code> takes an old result as <code><span class='Value'>𝕨</span></code> and a new value as <code><span class='Value'>𝕩</span></code>. This means that results correspond to <a href="prefixes.html">prefixes</a> and go left to right on each one. Since the most important scans have associative, commutative operands, the left-to-right ordering often doesn't make a difference. But sometimes a suffix rather than prefix scan is wanted. For these cases, Scan Under <a href="reverse.html">Reverse</a> (<code><span class='Modifier'>`</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span></code>) does the trick.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oioYCAgIDDigL8w4oC/MeKAvzDigL8w4oC/MeKAvzAKCuKIqGDijL7ijL0gMOKAvzDigL8x4oC/MOKAvzDigL8x4oC/MA==">↗️</a><pre> <span class='Function'>∨</span><span class='Modifier'>`</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'>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'>0</span>
⟨ 0 0 1 1 1 1 1 ⟩