diff options
| author | Marshall Lochbaum <mwlochbaum@gmail.com> | 2021-07-16 22:53:01 -0400 |
|---|---|---|
| committer | Marshall Lochbaum <mwlochbaum@gmail.com> | 2021-07-16 22:53:01 -0400 |
| commit | 247a554649e7cd0f165c716d4ec4e9a984349e56 (patch) | |
| tree | 4cb280a55b80d36b0943c12227c8459d8133d19a | |
| parent | d52e68535a2a3af69cd9aa24796d2cdcd18aaa58 (diff) | |
Actually add the files
| -rw-r--r-- | doc/find.md | 41 | ||||
| -rw-r--r-- | docs/doc/find.html | 80 |
2 files changed, 121 insertions, 0 deletions
diff --git a/doc/find.md b/doc/find.md new file mode 100644 index 00000000..b91a5930 --- /dev/null +++ b/doc/find.md @@ -0,0 +1,41 @@ +*View this file with results and syntax highlighting [here](https://mlochbaum.github.io/BQN/doc/find.html).* + +# Find + +Find (`β·`) searches for occurrences of an array `π¨` within `π©`. The result contains a boolean for each possible location, which is 1 if `π¨` was found there and 0 if not. + + "xx" β· "xxbdxxxcx" + +More precisely `π¨` needs to [match](match.md) a contiguous selection from `π©`, which for strings means a substring. These subarrays of `π©` are also exactly the cells in the result of [Windows](windows.md). In fact we can use Windows to see all the arrays `π¨` will be compared against. + + 2 β "xxbdxxxcx" + + "xx"βΈβ‘Λ 2 β "xxbdxxxcx" + +Like Windows, the result usually doesn't have the same dimensions as `π©`. This is easier to see when `π¨` is longer. It differs from APL's version, which includes trailing 0s in order to maintain the same length. Bringing the size up to that of `π©` is easy enough with [Take](take.md) (`β`), while shortening a padded result would be harder. + + "string" β· "substring" + + "string" (β’ββ’ββ·) "substring" # APL style + +If `π¨` is larger than `π©`, the result is empty, and there's no error even in cases where Windows would fail. One place this tends to come up is when applying [First](pick.md) (`β`) the result: `ββ·` tests whether `π¨` appears in `π©` at the first position, that is, whether it's a prefix of `π©`. If `π¨` is longer than `π©` it shouldn't be a prefix, so 0 is appropriate. + + "loooooong" β· "short" + + 9 β "short" + + β "loooooong" β· "short" + +This pattern also works in the high-rank case discussed below, testing whether `π¨` is a multi-dimensional prefix starting at the lowest-index corner of `π©`. + +### Higher ranks + +If `π¨` and `π©` are two-dimensional then Find does a two-dimensional search. The cells used are also found in `π¨β’βΈβπ©`. For example, the bottom-right corner of `π©` below matches `π¨`, so there's a 1 in the bottom-right corner of the result. + + β’ a β 7 (4|βΛ)βββ 9 # Array with patterns + + (0βΏ3βΏ0β0βΏ1βΏ0) β· a + +It's also allowed for `π¨` to have a smaller rank than `π©`; in this case leading axes of `π©` are mapped over so that axes of `π¨` correspond to trailing axes of `π©`. This is a minor violation of the [leading axis](leading.md) principle, which would match axes of `π¨` to leading axes of `π©` in order to make a function that's useful with the Rank operator, but such a function would be quite strange and hardly ever useful. + + 0βΏ1βΏ0βΏ1 β· a diff --git a/docs/doc/find.html b/docs/doc/find.html new file mode 100644 index 00000000..bc883db2 --- /dev/null +++ b/docs/doc/find.html @@ -0,0 +1,80 @@ +<head> + <link href="../favicon.ico" rel="shortcut icon" type="image/x-icon"/> + <link href="../style.css" rel="stylesheet"/> + <title>BQN: Find</title> +</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="find">Find</h1> +<p>Find (<code><span class='Function'>β·</span></code>) searches for occurrences of an array <code><span class='Value'>π¨</span></code> within <code><span class='Value'>π©</span></code>. The result contains a boolean for each possible location, which is 1 if <code><span class='Value'>π¨</span></code> was found there and 0 if not.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=Inh4IiDijbcgInh4YmR4eHhjeCI=">βοΈ</a><pre> <span class='String'>"xx"</span> <span class='Function'>β·</span> <span class='String'>"xxbdxxxcx"</span> +β¨ 1 0 0 0 1 1 0 0 β© +</pre> +<p>More precisely <code><span class='Value'>π¨</span></code> needs to <a href="match.html">match</a> a contiguous selection from <code><span class='Value'>π©</span></code>, which for strings means a substring. These subarrays of <code><span class='Value'>π©</span></code> are also exactly the cells in the result of <a href="windows.html">Windows</a>. In fact we can use Windows to see all the arrays <code><span class='Value'>π¨</span></code> will be compared against.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=MiDihpUgInh4YmR4eHhjeCIKCiJ4eCLiirjiiaHLmCAyIOKGlSAieHhiZHh4eGN4Ig==">βοΈ</a><pre> <span class='Number'>2</span> <span class='Function'>β</span> <span class='String'>"xxbdxxxcx"</span> +ββ +β΅"xx + xb + bd + dx + xx + xx + xc + cx" + β + + <span class='String'>"xx"</span><span class='Modifier2'>βΈ</span><span class='Function'>β‘</span><span class='Modifier'>Λ</span> <span class='Number'>2</span> <span class='Function'>β</span> <span class='String'>"xxbdxxxcx"</span> +β¨ 1 0 0 0 1 1 0 0 β© +</pre> +<p>Like Windows, the result usually doesn't have the same dimensions as <code><span class='Value'>π©</span></code>. This is easier to see when <code><span class='Value'>π¨</span></code> is longer. It differs from APL's version, which includes trailing 0s in order to maintain the same length. Bringing the size up to that of <code><span class='Value'>π©</span></code> is easy enough with <a href="take.html">Take</a> (<code><span class='Function'>β</span></code>), while shortening a padded result would be harder.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=InN0cmluZyIg4o23ICJzdWJzdHJpbmciCgoic3RyaW5nIiAo4omi4oiY4oqi4oaR4o23KSAic3Vic3RyaW5nIiAgIyBBUEwgc3R5bGU=">βοΈ</a><pre> <span class='String'>"string"</span> <span class='Function'>β·</span> <span class='String'>"substring"</span> +β¨ 0 0 0 1 β© + + <span class='String'>"string"</span> <span class='Paren'>(</span><span class='Function'>β’</span><span class='Modifier2'>β</span><span class='Function'>β’ββ·</span><span class='Paren'>)</span> <span class='String'>"substring"</span> <span class='Comment'># APL style +</span>β¨ 0 0 0 1 0 0 0 0 0 β© +</pre> +<p>If <code><span class='Value'>π¨</span></code> is larger than <code><span class='Value'>π©</span></code>, the result is empty, and there's no error even in cases where Windows would fail. One place this tends to come up is when applying <a href="pick.html">First</a> (<code><span class='Function'>β</span></code>) the result: <code><span class='Function'>ββ·</span></code> tests whether <code><span class='Value'>π¨</span></code> appears in <code><span class='Value'>π©</span></code> at the first position, that is, whether it's a prefix of <code><span class='Value'>π©</span></code>. If <code><span class='Value'>π¨</span></code> is longer than <code><span class='Value'>π©</span></code> it shouldn't be a prefix, so 0 is appropriate.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=Imxvb29vb29uZyIg4o23ICJzaG9ydCIKCjkg4oaVICJzaG9ydCIKCuKKkSAibG9vb29vb25nIiDijbcgInNob3J0Ig==">βοΈ</a><pre> <span class='String'>"loooooong"</span> <span class='Function'>β·</span> <span class='String'>"short"</span> +β¨β© + + <span class='Number'>9</span> <span class='Function'>β</span> <span class='String'>"short"</span> +ERROR + + <span class='Function'>β</span> <span class='String'>"loooooong"</span> <span class='Function'>β·</span> <span class='String'>"short"</span> +0 +</pre> +<p>This pattern also works in the high-rank case discussed below, testing whether <code><span class='Value'>π¨</span></code> is a multi-dimensional prefix starting at the lowest-index corner of <code><span class='Value'>π©</span></code>.</p> +<h3 id="higher-ranks">Higher ranks</h3> +<p>If <code><span class='Value'>π¨</span></code> and <code><span class='Value'>π©</span></code> are two-dimensional then Find does a two-dimensional search. The cells used are also found in <code><span class='Value'>π¨</span><span class='Function'>β’</span><span class='Modifier2'>βΈ</span><span class='Function'>β</span><span class='Value'>π©</span></code>. For example, the bottom-right corner of <code><span class='Value'>π©</span></code> below matches <code><span class='Value'>π¨</span></code>, so there's a 1 in the bottom-right corner of the result.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGEg4oaQIDcgKDR84ouGy5wp4oyc4peL4oaVIDkgICAjIEFycmF5IHdpdGggcGF0dGVybnMKCigw4oC/M+KAvzDiiY0w4oC/MeKAvzApIOKNtyBh">βοΈ</a><pre> <span class='Function'>β’</span> <span class='Value'>a</span> <span class='Gets'>β</span> <span class='Number'>7</span> <span class='Paren'>(</span><span class='Number'>4</span><span class='Function'>|β</span><span class='Modifier'>Λ</span><span class='Paren'>)</span><span class='Modifier'>β</span><span class='Modifier2'>β</span><span class='Function'>β</span> <span class='Number'>9</span> <span class='Comment'># Array with patterns +</span>ββ +β΅ 1 1 1 1 1 1 1 1 1 + 0 1 2 3 0 1 2 3 0 + 0 1 0 1 0 1 0 1 0 + 0 1 0 3 0 1 0 3 0 + 0 1 0 1 0 1 0 1 0 + 0 1 0 3 0 1 0 3 0 + 0 1 0 1 0 1 0 1 0 + β + + <span class='Paren'>(</span><span class='Number'>0</span><span class='Ligature'>βΏ</span><span class='Number'>3</span><span class='Ligature'>βΏ</span><span class='Number'>0</span><span class='Function'>β</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='Paren'>)</span> <span class='Function'>β·</span> <span class='Value'>a</span> +ββ +β΅ 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 + 0 0 1 0 0 0 1 + 0 0 0 0 0 0 0 + 0 0 1 0 0 0 1 + β +</pre> +<p>It's also allowed for <code><span class='Value'>π¨</span></code> to have a smaller rank than <code><span class='Value'>π©</span></code>; in this case leading axes of <code><span class='Value'>π©</span></code> are mapped over so that axes of <code><span class='Value'>π¨</span></code> correspond to trailing axes of <code><span class='Value'>π©</span></code>. This is a minor violation of the <a href="leading.html">leading axis</a> principle, which would match axes of <code><span class='Value'>π¨</span></code> to leading axes of <code><span class='Value'>π©</span></code> in order to make a function that's useful with the Rank operator, but such a function would be quite strange and hardly ever useful.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=MOKAvzHigL8w4oC/MSDijbcgYQ==">βοΈ</a><pre> <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='Function'>β·</span> <span class='Value'>a</span> +ββ +β΅ 0 0 0 0 0 0 + 0 0 0 0 0 0 + 1 0 1 0 1 0 + 0 0 0 0 0 0 + 1 0 1 0 1 0 + 0 0 0 0 0 0 + 1 0 1 0 1 0 + β +</pre> |