docs/doc/fold.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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255

<head>
  <link href="../favicon.ico" rel="shortcut icon" type="image/x-icon"/>
  <link href="../style.css" rel="stylesheet"/>
  <title>BQN: Fold and Insert</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="fold-and-insert">Fold and Insert</h1>
<svg viewBox='-184.8 -12 588 288'>
  <g font-size='21px' fill='currentColor' stroke-linecap='round' text-anchor='middle' font-family='BQN,monospace'>
    <rect class='code' stroke-width='1.5' rx='12' x='-128.8' y='0' width='476' height='264'/>
    <g class='lilac' stroke-width='2'>
      <line x1='2.548' y1='46' x2='26.572' y2='178'/>
      <line x1='58.548' y1='46' x2='77.112' y2='148'/>
      <line x1='114.548' y1='46' x2='127.652' y2='118'/>
      <line x1='170.548' y1='46' x2='178.192' y2='88'/>
      <line x1='226.548' y1='46' x2='228.732' y2='58'/>
      <line x1='271.964' y1='46' x2='265.076' y2='58'/>
      <line x1='82.74' y1='176' x2='65.52' y2='185'/>
      <line x1='133.28' y1='146' x2='116.06' y2='155'/>
      <line x1='183.82' y1='116' x2='166.6' y2='125'/>
      <line x1='234.36' y1='86' x2='217.14' y2='95'/>
      <line x1='42' y1='206' x2='42' y2='218'/>
    </g>
    <g text-anchor='end'>
      <text dy='0.32em' x='-61.6' y='32'>𝕩</text>
      <text dy='0.32em' x='-61.6' y='232'><tspan class='Function'>-</tspan><tspan class='Modifier'>´</tspan>𝕩</text>
    </g>
    <text dy='0.32em' x='0' y='32'><tspan class='Number'>2</tspan></text>
    <text dy='0.32em' x='56' y='32'><tspan class='Number'>0</tspan></text>
    <text dy='0.32em' x='112' y='32'><tspan class='Number'>5</tspan></text>
    <text dy='0.32em' x='168' y='32'><tspan class='Number'>3</tspan></text>
    <text dy='0.32em' x='224' y='32'><tspan class='Number'>4</tspan></text>
    <text dy='0.32em' x='280' y='32'><tspan class='Number'>2</tspan></text>
    <text dy='0.32em' x='42' y='232'><tspan class='Number'>6</tspan></text>
    <text dy='0.32em' x='42' y='192'><tspan class='Number'>2</tspan><tspan class='Function'>-</tspan><tspan class='Number'>¯4</tspan></text>
    <text dy='0.32em' x='92.54' y='162'><tspan class='Number'>0</tspan><tspan class='Function'>-</tspan><tspan class='Number'>4</tspan></text>
    <text dy='0.32em' x='143.08' y='132'><tspan class='Number'>5</tspan><tspan class='Function'>-</tspan><tspan class='Number'>1</tspan></text>
    <text dy='0.32em' x='193.62' y='102'><tspan class='Number'>3</tspan><tspan class='Function'>-</tspan><tspan class='Number'>2</tspan></text>
    <text dy='0.32em' x='244.16' y='72'><tspan class='Number'>4</tspan><tspan class='Function'>-</tspan><tspan class='Number'>2</tspan></text>
    <g class='bluegreen' stroke-width='3' style='fill:none' opacity='0.7'><path d='M-22.4 17l-6 15l6 15M302.4 17l6 15l-6 15'/></g>
  </g>
</svg>

