docs/doc/windows.html


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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

<head>
  <link href="../favicon.ico" rel="shortcut icon" type="image/x-icon"/>
  <link href="../style.css" rel="stylesheet"/>
  <title>BQN: Windows</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="windows"><a class="header" href="#windows">Windows</a></h1>
<p>The Windows function returns all slices, or contiguous subarrays, with shape (well, shape prefix) <code><span class='Value'>𝕨</span></code> from <code><span class='Value'>𝕩</span></code>. It might also be seen as sliding a moving window along <code><span class='Value'>𝕩</span></code>.</p>
<p>This function replaces APL's Windowed Reduction, J's more general Infix operator, and Dyalog APL's Stencil, which is adapted from one case of J's Cut operator. In BQN, it's strongly preferred to use functions, and not modifiers, for array manipulation. Functions are simpler with fewer moving parts, and more concrete, since the array results can always be viewed right away.</p>
<h2 id="basic-case"><a class="header" href="#basic-case">Basic case</a></h2>
<p>We'll start with the one-axis case. Here <code><span class='Value'>𝕨</span></code> is a number between <code><span class='Number'>0</span></code> and <code><span class='Number'>1</span><span class='Function'>+≠</span><span class='Value'>𝕩</span></code>. The result is composed of slices of <code><span class='Value'>𝕩</span></code> (contiguous sections of <a href="array.html#cells">major cells</a>) with length <code><span class='Value'>𝕨</span></code>, starting at each possible index in order.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=NeKGlSJhYmNkZWZnIg==">↗️</a><pre>    <span class='Number'>5</span><span class='Function'>↕</span><span class='String'>&quot;abcdefg&quot;</span>
┌─       
╵"abcde  
  bcdef  
  cdefg" 
        ┘
</pre>
<p>There are <code><span class='Number'>1</span><span class='Function'>+</span><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>-</span><span class='Value'>𝕨</span></code>, or <code><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>¬</span><span class='Value'>𝕨</span></code>, of these sections, because the starting index must be at least <code><span class='Number'>0</span></code> and at most <code><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>-</span><span class='Value'>𝕨</span></code>. Another way to find this result is to look at the number of cells in or before a given slice: there are always <code><span class='Value'>𝕨</span></code> in the slice and there are only <code><span class='Function'>≠</span><span class='Value'>𝕩</span></code> in total, so the number of slices is the range <a href="logic.html">spanned</a> by these two endpoints.</p>
<p>A single slice of an array <code><span class='Value'>𝕩</span></code> with length <code><span class='Value'>l</span></code> and starting index <code><span class='Value'>i</span></code> is <code><span class='Value'>l</span><span class='Function'>↑</span><span class='Value'>i</span><span class='Function'>↓</span><span class='Value'>𝕩</span></code>, using <a href="take.html">Take and Drop</a>. The <a href="prefixes.html">Prefixes</a> function returns all the slices that end at the end of the array (<code><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>=</span><span class='Value'>i</span><span class='Function'>+</span><span class='Value'>l</span></code>), and Suffixes gives the slices that start at the beginning (<code><span class='Value'>i</span><span class='Function'>=</span><span class='Number'>0</span></code>). Windows gives yet another collection of slices: the ones that have a fixed length <code><span class='Value'>l</span><span class='Function'>=</span><span class='Value'>𝕨</span></code>. Selecting one cell from its result gives the slice starting at that cell's index:</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=MuKKjzXihpUiYWJjZGVmZyIKCjXihpEy4oaTImFiY2RlZmci">↗️</a><pre>    <span class='Number'>2</span><span class='Function'>⊏</span><span class='Number'>5</span><span class='Function'>↕</span><span class='String'>&quot;abcdefg&quot;</span>
"cdefg"

    <span class='Number'>5</span><span class='Function'>↑</span><span class='Number'>2</span><span class='Function'>↓</span><span class='String'>&quot;abcdefg&quot;</span>
