1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">doc</a></div>
<h1 id="find"><a class="header" href="#find">Find</a></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>. So 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">First</a> (<code><span class='Function'>โ</span></code>) to 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. First will fail but using a <a href="fold.html">fold</a> <code><span class='Number'>0</span><span class='Function'>โฃ</span><span class='Modifier'>ยด</span><span class='Function'>โท</span></code> instead gives a 0 in this case.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=Imxvb29vb29uZyIg4o23ICJzaG9ydCIKCjkg4oaVICJzaG9ydCIKCjAg4oqjwrQgImxvb29vb29uZyIg4o23ICJzaG9ydCI=">โ๏ธ</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>
<span class='Error'>Error: โ: Window length ๐จ must be at most axis length plus one</span>
<span class='Number'>0</span> <span class='Function'>โฃ</span><span class='Modifier'>ยด</span> <span class='String'>"loooooong"</span> <span class='Function'>โท</span> <span class='String'>"short"</span>
0
</pre>
<p>Adding a <a href="reshape.html#deshape">Deshape</a> gives <code><span class='Number'>0</span><span class='Function'>โฃ</span><span class='Modifier'>ยด</span><span class='Function'>โฅ</span><span class='Modifier2'>โ</span><span class='Function'>โท</span></code>, which works with the high-rank case discussed below. It tests 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"><a class="header" href="#higher-ranks">Higher ranks</a></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>; the axes of <code><span class='Value'>๐จ</span></code> then correspond to trailing axes of <code><span class='Value'>๐ฉ</span></code>, so that leading axes of <code><span class='Value'>๐ฉ</span></code> are mapped over. 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=4oqiIGEg4oaQIDcgKDR84ouGy5wp4oyc4peL4oaVIDkgICAjIEFycmF5IHdpdGggcGF0dGVybnMKMOKAvzHigL8w4oC/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>
|