<p>The closely related 1-modifiers Fold (<code><span class='Modifier'>´</span></code>) and Insert (<code><span class='Modifier'>˝</span></code>) apply a dyadic operand function <code><span class='Function'>𝔽</span></code> repeatedly between elements or major cells of <code><span class='Value'>𝕩</span></code>. Neither is quite like the APL2-style Reduce operator (<code><span class='Function'>/</span></code> or <code><span class='Value'>⌿</span></code> in APL), although I sometimes use the term &quot;reduction&quot; to mean either Fold or Insert. There are a bunch of other names like &quot;accumulate&quot; and &quot;aggregate&quot; for this class of calculations—I don't know which is best but I know &quot;catamorphism&quot; is worst.</p>
<p>A distinguishing feature of APL-family reductions is that they don't use an initial value, and try to derive an &quot;identity element&quot; from the operand if the argument array is empty. BQN retains this capability but also allows the programmer to supply an initial value as <code><span class='Value'>𝕨</span></code>.</p>
<h2 id="fold">Fold</h2>
<p>As its glyph suggests, Fold is slightly simpler than Insert. The argument <code><span class='Value'>𝕩</span></code> must always be a list, and Fold applies <code><span class='Function'>𝔽</span></code> between elements—always two at a time—of the list to yield a single result value. In this sense, <code><span class='Function'>𝔽</span><span class='Modifier'>´</span></code> removes a layer of <a href="depth.html">depth</a> from <code><span class='Value'>𝕩</span></code>, although it's not necessarily true that the depth of <code><span class='Function'>𝔽</span><span class='Modifier'>´</span><span class='Value'>𝕩</span></code> is less than that of <code><span class='Value'>𝕩</span></code> because the function <code><span class='Function'>𝔽</span></code> might increase depth.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=K8K0IDLigL804oC/M+KAvzEKK8K0IOKfqDLigL80LCAz4oC/MeKfqQ==">↗️</a><pre>    <span class='Function'>+</span><span class='Modifier'>´</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span>
10
    <span class='Function'>+</span><span class='Modifier'>´</span> <span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Separator'>,</span> <span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Bracket'>⟩</span>
