diff options
Diffstat (limited to 'docs/doc/search.html')
| -rw-r--r-- | docs/doc/search.html | 72 |
1 files changed, 70 insertions, 2 deletions
diff --git a/docs/doc/search.html b/docs/doc/search.html index 118cd35a..285f8b46 100644 --- a/docs/doc/search.html +++ b/docs/doc/search.html @@ -6,6 +6,15 @@ <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="search-functions">Search functions</h1> <svg viewBox='-124.8 -46.8 532.8 280.8'> + <defs> + <mask id='m'> + <linearGradient id='grad' x2='0' y2='1'> + <stop offset='0.6' stop-color='#000'/> + <stop offset='0.9' stop-color='#fff'/> + </linearGradient> + <rect fill='url(#grad)' x='-86.4' y='0' width='456' height='72'/> + </mask> + </defs> <g font-family='BQN,monospace' font-size='19px' text-anchor='middle'> <rect class='code' stroke-width='1.5' rx='12' x='-86.4' y='-36' width='456' height='259.2'/> <g class='purple' stroke-width='0' opacity='0.5'> @@ -15,7 +24,7 @@ <g class='lilac' stroke-linecap='round'> <g stroke-width='1' stroke-dasharray='6,7'> <line x1='99.84' x2='332.16' y1='60.48' y2='11.52'/> - <line x1='243.84' x2='380.16' y1='60.48' y2='11.52'/> + <line mask='url(#m)' x1='243.84' x2='380.16' y1='60.48' y2='11.52'/> </g> <g stroke-width='1.5'> <line x1='92.16' x2='3.84' y1='60.48' y2='11.52'/> @@ -25,7 +34,7 @@ <line x1='3.84' x2='44.16' y1='60.48' y2='11.52'/> <line x1='44.16' x2='3.84' y1='60.48' y2='11.52'/> <line x1='140.16' x2='99.84' y1='60.48' y2='11.52'/> - <line x1='195.84' x2='380.16' y1='60.48' y2='11.52'/> + <line mask='url(#m)' x1='195.84' x2='380.16' y1='60.48' y2='11.52'/> </g> </g> <g fill='currentColor' font-size='12' opacity='0.75'> @@ -124,3 +133,62 @@ </table> <p>The searched-for argument is <code><span class='Value'>๐ฉ</span></code> in Index-of functions (<code><span class='Function'>โโ</span></code>) and <code><span class='Value'>๐จ</span></code> in Member of (<code><span class='Function'>โ</span></code>). <a href="order.html#bins">Bins</a> Up and Down (<code><span class='Function'>โโ</span></code>) are ordering functions but follow the same pattern as Index-of. It's split into cells, but not necessarily <em>major</em> cells: instead, the cells used match the rank of a major cell of the other (searched-in) argument. In the most common case, when the searched-in argument is a list, 0-cells are used for the search (we might also say elements, as it gives the same result).</p> <p>The result is always an array containing one number for each searched-for cell. For Index of and Member of, every result is computed independently; for Progressive Index of the result for a cell can depend on earlier cells, in index order.</p> +<h2 id="member-of">Member of</h2> +<p>The simplest of the search functions, Member of (<code><span class='Function'>โ</span></code>) returns <code><span class='Number'>1</span></code> if an entry in <code><span class='Value'>๐จ</span></code> matches some entry in <code><span class='Value'>๐ฉ</span></code>, and <code><span class='Number'>0</span></code> if it doesn't.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ImdyZWVuIuKAvyJicmlja3Mi4oC/ImNvdyLigL8iYmx1ZSIg4oiKICJyZWQi4oC/ImdyZWVuIuKAvyJibHVlIg==">โ๏ธ</a><pre> <span class='String'>"green"</span><span class='Ligature'>โฟ</span><span class='String'>"bricks"</span><span class='Ligature'>โฟ</span><span class='String'>"cow"</span><span class='Ligature'>โฟ</span><span class='String'>"blue"</span> <span class='Function'>โ</span> <span class='String'>"red"</span><span class='Ligature'>โฟ</span><span class='String'>"green"</span><span class='Ligature'>โฟ</span><span class='String'>"blue"</span> +โจ 1 0 0 1 โฉ +</pre> +<p>The result is independent of the ordering of <code><span class='Value'>๐ฉ</span></code>: all that matters is which cells it contains.</p> +<p>Member of can be used in a <a href="train.html">train</a> to compute the set intersection and difference of two arrays. For example, <code><span class='Function'>โ/โฃ</span></code> uses <code><span class='Value'>๐จ</span><span class='Function'>โ</span><span class='Value'>๐ฉ</span></code> to <a href="replicate.html">filter</a> <code><span class='Value'>๐จ</span></code> (from <code><span class='Value'>๐จ</span><span class='Function'>โฃ</span><span class='Value'>๐ฉ</span></code>), giving an intersection.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ImluaXRpYWwgc2V0IiAo4oiKL+KKoykgImludGVyc2VjdCIgICAgICMgS2VlcCDwnZWpCgoiaW5pdGlhbCBzZXQiICjCrOKImOKIii/iiqMpICJkaWZmZXJlbmNlIiAgIyBSZW1vdmUg8J2VqQ==">โ๏ธ</a><pre> <span class='String'>"initial set"</span> <span class='Paren'>(</span><span class='Function'>โ/โฃ</span><span class='Paren'>)</span> <span class='String'>"intersect"</span> <span class='Comment'># Keep ๐ฉ +</span>"initiset" + + <span class='String'>"initial set"</span> <span class='Paren'>(</span><span class='Function'>ยฌ</span><span class='Modifier2'>โ</span><span class='Function'>โ/โฃ</span><span class='Paren'>)</span> <span class='String'>"difference"</span> <span class='Comment'># Remove ๐ฉ +</span>"tal st" +</pre> +<p>These are the APL functions Intersect (<code><span class='Value'>โฉ</span></code>) and Without (<code><span class='Value'>~</span></code>). Really, only <code><span class='Value'>๐ฉ</span></code> is treated like a set, while the ordering and multiplicity of elements of <code><span class='Value'>๐จ</span></code> are maintained. I think the explicit implementations show this well, since <code><span class='Value'>๐ฉ</span></code> is only used as the right argument to <code><span class='Function'>โ</span></code>, and prefer this clarity to the brevity of a single symbol.</p> +<h2 id="index-of">Index of</h2> +<p>Index of (<code><span class='Function'>โ</span></code>) returns the index of the first occurrence of each entry in <code><span class='Value'>๐จ</span></code>, or <code><span class='Function'>โ </span><span class='Value'>๐จ</span></code> if an entry doesn't appear in <code><span class='Value'>๐จ</span></code> at all.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=Inplcm8i4oC/Im9uZSLigL8idHdvIuKAvyJ0aHJlZSIg4oqQICJvbmUi4oC/ImVpZ2h0IuKAvyJ0d28i">โ๏ธ</a><pre> <span class='String'>"zero"</span><span class='Ligature'>โฟ</span><span class='String'>"one"</span><span class='Ligature'>โฟ</span><span class='String'>"two"</span><span class='Ligature'>โฟ</span><span class='String'>"three"</span> <span class='Function'>โ</span> <span class='String'>"one"</span><span class='Ligature'>โฟ</span><span class='String'>"eight"</span><span class='Ligature'>โฟ</span><span class='String'>"two"</span> +โจ 1 4 2 โฉ +</pre> +<p><code><span class='Value'>๐ฉ</span><span class='Function'>โ</span><span class='Value'>๐จ</span></code> is the same as <code><span class='Paren'>(</span><span class='Value'>๐จ</span><span class='Function'>โ</span><span class='Value'>๐ฉ</span><span class='Paren'>)</span><span class='Function'><โ </span><span class='Value'>๐จ</span></code>. Note the reversal of arguments! In both <code><span class='Function'>โ</span></code> and <code><span class='Function'>โ</span></code>, the open side points to the searched-in argument and the closed side points to the searched-for argument. Relatedly, in Select (<code><span class='Function'>โ</span></code>), the open side points to the selected argument, which is more like the searched-in argument in that its cells are generally accessed out of order (the searched-for argument is most like the selection result <code><span class='Value'>๐จ</span><span class='Function'>โ</span><span class='Value'>๐ฉ</span></code>).</p> +<p>Index of always returns exactly one number, even if there are multiple matches, or no matches at all. To find the indices of all matches, start with <a href="match.html">Match</a> <a href="map.html">Each</a>, then <a href="replicate.html#indices">Indices</a> (I didn't mean for it to sound so repetitive! It just happened!).</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=LyAibGV0dGVycyIg4omhwqg8ICdlJyAgICAgICAgIyBNYW55IHRvIG9uZQoKImxldHRlcnMiICg84oiYL8uY4omh4oycy5wpICJsZXQiICAjIE1hbnkgdG8gbWFueQ==">โ๏ธ</a><pre> <span class='Function'>/</span> <span class='String'>"letters"</span> <span class='Function'>โก</span><span class='Modifier'>ยจ</span><span class='Function'><</span> <span class='String'>'e'</span> <span class='Comment'># Many to one +</span>โจ 1 4 โฉ + + <span class='String'>"letters"</span> <span class='Paren'>(</span><span class='Function'><</span><span class='Modifier2'>โ</span><span class='Function'>/</span><span class='Modifier'>ห</span><span class='Function'>โก</span><span class='Modifier'>โห</span><span class='Paren'>)</span> <span class='String'>"let"</span> <span class='Comment'># Many to many +</span>โจ โจ 0 โฉ โจ 1 4 โฉ โจ 2 3 โฉ โฉ +</pre> +<h2 id="progressive-index-of">Progressive Index of</h2> +<p>Progressive Index of (<code><span class='Function'>โ</span></code>), as the name and glyph suggest, is a more sophisticated variant of Index of. Like Index of, it returns either <code><span class='Function'>โ </span><span class='Value'>๐จ</span></code> or an index of a cell from <code><span class='Value'>๐จ</span></code> that matches the given cell of <code><span class='Value'>๐ฉ</span></code>. Unlike Index of, no index except <code><span class='Function'>โ </span><span class='Value'>๐จ</span></code> can ever be repeated. Progressive Index of returns the index of the first <em>unused</em> match, provided there's still one left.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ImFhYSIg4oqSICJhYWFhYSIKCiJhYWFiYiIg4oqSICJhYmFiYWJhYmFiIg==">โ๏ธ</a><pre> <span class='String'>"aaa"</span> <span class='Function'>โ</span> <span class='String'>"aaaaa"</span> +โจ 0 1 2 3 3 โฉ + + <span class='String'>"aaabb"</span> <span class='Function'>โ</span> <span class='String'>"ababababab"</span> +โจ 0 3 1 4 2 5 5 5 5 5 โฉ +</pre> +<p>Above we said that <code><span class='Value'>๐ฉ</span><span class='Function'>โ</span><span class='Value'>๐จ</span></code> is <code><span class='Paren'>(</span><span class='Value'>๐จ</span><span class='Function'>โ</span><span class='Value'>๐ฉ</span><span class='Paren'>)</span><span class='Function'><โ </span><span class='Value'>๐จ</span></code>, so that <code><span class='Function'>โ</span><span class='Modifier'>ห</span><span class='Function'><โ </span><span class='Modifier2'>โ</span><span class='Function'>โข</span></code> is an implementation of Member of. The corresponding <code><span class='Function'>โ</span><span class='Modifier'>ห</span><span class='Function'><โ </span><span class='Modifier2'>โ</span><span class='Function'>โข</span></code> implements <em>progressive</em> member of, that is, membership on <a href="https://en.wikipedia.org/wiki/Multiset">multisets</a>. So if <code><span class='Value'>๐ฉ</span></code> contains two copies of <code><span class='String'>'a'</span></code>, only the first to instances of <code><span class='String'>'a'</span></code> in <code><span class='Value'>๐จ</span></code> are considered to belong to it. And like membership is useful for set intersection and difference, progressive membership gives multiset versions of these.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ImFhYmJjYyIgKOKKkMucPOKJoOKImOKKoikgImJhYSIKCiJhYWJiY2MiICjiipLLnDziiaDiiJjiiqIpICJiYWEiCgoiYWFiYmNjIiAoKOKKksucPeKJoOKImOKKoikv4oqjKSAiYmFhIiAgIyBNdWx0aXNldCBkaWZmZXJlbmNl">โ๏ธ</a><pre> <span class='String'>"aabbcc"</span> <span class='Paren'>(</span><span class='Function'>โ</span><span class='Modifier'>ห</span><span class='Function'><โ </span><span class='Modifier2'>โ</span><span class='Function'>โข</span><span class='Paren'>)</span> <span class='String'>"baa"</span> +โจ 1 1 1 1 0 0 โฉ + + <span class='String'>"aabbcc"</span> <span class='Paren'>(</span><span class='Function'>โ</span><span class='Modifier'>ห</span><span class='Function'><โ </span><span class='Modifier2'>โ</span><span class='Function'>โข</span><span class='Paren'>)</span> <span class='String'>"baa"</span> +โจ 1 1 1 0 0 0 โฉ + + <span class='String'>"aabbcc"</span> <span class='Paren'>((</span><span class='Function'>โ</span><span class='Modifier'>ห</span><span class='Function'>=โ </span><span class='Modifier2'>โ</span><span class='Function'>โข</span><span class='Paren'>)</span><span class='Function'>/โฃ</span><span class='Paren'>)</span> <span class='String'>"baa"</span> <span class='Comment'># Multiset difference +</span>"bcc" +</pre> +<p>This primitive gives an interesting way to implement the <a href="order.html#ordinals">ordinals</a> pattern that might be easier to understand than the APL classic <code><span class='Function'>โโ</span></code> (it's probably a little slower though). The idea is to use the sorted array as the left argument to <code><span class='Function'>โ</span></code>. Now the index returned for each cell is just where it ended up in that sorted order. If we used ordinary Index of then equal cells would share the smallest index; Progressive Index of means ties are broken in favor of earlier cells.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4o2L4oiY4o2LICJhZGViY2VkYmEiCgriiKfiirjiipIgImFkZWJjZWRiYSIKCuKIp+KKuOKKkCAiYWRlYmNlZGJhIiAgIyBUaWVzIGluY2x1ZGVk">โ๏ธ</a><pre> <span class='Function'>โ</span><span class='Modifier2'>โ</span><span class='Function'>โ</span> <span class='String'>"adebcedba"</span> +โจ 0 5 7 2 4 8 6 3 1 โฉ + + <span class='Function'>โง</span><span class='Modifier2'>โธ</span><span class='Function'>โ</span> <span class='String'>"adebcedba"</span> +โจ 0 5 7 2 4 8 6 3 1 โฉ + + <span class='Function'>โง</span><span class='Modifier2'>โธ</span><span class='Function'>โ</span> <span class='String'>"adebcedba"</span> <span class='Comment'># Ties included +</span>โจ 0 5 7 2 4 7 5 2 0 โฉ +</pre> +<p>Here's a goofy code golf tip: if the two arguments to Progressive Index of are the same, then every cell will be matched to itself, because all the previous indices are taken but the current one does match. So <code><span class='Function'>โ</span><span class='Modifier'>ห</span></code> is the same as <code><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=4oqSy5wgImFueXRoaW5nIGF0IGFsbCI=">โ๏ธ</a><pre> <span class='Function'>โ</span><span class='Modifier'>ห</span> <span class='String'>"anything at all"</span> +โจ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 โฉ +</pre> |