"cdefg"
</pre>
<p>Windows differs from Prefixes and Suffixes in that it doesn't add a layer of nesting (it doesn't enclose each slice). This is possible because the slices have a fixed size, so they fit together as cells of an array.</p>
<h2 id="windowed-reduction"><a class="header" href="#windowed-reduction">Windowed reduction</a></h2>
<p>Windows can be followed up with <a href="fold.html#insert">Insert</a> on each slice to give a windowed reduction or fold. Here we take running sums of 3 values.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=K8udy5gz4oaVIOKfqDIsNiwwLDEsNCwz4p+p">↗️</a><pre>    <span class='Function'>+</span><span class='Modifier'>˝˘</span><span class='Number'>3</span><span class='Function'>↕</span> <span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Separator'>,</span><span class='Number'>6</span><span class='Separator'>,</span><span class='Number'>0</span><span class='Separator'>,</span><span class='Number'>1</span><span class='Separator'>,</span><span class='Number'>4</span><span class='Separator'>,</span><span class='Number'>3</span><span class='Bracket'>⟩</span>
⟨ 8 7 5 8 ⟩
</pre>
<p>A common task is to act on windows with an initial or final element so the total length stays the same. When using windows of length 2, the best way to accomplish this is with a <a href="shift.html">shift</a> <code><span class='Function'>«</span></code> or <code><span class='Function'>»</span></code>. If the window length is longer or variable, then a trick with Windows works better: add the elements, and then use windows matching the original length. Here we invert Plus <a href="scan.html">Scan</a> <code><span class='Function'>+</span><span class='Modifier'>`</span></code>, which requires we take pairwise differences starting at initial value 0.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=LeKfnCgwwrviiqIpICtgIDPigL8y4oC/MeKAvzEKCigty5zLneKJoOKGlTDiiL7iiqIpICtgIDPigL8y4oC/MeKAvzE=">↗️</a><pre>    <span class='Function'>-</span><span class='Modifier2'>⟜</span><span class='Paren'>(</span><span class='Number'>0</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>
⟨ 3 2 1 1 ⟩

    <span class='Paren'>(</span><span class='Function'>-</span><span class='Modifier'>˜˝</span><span class='Function'>≠↕</span><span class='Number'>0</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>
⟨ 3 2 1 1 ⟩
</pre>
<p>With Windows, we can modify the 3-element running sum from before to keep the length constant by starting with two zeros.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=KCvLneKJoOKGlSgy4qWKMCniirjiiL4pIOKfqDIsNiwwLDEsNCwz4p+p">↗️</a><pre>    <span class='Paren'>(</span><span class='Function'>+</span><span class='Modifier'>˝</span><span class='Function'>≠↕</span><span class='Paren'>(</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='Number'>0</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>∾</span><span class='Paren'>)</span> <span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Separator'>,</span><span class='Number'>6</span><span class='Separator'>,</span><span class='Number'>0</span><span class='Separator'>,</span><span class='Number'>1</span><span class='Separator'>,</span><span class='Number'>4</span><span class='Separator'>,</span><span class='Number'>3</span><span class='Bracket'>⟩</span>
⟨ 2 8 8 7 5 8 ⟩
</pre>
<h2 id="symmetry"><a class="header" href="#symmetry">Symmetry</a></h2>
<p>Let's look at the first example, paired with its <a href="transpose.html">Transpose</a> (<code><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=4ouI4p+c4o2JIDXihpUiYWJjZGVmZyI=">↗️</a><pre>    <span class='Function'>⋈</span><span class='Modifier2'>⟜</span><span class='Function'>⍉</span> <span class='Number'>5</span><span class='Function'>↕</span><span class='String'>&quot;abcdefg&quot;</span>
┌─                   
· ┌─        ┌─       
  ╵"abcde   ╵"abc    
    bcdef     bcd    
    cdefg"    cde    
          ┘   def    
              efg"   
                  ┘  
                    ┘
</pre>
<p>Although the two arrays have different shapes, they're identical in the 3×3 region where they overlap.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4omh4peLKDPigL8z4oq44oaRKeKfnOKNiSA14oaVImFiY2RlZmci">↗️</a><pre>    <span class='Function'>≡</span><span class='Modifier2'>○</span><span class='Paren'>(</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Modifier2'>⊸</span><span class='Function'>↑</span><span class='Paren'>)</span><span class='Modifier2'>⟜</span><span class='Function'>⍉</span> <span class='Number'>5</span><span class='Function'>↕</span><span class='String'>&quot;abcdefg&quot;</span>
1
</pre>
<p>More concretely, the <code><span class='Value'>i</span></code>th element of slice <code><span class='Value'>j</span></code> is the same as the <code><span class='Value'>j</span></code>th element of slice <code><span class='Value'>i</span></code>: it's the <code><span class='Value'>i</span><span class='Function'>+</span><span class='Value'>j</span></code>th element of the argument. So transposing still gives a possible result of Windows, but with a different slice length. The two lengths are related by <a href="logic.html">Span</a>, which converts between length and number of slices.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=eyg14oaV8J2VqSniiaHijYkoM+KGlfCdlakpfSJhYmNkZWZnIgoKKOKJoCJhYmNkZWZnIikgwqwgMw==">↗️</a><pre>    <span class='Brace'>{</span><span class='Paren'>(</span><span class='Number'>5</span><span class='Function'>↕</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>≡⍉</span><span class='Paren'>(</span><span class='Number'>3</span><span class='Function'>↕</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Brace'>}</span><span class='String'>&quot;abcdefg&quot;</span>
1

    <span class='Paren'>(</span><span class='Function'>≠</span><span class='String'>&quot;abcdefg&quot;</span><span class='Paren'>)</span> <span class='Function'>¬</span> <span class='Number'>3</span>
5
</pre>
<h2 id="multiple-dimensions"><a class="header" href="#multiple-dimensions">Multiple dimensions</a></h2>
<p>The right argument can have rank more than 1, and it's viewed as a list of major cells following <a href="leading.html">leading axis</a> principles. As an example, Windows can take two-row slices of a shape <code><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</span></code> array.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ICAgIDLihpVbIjAxMjMiLCJhYmNkIiwiQUJDRCJdCgo84o6JMiAy4oaVWyIwMTIzIiwiYWJjZCIsIkFCQ0QiXQ==">↗️</a><pre>        <span class='Number'>2</span><span class='Function'>↕</span><span class='Bracket'>[</span><span class='String'>&quot;0123&quot;</span><span class='Separator'>,</span><span class='String'>&quot;abcd&quot;</span><span class='Separator'>,</span><span class='String'>&quot;ABCD&quot;</span><span class='Bracket'>]</span>
┌─      
╎"0123  
  abcd  
        
 ·abcd  
  ABCD" 
       ┘

    <span class='Function'>&lt;</span><span class='Modifier2'>⎉</span><span class='Number'>2</span> <span class='Number'>2</span><span class='Function'>↕</span><span class='Bracket'>[</span><span class='String'>&quot;0123&quot;</span><span class='Separator'>,</span><span class='String'>&quot;abcd&quot;</span><span class='Separator'>,</span><span class='String'>&quot;ABCD&quot;</span><span class='Bracket'>]</span>
┌─                   
· ┌─       ┌─        
  ╵"0123   ╵"abcd    
    abcd"    ABCD"   
         ┘        ┘  
                    ┘
</pre>
<p>In the second version we've enclosed each slice with <code><span class='Function'>&lt;</span><span class='Modifier2'>⎉</span><span class='Number'>2</span></code> for viewing—a slice has rank 2, the same as <code><span class='Value'>𝕩</span></code>. Passing a list as the left argument to Windows takes slices along any number of leading axes. Here are all the shape <code><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>2</span></code> slices:</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=POKOiTIgMuKAvzLihpVbIjAxMjMiLCJhYmNkIiwiQUJDRCJd">↗️</a><pre>    <span class='Function'>&lt;</span><span class='Modifier2'>⎉</span><span class='Number'>2</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>↕</span><span class='Bracket'>[</span><span class='String'>&quot;0123&quot;</span><span class='Separator'>,</span><span class='String'>&quot;abcd&quot;</span><span class='Separator'>,</span><span class='String'>&quot;ABCD&quot;</span><span class='Bracket'>]</span>
┌─                      
╵ ┌─     ┌─     ┌─      
  ╵"01   ╵"12   ╵"23    
    ab"    bc"    cd"   
       ┘      ┘      ┘  
  ┌─     ┌─     ┌─      
  ╵"ab   ╵"bc   ╵"cd    
    AB"    BC"    CD"   
       ┘      ┘      ┘  
                       ┘
</pre>
<p>The slices are naturally arranged along multiple dimensions according to their starting index. Once again the equivalence <code><span class='Value'>i</span><span class='Function'>⊏</span><span class='Value'>l</span><span class='Function'>↕</span><span class='Value'>x</span></code> ←→ <code><span class='Value'>l</span><span class='Function'>↑</span><span class='Value'>i</span><span class='Function'>↓</span><span class='Value'>x</span></code> holds, provided <code><span class='Value'>i</span></code> and <code><span class='Value'>l</span></code> have the same length.</p>
<p>If <code><span class='Value'>𝕨</span></code> has length <code><span class='Number'>0</span></code>, then <code><span class='Value'>𝕩</span></code> is not sliced along any dimensions. The only slice that results—the entire argument—is then arranged along an additional zero dimensions. In the end, the result is <code><span class='Value'>𝕩</span></code>, unchanged.</p>
<p>Here's a more formal definition: <code><span class='Value'>𝕩</span></code> is an array. <code><span class='Value'>𝕨</span></code> is a number, or numeric list or unit, with <code><span class='Value'>𝕨</span><span class='Function'>≤</span><span class='Modifier2'>○</span><span class='Function'>≠≢</span><span class='Value'>𝕩</span></code>. The result <code><span class='Value'>z</span></code> has shape <code><span class='Value'>𝕨</span><span class='Function'>∾¬</span><span class='Modifier2'>⟜</span><span class='Value'>𝕨</span><span class='Modifier2'>⌾</span><span class='Paren'>((</span><span class='Function'>≠</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>↑</span><span class='Paren'>)</span><span class='Function'>≢</span><span class='Value'>𝕩</span></code>, and element <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>z</span></code> is <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>z</span></code> ←→ <code><span class='Value'>𝕩</span><span class='Function'>⊑</span><span class='Modifier'>˜</span><span class='Function'>+</span><span class='Modifier'>´¨</span><span class='Paren'>(</span><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Modifier2'>○</span><span class='Paren'>(</span><span class='Function'>↕</span><span class='Modifier2'>∘</span><span class='Function'>≠</span><span class='Paren'>)</span><span class='Function'>≢</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>⊔</span><span class='Value'>i</span></code>.</p>