diff options
Diffstat (limited to 'docs/doc/scan.html')
| -rw-r--r-- | docs/doc/scan.html | 10 |
1 files changed, 5 insertions, 5 deletions
diff --git a/docs/doc/scan.html b/docs/doc/scan.html index 4b168b89..9d881cba 100644 --- a/docs/doc/scan.html +++ b/docs/doc/scan.html @@ -4,7 +4,7 @@ <title>BQN: Scan</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="scan">Scan</h1> +<h1 id="scan"><a class="header" href="#scan">Scan</a></h1> <svg viewBox='-184.8 -12.6 588 285.6'> <g fill='currentColor' stroke-linecap='round' text-anchor='middle' font-family='BQN,monospace'> <rect class='code' stroke-width='1.5' rx='12' x='-128.8' y='0' width='476' height='260.4'/> @@ -61,7 +61,7 @@ <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 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> +<h2 id="lists"><a class="header" href="#lists">Lists</a></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> ⟨ 2 6 9 10 ⟩ @@ -108,7 +108,7 @@ <span class='Brace'>{</span><span class='Function'>¬<</span><span class='Modifier'>`</span><span class='String'>'\'</span><span class='Function'>=</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Modifier2'>⊸</span><span class='Function'>/</span> <span class='String'>"ab\\\rs\\\\"</span> "ab\rs\\" </pre> -<h2 id="reverse-scan">Reverse scan</h2> +<h2 id="reverse-scan"><a class="header" href="#reverse-scan">Reverse scan</a></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 <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 ⟩ @@ -124,7 +124,7 @@ <a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=eyIoIuKIvvCdlajiiL4iKfCdlL0i4oi+8J2VqX3LnGDijL7ijL0gImEi4oC/ImIi4oC/ImMi4oC/ImQi">↗️</a><pre> <span class='Brace'>{</span><span class='String'>"("</span><span class='Function'>∾</span><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='String'>")𝔽"</span><span class='Function'>∾</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Modifier'>˜`</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span> <span class='String'>"a"</span><span class='Ligature'>‿</span><span class='String'>"b"</span><span class='Ligature'>‿</span><span class='String'>"c"</span><span class='Ligature'>‿</span><span class='String'>"d"</span> ⟨ "(a)𝔽(b)𝔽(c)𝔽d" "(b)𝔽(c)𝔽d" "(c)𝔽d" "d" ⟩ </pre> -<h2 id="higher-ranks">Higher ranks</h2> +<h2 id="higher-ranks"><a class="header" href="#higher-ranks">Higher ranks</a></h2> <p>Scan moves along the <a href="leading.html">leading axis</a> of <code><span class='Value'>𝕩</span></code>: vertically, for a table. To apply a scan to later axes, use <code><span class='Modifier'>˘</span></code> or <code><span class='Modifier2'>⎉</span></code>. Since a scan returns an array with the same shape as its argument, this can't cause an error from differing result cell shapes, unlike Fold or Insert.</p> <a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGEg4oaQIMKvMuKAvzAuMjXigL8nYSfigL/iiJ4g4oi+IDPigL804qWKwq8x4oC/MOKAvzEKCitgIGE=">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>a</span> <span class='Gets'>←</span> <span class='Number'>¯2</span><span class='Ligature'>‿</span><span class='Number'>0.25</span><span class='Ligature'>‿</span><span class='String'>'a'</span><span class='Ligature'>‿</span><span class='Number'>∞</span> <span class='Function'>∾</span> <span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</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> ┌─ @@ -152,6 +152,6 @@ ┘ </pre> <p>Results are produced in index order. This means that instead of moving along each column in turn, a scan produces the first result cell one element at a time, then the next, and so on. Something like a breadth-first as opposed to depth-first ordering.</p> -<h2 id="definition">Definition</h2> +<h2 id="definition"><a class="header" href="#definition">Definition</a></h2> <p>Scan admits a simple recursive definition. <code><span class='Value'>𝕩</span></code> is an array of rank one or more and <code><span class='Value'>𝕨</span></code>, if given, is an atom or array with shape <code><span class='Number'>1</span><span class='Function'>↓≢</span><span class='Value'>𝕩</span></code>. The result <code><span class='Value'>z</span><span class='Gets'>←</span><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier'>`</span><span class='Value'>𝕩</span></code> is an array with the same shape as <code><span class='Value'>𝕩</span></code>. If it has length at least one, <code><span class='Function'>⊏</span><span class='Value'>z</span></code> is <code><span class='Function'>⊏</span><span class='Value'>𝕩</span></code> if <code><span class='Value'>𝕨</span></code> isn't given and <code><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier'>¨</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code> if it is. For <code><span class='Number'>0</span><span class='Function'>≤</span><span class='Value'>i</span></code>, <code><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>+</span><span class='Number'>1</span><span class='Paren'>)</span><span class='Function'>⊏</span><span class='Value'>z</span></code> is <code><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>⊏</span><span class='Value'>z</span><span class='Paren'>)</span><span class='Function'>𝔽</span><span class='Modifier'>¨</span><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>+</span><span class='Number'>1</span><span class='Paren'>)</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code>.</p> <p>The ordering of <code><span class='Function'>𝔽</span></code> application is the natural one for this definition: cells are computed in turn, and each instance of <code><span class='Function'>𝔽</span><span class='Modifier'>¨</span></code> goes in index order.</p> |