diff options
Diffstat (limited to 'docs/doc/under.html')
| -rw-r--r-- | docs/doc/under.html | 78 |
1 files changed, 78 insertions, 0 deletions
diff --git a/docs/doc/under.html b/docs/doc/under.html index 240fa324..58c9f9d4 100644 --- a/docs/doc/under.html +++ b/docs/doc/under.html @@ -26,3 +26,81 @@ </g> </svg> +<p>The Under 2-modifier expresses the idea of modifying <em>part</em> of an array, or applying a function in a different domain, such as working in logarithmic space. It works with a transformation <code><span class='Function'>𝔾</span></code> that applies to the original argument <code><span class='Value'>𝕩</span></code>, and a function <code><span class='Function'>𝔽</span></code> that applies to the result of <code><span class='Function'>𝔾</span></code> (and if <code><span class='Value'>𝕨</span></code> is given, <code><span class='Function'>𝔾</span><span class='Value'>𝕨</span></code> is used as the left argument to <code><span class='Function'>𝔽</span></code>). Under does the "same thing" as <code><span class='Function'>𝔽</span></code>, but to the original argument, by applying <code><span class='Function'>𝔾</span></code>, then <code><span class='Function'>𝔽</span></code>, then undoing <code><span class='Function'>𝔾</span></code> somehow.</p> +<p>It's not always possible to undo <code><span class='Function'>𝔾</span></code>, so only some right operands will work. BQN supports two cases. <strong>Computational</strong> Under tries the <a href="undo.html">Undo</a> modifier, so that <code><span class='Function'>𝔽</span><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span></code> is <code><span class='Function'>𝔾</span><span class='Modifier'>⁼</span><span class='Modifier2'>∘</span><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=MyAr4oy+KMOXy5wpIDQgICMgU3F1YXJlIHJvb3Qgb2Ygc3VtIG9mIHNxdWFyZXM=">↗️</a><pre> <span class='Number'>3</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='Comment'># Square root of sum of squares +</span>5 +</pre> +<p><strong>Structural</strong> Under is used when <code><span class='Function'>𝔾</span></code> selects part of the array. BQN tracks what was selected and puts the results from <code><span class='Function'>𝔽</span></code> back where they came from.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=K2DijL7iiL4g4p+oM+KAvzHigL8wLCAy4oC/NSwgMOKAvzDigL824p+pICAjIFByZWZpeCBzdW0sIGtlZXBpbmcgc3RydWN0dXJl">↗️</a><pre> <span class='Function'>+</span><span class='Modifier'>`</span><span class='Modifier2'>⌾</span><span class='Function'>∾</span> <span class='Bracket'>⟨</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Separator'>,</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Separator'>,</span> <span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>6</span><span class='Bracket'>⟩</span> <span class='Comment'># Prefix sum, keeping structure +</span>⟨ ⟨ 3 4 4 ⟩ ⟨ 6 11 ⟩ ⟨ 11 11 17 ⟩ ⟩ +</pre> +<p>Structural Under is an essential part of BQN because of how it can "change" an immutable <a href="array.html">array</a>, and it supports more functions and is always well defined. Computational Under's nice, but not so important. The reason they can both be supported as a single primitive is that they follow this unifying principle:</p> +<pre><span class='Paren'>(</span><span class='Function'>𝔾</span> <span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier2'>⌾</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='Modifier2'>○</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span> +</pre> +<p>That is, when you apply <code><span class='Function'>𝔽</span><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span></code> <em>before</em> applying <code><span class='Function'>𝔾</span></code>, you get the value that comes from applying <code><span class='Function'>𝔽</span></code> <em>after</em> <code><span class='Function'>𝔾</span></code>. The definition of computational under comes from applying <code><span class='Function'>𝔾</span><span class='Modifier'>⁼</span></code> to both sides and cancelling <code><span class='Function'>𝔾</span><span class='Modifier'>⁼</span><span class='Function'>𝔾</span></code>, which solves the constraint but doesn't have to be a unique solution. For structural Under, the reason this works is that <code><span class='Function'>𝔾</span></code> selects out the parts of <code><span class='Function'>𝔽</span><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span></code> that were placed back in by Under. Other parts are defined to be the same as it was in <code><span class='Value'>𝕩</span></code>, so the result is fully specified.</p> +<h2 id="structural-under"><a class="header" href="#structural-under">Structural Under</a></h2> +<p>A <em>structural function</em> is one that moves elements around without performing computation on them. It's okay if it performs computation, but it has to be based on the structure of its argument—shape, and element structure—and not on the values of atoms in it. As an example, the function <code><span class='Function'>⊏</span><span class='Modifier'>˘</span></code> selects the first column of an array.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGEg4oaQIDTigL8z4qWK4oaVMTIKCjHiirjijL3ijL4o4oqPy5gpIGE=">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>a</span> <span class='Gets'>←</span> <span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Function'>⥊↕</span><span class='Number'>12</span> +┌─ +╵ 0 1 2 + 3 4 5 + 6 7 8 + 9 10 11 + ┘ + + <span class='Number'>1</span><span class='Modifier2'>⊸</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='Value'>a</span> +┌─ +╵ 3 1 2 + 6 4 5 + 9 7 8 + 0 10 11 + ┘ +</pre> +<p>When used with Under, the function <code><span class='Number'>1</span><span class='Modifier2'>⊸</span><span class='Function'>⌽</span></code> applies to the first column, rotating it. The result of <code><span class='Function'>𝔽</span></code> needs to be compatible with the selection function, so Rotate works but trying to remove an element is no good:</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=MeKKuOKGk+KMvijiio/LmCkgYQ==">↗️</a><pre> <span class='Number'>1</span><span class='Modifier2'>⊸</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='Value'>a</span> +<span class='Error'>Error: ⁼: Inverse not found</span> +</pre> +<p>BQN can detect lots of structural functions when written in <a href="tacit.html">tacit</a> form; see the list of functions <a href="../spec/inferred.html#required-structural-inverses">in the spec</a>. You can also include computations on the shape. For example, here's a function to reverse the first half of a list.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oy94oy+KOKKouKGkcuc4omgw7cyy5kpICJhYmNkZWYi">↗️</a><pre> <span class='Function'>⌽</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Function'>⊢↑</span><span class='Modifier'>˜</span><span class='Function'>≠÷</span><span class='Number'>2</span><span class='Modifier'>˙</span><span class='Paren'>)</span> <span class='String'>"abcdef"</span> +"cbadef" +</pre> +<p>Under is useful with <a href="scan.html">scans</a>, as discussed in a section on <a href="scan.html#reverse-scan">reverse scan</a>. In this case, <code><span class='Function'>⌽</span></code> is exactly invertible, so <code><span class='Modifier2'>⌾</span></code> can just as easily be seen as computational Under. When <code><span class='Function'>𝔾</span></code> has an exact inverse, there can only be one solution to the constraint on Under, and both forms must be the same.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oinYOKMvuKMvSAx4oC/MOKAvzHigL8w4oC/MeKAvzHigL8x">↗️</a><pre> <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='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> +⟨ 0 0 0 0 1 1 1 ⟩ +</pre> +<h2 id="computational-under"><a class="header" href="#computational-under">Computational Under</a></h2> +<p>Computational Under is based on <a href="undo.html">Undo</a> (<code><span class='Modifier'>⁼</span></code>), and applies whenever structural Under doesn't. It's still limited, because Undo doesn't work on many or even most functions. One common use is with the square function <code><span class='Function'>×</span><span class='Modifier'>˜</span></code>, for computations such as finding the magnitude of a vector, or a <a href="https://en.wikipedia.org/wiki/Root_mean_square">root-mean-square</a> average like the one below.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=KCvCtMO34omgKeKMvijDl8ucKSAy4oC/M+KAvzTigL81">↗️</a><pre> <span class='Paren'>(</span><span class='Function'>+</span><span class='Modifier'>´</span><span class='Function'>÷≠</span><span class='Paren'>)</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Function'>×</span><span class='Modifier'>˜</span><span class='Paren'>)</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>5</span> +3.674234614174767 +</pre> +<p>This average is the square root of the average of the squares of the arguments, and <code><span class='Modifier2'>⌾</span></code> lets us combine the two square-y steps. Similarly, <code><span class='Modifier2'>⌾</span><span class='Function'>÷</span></code> can be used for a harmonic sum or mean (you might notice that computational Under is a lot more mathy than the structural one).</p> +<p>Under is the idiomatic way to do a round-to-nearest function:</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oyK4oy+KDEw4oq4w5cpIDMuNTI04oC/Ni43OTnigL8yLjAzMQ==">↗️</a><pre> <span class='Function'>⌊</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Number'>10</span><span class='Modifier2'>⊸</span><span class='Function'>×</span><span class='Paren'>)</span> <span class='Number'>3.524</span><span class='Ligature'>‿</span><span class='Number'>6.799</span><span class='Ligature'>‿</span><span class='Number'>2.031</span> +⟨ 3.5 6.7 2 ⟩ +</pre> +<p>See how it works? <code><span class='Function'>⌊</span></code> rounds down to an integer, but we can get it to round down to a decimal by first multiplying by 10 (single decimals are now integers), then rounding, then undoing that multiplication. A related idea is to not just round but produce a range. Suppose I want the arithmetic progression 4, 7, 10, ... <20. If I had the right range <code><span class='Function'>↕</span><span class='Value'>n</span></code>, then it would be <code><span class='Number'>4</span><span class='Function'>+</span><span class='Number'>3</span><span class='Function'>×↕</span><span class='Value'>n</span></code>, or <code><span class='Paren'>(</span><span class='Number'>4</span><span class='Function'>+</span><span class='Number'>3</span><span class='Function'>×⊢</span><span class='Paren'>)</span><span class='Function'>↕</span><span class='Value'>n</span></code>. By using the <em>inverse</em> of this transformation function on the desired endpoint, I can make sure it's applied on the way out, and BQN figures out what to do on the way in as if by magic.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oaV4oiY4oyI4oy+KCg0KzPDl+KKoinigbwpIDIw">↗️</a><pre> <span class='Function'>↕</span><span class='Modifier2'>∘</span><span class='Function'>⌈</span><span class='Modifier2'>⌾</span><span class='Paren'>((</span><span class='Number'>4</span><span class='Function'>+</span><span class='Number'>3</span><span class='Function'>×⊢</span><span class='Paren'>)</span><span class='Modifier'>⁼</span><span class='Paren'>)</span> <span class='Number'>20</span> +⟨ 4 7 10 13 16 19 ⟩ +</pre> +<p>Well, really it's a bit of simple algebra, but if it wants to wear a pointy hat and wave a wand around I won't judge.</p> +<h2 id="left-argument"><a class="header" href="#left-argument">Left argument</a></h2> +<p>When called dyadically, Under applies <code><span class='Function'>𝔽</span></code> dyadically, like <a href="compose.html#over">Over</a>. This doesn't affect the undoing part of Under, which still tries to put the result of <code><span class='Function'>𝔽</span></code> back into <code><span class='Value'>𝕩</span></code> for structural Under or invert <code><span class='Function'>𝔾</span></code> for computational. In fact, <code><span class='Value'>𝕨</span> <span class='Function'>𝔽</span><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span> <span class='Value'>𝕩</span></code> is equivalent to <code><span class='Paren'>(</span><span class='Function'>𝔾</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Modifier'>˙</span><span class='Modifier2'>⊸</span><span class='Function'>𝔽</span><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span> <span class='Value'>𝕩</span></code> so no exciting language stuff is happening here at all.</p> +<p>But you can still do some cool stuff with it! One pattern is simply to set <code><span class='Function'>𝔽</span></code> to <code><span class='Function'>⊣</span></code>, the <a href="identity.html">identity</a> function that just returns its left argument. Now structural Under will replace everything that <code><span class='Function'>𝔾</span></code> selects from <code><span class='Value'>𝕩</span></code> with the corresponding values in <code><span class='Value'>𝕨</span></code>. Here's an example that replaces elements with indices <code><span class='Number'>1</span></code> and <code><span class='Number'>2</span></code>.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ImFiY2QiIOKKo+KMvigx4oC/MuKKuOKKjykgIjAxMjMi">↗️</a><pre> <span class='String'>"abcd"</span> <span class='Function'>⊣</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span><span class='Paren'>)</span> <span class='String'>"0123"</span> +"0bc3" +</pre> +<p>This method can replace deeper structure too. Below, <code><span class='Function'>𝔾</span></code> is <code><span class='Number'>¯1</span><span class='Function'>⊑</span><span class='Modifier'>¨</span><span class='Number'>2</span><span class='Function'>↑⊢</span></code>, selecting the last element of each of the first two elements of its argument. The elements that aren't selected don't have to match up.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4p+oImFiIiwgImNkZSIsICJmZyLin6kg4oqj4oy+KMKvMeKKkcKoMuKGkeKKoikg4oaVwqgz4oC/MuKAvzHigL8x">↗️</a><pre> <span class='Bracket'>⟨</span><span class='String'>"ab"</span><span class='Separator'>,</span> <span class='String'>"cde"</span><span class='Separator'>,</span> <span class='String'>"fg"</span><span class='Bracket'>⟩</span> <span class='Function'>⊣</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Number'>¯1</span><span class='Function'>⊑</span><span class='Modifier'>¨</span><span class='Number'>2</span><span class='Function'>↑⊢</span><span class='Paren'>)</span> <span class='Function'>↕</span><span class='Modifier'>¨</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='Ligature'>‿</span><span class='Number'>1</span> +⟨ ⟨ 0 1 'b' ⟩ ⟨ 0 'e' ⟩ ⟨ 0 ⟩ ⟨ 0 ⟩ ⟩ +</pre> +<p>In fact, the elements that <em>are</em> selected don't really have to match up before being selected. So here's an example with <a href="join.html">Join</a> where the same pattern is used to "re-flow" <code><span class='Value'>𝕨</span></code> into the structure of <code><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=4p+oImFiIiwgImNkZSIsICJmZyLin6kg4oqj4oy+4oi+IOKfqCItLS0iLCAiLS0tLSLin6k=">↗️</a><pre> <span class='Bracket'>⟨</span><span class='String'>"ab"</span><span class='Separator'>,</span> <span class='String'>"cde"</span><span class='Separator'>,</span> <span class='String'>"fg"</span><span class='Bracket'>⟩</span> <span class='Function'>⊣</span><span class='Modifier2'>⌾</span><span class='Function'>∾</span> <span class='Bracket'>⟨</span><span class='String'>"---"</span><span class='Separator'>,</span> <span class='String'>"----"</span><span class='Bracket'>⟩</span> +⟨ "abc" "defg" ⟩ +</pre> +<h3 id="and-getting-it-not-to-do-that"><a class="header" href="#and-getting-it-not-to-do-that">And getting it not to do that</a></h3> +<p>The Over-based action on <code><span class='Value'>𝕨</span></code> shows up more than you might think, but sometimes you just want to pass a left argument to <code><span class='Function'>𝔽</span></code> without <code><span class='Function'>𝔾</span></code> getting involved. In this case you have to <a href="hook.html#bind">bind</a> it in: call <code><span class='Value'>𝕨</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=MeKAvzLigL8z4oq4K+KMvigx4oC/MeKAvzDigL8x4oq4LykgMTDigL8yMOKAvzMw4oC/NDA=">↗️</a><pre> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Modifier2'>⊸</span><span class='Function'>+</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Number'>1</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='Modifier2'>⊸</span><span class='Function'>/</span><span class='Paren'>)</span> <span class='Number'>10</span><span class='Ligature'>‿</span><span class='Number'>20</span><span class='Ligature'>‿</span><span class='Number'>30</span><span class='Ligature'>‿</span><span class='Number'>40</span> +⟨ 11 22 30 43 ⟩ +</pre> +<p>This <a href="../problems.html#underbind-combination-is-awkward">gets bad</a> when you want <code><span class='Value'>𝕨</span></code> to be an argument. In the worst case you might need to write out an operator <code><span class='Brace'>{</span><span class='Value'>𝕨</span><span class='Modifier2'>⊸</span><span class='Function'>𝔽</span><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code>.</p> |