⟨ 5 5 ⟩
</pre>
<p>Any function can be used as an operand. With Maximum (<code><span class='Function'>⌈</span></code>) you can find the largest number out of an entire list, and likewise for Minimum (<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=4oyIwrQgMuKAvzTigL8z4oC/MQrijIrCtCAy4oC/NOKAvzPigL8xCsOXwrQgMuKAvzTigL8z4oC/MSAgIyBQcm9kdWN0IGFzIHdlbGw=">↗️</a><pre>    <span class='Function'>⌈</span><span class='Modifier'>´</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span>
4
    <span class='Function'>⌊</span><span class='Modifier'>´</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span>
1
    <span class='Function'>×</span><span class='Modifier'>´</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span>  <span class='Comment'># Product as well
</span>24
</pre>
<p>The <a href="logic.html">logic</a> function And (<code><span class='Function'>∧</span></code>) tests if all elements of a boolean list are 1, while Or (<code><span class='Function'>∨</span></code>) tests if any are 1.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oinwrQgMeKAvzHigL8wCuKIqMK0IDHigL8x4oC/MA==">↗️</a><pre>    <span class='Function'>∧</span><span class='Modifier'>´</span> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>0</span>
0
    <span class='Function'>∨</span><span class='Modifier'>´</span> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>0</span>
1
</pre>
<h3 id="identity-values">Identity values</h3>
<p>Folding over a list of length 1 never calls the operand function: it returns the lone element unchanged.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=IcK0IOKfqOKOiuKfqQ==">↗️</a><pre>    <span class='Function'>!</span><span class='Modifier'>´</span> <span class='Bracket'>⟨</span><span class='Modifier2'>⎊</span><span class='Bracket'>⟩</span>
⎊
</pre>
<p>Folding over a list of two values applies <code><span class='Function'>𝔽</span></code> once, since <code><span class='Function'>𝔽</span></code> is always called on two arguments. But what about zero values? Should <code><span class='Function'>𝔽</span></code> be applied minus one times? Sort of. BQN checks to see if it knows an <em>identity value</em> for the operand function, and returns that, never calling the function. This works for the <a href="arithmetic.html">arithmetic functions</a> we showed above, always returning a single number.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=K8K0IOKfqOKfqSAgIyBBZGQgbm90aGluZyB1cCwgZ2V0IHplcm8K4oyIwrQg4p+o4p+pICAjIFRoZSBzbWFsbGVzdCBudW1iZXIK4oinwrQg4p+o4p+pICAjIEFsbCB0aGUgZWxlbWVudHMgaW4gdGhlIGxpc3QgYXJlIHRydWXigKY=">↗️</a><pre>    <span class='Function'>+</span><span class='Modifier'>´</span> <span class='Bracket'>⟨⟩</span>  <span class='Comment'># Add nothing up, get zero
</span>0
    <span class='Function'>⌈</span><span class='Modifier'>´</span> <span class='Bracket'>⟨⟩</span>  <span class='Comment'># The smallest number
</span>¯∞
    <span class='Function'>∧</span><span class='Modifier'>´</span> <span class='Bracket'>⟨⟩</span>  <span class='Comment'># All the elements in the list are true…
</span>1
</pre>
<p>The full list of identity values Fold has to use is shown below.</p>
<table>
<thead>
<tr>
<th align="right">Id</th>
<th align="center">Fn</th>
<th align="center">Fn</th>
<th align="right">Id</th>
</tr>
</thead>
<tbody>
<tr>
<td align="right"><code><span class='Number'>0</span></code></td>
<td align="center"><code><span class='Function'>+</span></code></td>
<td align="center"><code><span class='Function'>-</span></code></td>
<td align="right"><code><span class='Number'>0</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>1</span></code></td>
<td align="center"><code><span class='Function'>×</span></code></td>
<td align="center"><code><span class='Function'>÷</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>1</span></code></td>
<td align="center"><code><span class='Function'>⋆</span></code></td>
<td align="center"><code><span class='Function'>¬</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>∞</span></code></td>
<td align="center"><code><span class='Function'>⌊</span></code></td>
<td align="center"><code><span class='Function'>⌈</span></code></td>
<td align="right"><code><span class='Number'>¯∞</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>0</span></code></td>
<td align="center"><code><span class='Function'>∨</span></code></td>
<td align="center"><code><span class='Function'>∧</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>0</span></code></td>
<td align="center"><code><span class='Function'>≠</span></code></td>
<td align="center"><code><span class='Function'>=</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>0</span></code></td>
<td align="center"><code><span class='Function'>&gt;</span></code></td>
<td align="center"><code><span class='Function'>≥</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
</tbody>
</table>
<h3 id="right-to-left">Right-to-left</h3>
<p>The functions we've shown so far are associative (ignoring floating point imprecision), meaning it's equally valid to combine elements of the argument list in any order. But it can be useful to fold using a non-associative function. In this case you must know that Fold performs a <em>right fold</em>, starting from the end of the array and working towards the beginning.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4omN4peLPMK0ICJhYmNkIgoKJ2EnIOKJjeKXizwgJ2InIOKJjeKXizwgJ2MnIOKJjeKXizwgJ2QnICAjIEV4cGFuZGVkIGZvcm0=">↗️</a><pre>    <span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'>&lt;</span><span class='Modifier'>´</span> <span class='String'>&quot;abcd&quot;</span>
⟨ 'a' ⟨ 'b' "cd" ⟩ ⟩

    <span class='String'>'a'</span> <span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'>&lt;</span> <span class='String'>'b'</span> <span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'>&lt;</span> <span class='String'>'c'</span> <span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'>&lt;</span> <span class='String'>'d'</span>  <span class='Comment'># Expanded form
</span>⟨ 'a' ⟨ 'b' "cd" ⟩ ⟩
</pre>
<p>Using the <a href="couple.html#coupling-units">pair</a> function <code><span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'>&lt;</span></code> as an operand shows the structure nicely. This fold first pairs the final two characters <code><span class='String'>'c'</span></code> and <code><span class='String'>'d'</span></code>, then pairs <code><span class='String'>'b'</span></code> with that and so on. This matches BQN's right-to-left order of evaluation. More declaratively we might say that each character is paired with the result of folding over everything to its right.</p>
<p>BQN doesn't provide a left Fold (<code><span class='Modifier'>`</span></code> is <a href="scan.html">Scan</a>). However, you can fold from the left by <a href="reverse.html#reverse">reversing</a> (<code><span class='Function'>⌽</span></code>) the argument list and also reversing (<code><span class='Modifier'>˜</span></code>) the operand function's argument order.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4omN4peLPMucwrQg4oy9ICJhYmNkIg==">↗️</a><pre>    <span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'>&lt;</span><span class='Modifier'>˜´</span> <span class='Function'>⌽</span> <span class='String'>&quot;abcd&quot;</span>
⟨ ⟨ "ab" 'c' ⟩ 'd' ⟩
</pre>
<p>One consequence of this ordering is that folding with Minus (<code><span class='Function'>-</span></code>) gives an alternating sum, where the first value is added, the second subtracted, the third added, and so on. Similarly, <code><span class='Function'>÷</span></code> gives an alternating product, with some elements multiplied and some divided.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=LcK0IDMw4oC/MeKAvzIw4oC/MuKAvzEw">↗️</a><pre>    <span class='Function'>-</span><span class='Modifier'>´</span> <span class='Number'>30</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>20</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>10</span>
57
</pre>
<p>The operand <code><span class='Function'>+</span><span class='Modifier2'>⟜</span><span class='Function'>÷</span></code> is a quick way to compute a <a href="https://en.wikipedia.org/wiki/Continued_fraction">continued fraction</a>'s value from a list of numbers. Here are a few terms from the continued fraction for <em>e</em>.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=K+KfnMO3wrQgMuKAvzHigL8y4oC/MeKAvzHigL804oC/MeKAvzE=">↗️</a><pre>    <span class='Function'>+</span><span class='Modifier2'>⟜</span><span class='Function'>÷</span><span class='Modifier'>´</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>1</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><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>1</span>
2.7183098591549295
</pre>
<h3 id="initial-element">Initial element</h3>
<p>When the operand isn't just an arithmetic primitive, folding with no initial element can be dangerous. Even if you know <code><span class='Value'>𝕩</span></code> isn't empty, saving you from an &quot;Identity not found&quot; error, the case with only one element can easily violate expectations. Here's a somewhat silly example of a function meant to merge elements of the argument into a single list (<code><span class='Function'>∾⥊</span><span class='Modifier'>¨</span></code> is a much better way to do this):</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oi+4peL4qWKwrQg4p+oMuKAvzTiiY024oC/OCwiYWJjZCIsMOKfqQoK4oi+4peL4qWKwrQg4p+oMuKAvzTiiY024oC/OCwiYWJjZCLin6kKCuKIvuKXi+KlisK0IOKfqDLigL804omNNuKAvzjin6k=">↗️</a><pre>    <span class='Function'>∾</span><span class='Modifier2'>○</span><span class='Function'>⥊</span><span class='Modifier'>´</span> <span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Function'>≍</span><span class='Number'>6</span><span class='Ligature'>‿</span><span class='Number'>8</span><span class='Separator'>,</span><span class='String'>&quot;abcd&quot;</span><span class='Separator'>,</span><span class='Number'>0</span><span class='Bracket'>⟩</span>
⟨ 2 4 6 8 'a' 'b' 'c' 'd' 0 ⟩

    <span class='Function'>∾</span><span class='Modifier2'>○</span><span class='Function'>⥊</span><span class='Modifier'>´</span> <span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Function'>≍</span><span class='Number'>6</span><span class='Ligature'>‿</span><span class='Number'>8</span><span class='Separator'>,</span><span class='String'>&quot;abcd&quot;</span><span class='Bracket'>⟩</span>
⟨ 2 4 6 8 'a' 'b' 'c' 'd' ⟩

    <span class='Function'>∾</span><span class='Modifier2'>○</span><span class='Function'>⥊</span><span class='Modifier'>´</span> <span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Function'>≍</span><span class='Number'>6</span><span class='Ligature'>‿</span><span class='Number'>8</span><span class='Bracket'>⟩</span>
┌─     
╵ 2 4  
  6 8  
      ┘
</pre>
<p>The result always has rank 1, until the one-element case, when <code><span class='Function'>∾</span><span class='Modifier2'>○</span><span class='Function'>⥊</span></code> is never applied and can't deshape anything. Using Fold with lots of complex operands and no initial element can make a program fragile.</p>
<p>However, it's easy to specify an initial element for Fold: simply pass it as <code><span class='Value'>𝕨</span></code>. Because <code><span class='Value'>𝕨</span></code> behaves like an element of <code><span class='Value'>𝕩</span></code>, it doesn't need to be enclosed and will usually have one smaller depth. For <code><span class='Function'>∾</span><span class='Modifier2'>○</span><span class='Function'>⥊</span></code> the natural starting element for a fold that returns a list is the empty list.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4p+o4p+pIOKIvuKXi+KlisK0IOKfqDLigL804omNNuKAvzjin6k=">↗️</a><pre>    <span class='Bracket'>⟨⟩</span> <span class='Function'>∾</span><span class='Modifier2'>○</span><span class='Function'>⥊</span><span class='Modifier'>´</span> <span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Function'>≍</span><span class='Number'>6</span><span class='Ligature'>‿</span><span class='Number'>8</span><span class='Bracket'>⟩</span>
⟨ 2 4 6 8 ⟩
</pre>
<p>The initial element is used in the first function application, so it behaves as though it's added to the end of the list (<code><span class='Function'>∾</span><span class='Modifier2'>⟜</span><span class='Function'>&lt;</span><span class='Modifier'>˜</span></code> would accomplish this as well).</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ImVuZCIg4oi+4peL4qWKwrQg4p+oInN0YXJ0IiwibWlkZGxlIuKfqQ==">↗️</a><pre>    <span class='String'>&quot;end&quot;</span> <span class='Function'>∾</span><span class='Modifier2'>○</span><span class='Function'>⥊</span><span class='Modifier'>´</span> <span class='Bracket'>⟨</span><span class='String'>&quot;start&quot;</span><span class='Separator'>,</span><span class='String'>&quot;middle&quot;</span><span class='Bracket'>⟩</span>
"startmiddleend"
</pre>
<p>Folding with <code><span class='Value'>𝕨</span></code> never needs to come up with an identity value, and the number of function applications is exactly the length of <code><span class='Value'>𝕩</span></code>. A function <code><span class='Function'>P</span></code> can be applied to each element of <code><span class='Value'>𝕩</span></code> before operating using <code><span class='Value'>𝕨</span><span class='Function'>P</span><span class='Modifier2'>⊸</span><span class='Function'>F</span><span class='Modifier'>´</span><span class='Value'>𝕩</span></code>, which is equivalent to <code><span class='Value'>𝕨</span> <span class='Function'>F</span><span class='Modifier'>´</span> <span class='Function'>P</span><span class='Modifier'>¨</span><span class='Value'>𝕩</span></code> except for the order in which <code><span class='Function'>F</span></code> and <code><span class='Function'>P</span></code> are invoked (if they have side effects).</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=IlNUT1AiIOKMveKKuOKIvsK0ICJBQkNERSLigL8iMDEyIuKAvyJhYmNkIg==">↗️</a><pre>    <span class='String'>&quot;STOP&quot;</span> <span class='Function'>⌽</span><span class='Modifier2'>⊸</span><span class='Function'>∾</span><span class='Modifier'>´</span> <span class='String'>&quot;ABCDE&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;012&quot;</span><span class='Ligature'>‿</span><span class='String'>&quot;abcd&quot;</span>
"EDCBA210dcbaSTOP"
</pre>
<h2 id="insert">Insert</h2>
<p>Fold only works on lists. What if you want to, say, sum the columns of a table?</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIHRhYiDihpAgKDIr4oaVNSkgfOKMnCA5K+KGlTMKCivLnSB0YWI=">↗️</a><pre>    <span class='Function'>⊢</span> <span class='Value'>tab</span> <span class='Gets'>←</span> <span class='Paren'>(</span><span class='Number'>2</span><span class='Function'>+↕</span><span class='Number'>5</span><span class='Paren'>)</span> <span class='Function'>|</span><span class='Modifier'>⌜</span> <span class='Number'>9</span><span class='Function'>+↕</span><span class='Number'>3</span>
┌─       
╵ 1 0 1  
  0 1 2  
  1 2 3  
  4 0 1  
  3 4 5  
        ┘

    <span class='Function'>+</span><span class='Modifier'>˝</span> <span class='Value'>tab</span>
⟨ 9 7 12 ⟩
</pre>
<p>The Insert (<code><span class='Modifier'>˝</span></code>) modifier will do this for you. Because it works on the <a href="leading.html">leading axis</a> of the argument, Insert can be applied to axes other than the first with Rank. Sum each row (second axis) with <code><span class='Modifier'>˘</span></code>, for example.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=K8udy5ggdGFi">↗️</a><pre>    <span class='Function'>+</span><span class='Modifier'>˝˘</span> <span class='Value'>tab</span>
⟨ 2 3 6 5 12 ⟩
</pre>
<p>This case is tricky, because <code><span class='Function'>+</span><span class='Modifier'>´˘</span> <span class='Value'>tab</span></code> yields the same result but is actually unsound—if <code><span class='Value'>tab</span></code> contains arrays then they will be merged together at the end. Remember that if you want to reduce along one axis of an array but get an array of results out, you should use Insert (possibly adding Each to work on elements instead of cells; see <a href="#apl2-reduction">APL2 reduction</a> below).</p>
<p>A function with Insert <code><span class='Function'>𝔽</span><span class='Modifier'>˝</span></code> is nearly equivalent to <code><span class='Function'>𝔽</span><span class='Modifier'>´</span><span class='Function'>&lt;</span><span class='Modifier'>˘</span></code> (and both fail on unit arguments, because there's no axis to apply along). Besides being more convenient, <code><span class='Function'>𝔽</span><span class='Modifier'>˝</span></code> is a little safer because it takes the argument shape into account when returning an identity value:</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=K8K0PMuYIDDigL804qWKMAory50gICAw4oC/NOKlijA=">↗️</a><pre>    <span class='Function'>+</span><span class='Modifier'>´</span><span class='Function'>&lt;</span><span class='Modifier'>˘</span> <span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Function'>⥊</span><span class='Number'>0</span>
0
    <span class='Function'>+</span><span class='Modifier'>˝</span>   <span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Function'>⥊</span><span class='Number'>0</span>
⟨ 0 0 0 0 ⟩
</pre>
<p>Just like Fold, Insert allows an initial element for the left argument, so that you don't need to rely on the interpreter knowing the identity. A more complete translation into Fold is therefore <code><span class='Brace'>{</span><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier'>´</span><span class='Function'>&lt;</span><span class='Modifier'>˘</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code>. The expression below shows that the operand function is called on the last major cell when the identity, then the next-to-last major cell and so on. In total there are <code><span class='Function'>≠</span><span class='Value'>𝕩</span></code> calls, while there would be <code><span class='Number'>1</span><span class='Function'>-</span><span class='Modifier'>˜</span><span class='Function'>≠</span><span class='Value'>𝕩</span></code> without the left argument.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ImlkIiDiiY3il4s8y50gInJvdzAgIuKIviJyb3cxICLiiY0icm93MiAi">↗️</a><pre>    <span class='String'>&quot;id&quot;</span> <span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'>&lt;</span><span class='Modifier'>˝</span> <span class='String'>&quot;row0 &quot;</span><span class='Function'>∾</span><span class='String'>&quot;row1 &quot;</span><span class='Function'>≍</span><span class='String'>&quot;row2 &quot;</span>
┌─                                      
· "row0 " ⟨ "row1 " ⟨ "row2 " "id" ⟩ ⟩  
                                       ┘
</pre>
<p>One trick involving Insert is <code><span class='Function'>∾</span><span class='Modifier'>˝</span></code>, which merges the first two axes of <code><span class='Value'>𝕩</span></code> into one long axis. It even works on empty arrays, because BQN knows that there's only one result shape that makes sense (in contrast to <code><span class='Function'>∾</span><span class='Modifier'>´</span><span class='Bracket'>⟨⟩</span></code>, where many results sometimes work but none of them always work).</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGxldCDihpAgKCJBSFciLSdBJykgK+KMnCAiYUEiICvijJwg4oaVNAoK4oi+y50gbGV0CgriiaIg4oi+y50g4oaVM+KAvzLigL80CgriiaIg4oi+y50g4oaVMOKAvzLigL80ICAjIFRoZSBpZGVudGl0eSBpcyBhbiBlbXB0eSBjZWxs">↗️</a><pre>    <span class='Function'>⊢</span> <span class='Value'>let</span> <span class='Gets'>←</span> <span class='Paren'>(</span><span class='String'>&quot;AHW&quot;</span><span class='Function'>-</span><span class='String'>'A'</span><span class='Paren'>)</span> <span class='Function'>+</span><span class='Modifier'>⌜</span> <span class='String'>&quot;aA&quot;</span> <span class='Function'>+</span><span class='Modifier'>⌜</span> <span class='Function'>↕</span><span class='Number'>4</span>
┌─      
╎"abcd  
  ABCD  
        
 ·hijk  
  HIJK  
        
 ·wxyz  
  WXYZ" 
       ┘

    <span class='Function'>∾</span><span class='Modifier'>˝</span> <span class='Value'>let</span>
┌─      
╵"abcd  
  ABCD  
  hijk  
  HIJK  
  wxyz  
  WXYZ" 
       ┘

    <span class='Function'>≢</span> <span class='Function'>∾</span><span class='Modifier'>˝</span> <span class='Function'>↕</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span>
⟨ 6 4 ⟩

    <span class='Function'>≢</span> <span class='Function'>∾</span><span class='Modifier'>˝</span> <span class='Function'>↕</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>4</span>  <span class='Comment'># The identity is an empty cell
</span>⟨ 0 4 ⟩
</pre>
<p>As a historical note, Insert is named after J's adverb <code><span class='Function'>/</span></code>, which comes from SHARP APL's <code><span class='Value'>⌿</span></code>, reduce-down. In the original APL, only arithmetic reductions were defined, and nested arrays didn't exist—arrays were either all characters or all numbers. SHARP extended them by splitting the array into cells as we've shown. However, there's another interpretation, which is what you'll find in mainstream APLs today…</p>
<h2 id="apl2-reduction">APL2 reduction?</h2>
<p>If you try an expression like <code><span class='Value'>⍪⌿</span></code> in Dyalog APL, you'll get results very different from BQN's <code><span class='Function'>∾</span><span class='Modifier'>˝</span></code>. Instead of combining the cells like we see above, APL applies the function on pairs of <em>elements</em> much like Fold. The difference is that, because reduction happens only along one axis but an array might have other axes, there can be multiple values in the result, so that it will always be an array like the argument. BQN can perform this operation as well: <code><span class='Value'>⍪⌿</span></code> is written <code><span class='Function'>∾</span><span class='Modifier'>¨˝</span></code> in BQN.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oi+wqjLnSB0YWI=">↗️</a><pre>    <span class='Function'>∾</span><span class='Modifier'>¨˝</span> <span class='Value'>tab</span>
⟨ ⟨ 1 0 1 4 3 ⟩ ⟨ 0 1 2 0 4 ⟩ ⟨ 1 2 3 1 5 ⟩ ⟩
</pre>
<p>This kind of reduction has an interesting property that the other two lack: it always removes exacly one axis, so that the result's shape is the argument's major cell shape. When applied to a later axis using the Rank or Cells modifier, it removes that axis instead.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4omiIOKIvsKoy50g4oaVNOKAvzLigL8zICAgIyBSZWR1Y2Ugb3V0IHRoZSBmaXJzdCBheGlzCuKJoiDiiL7CqMudy5gg4oaVNOKAvzLigL8zICAjIFJlZHVjZSBvdXQgdGhlIHNlY29uZA==">↗️</a><pre>    <span class='Function'>≢</span> <span class='Function'>∾</span><span class='Modifier'>¨˝</span> <span class='Function'>↕</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span>   <span class='Comment'># Reduce out the first axis
</span>⟨ 2 3 ⟩
    <span class='Function'>≢</span> <span class='Function'>∾</span><span class='Modifier'>¨˝˘</span> <span class='Function'>↕</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span>  <span class='Comment'># Reduce out the second
</span>⟨ 4 3 ⟩
</pre>
<p>When the operand is an arithmetic function, say <code><span class='Function'>⌊</span></code>, APL2-style reduction is no different from Insert: <code><span class='Function'>⌊</span><span class='Modifier'>¨˝</span></code> is the same as <code><span class='Function'>⌊</span><span class='Modifier'>˝</span></code>, because <code><span class='Function'>⌊</span><span class='Modifier'>¨</span></code> and <code><span class='Function'>⌊</span></code> are the same on arrays. That means that Insert with an arithmetic operand also has this axis-removing property.</p>