diff options
| author | Marshall Lochbaum <mwlochbaum@gmail.com> | 2020-07-21 15:45:25 -0400 |
|---|---|---|
| committer | Marshall Lochbaum <mwlochbaum@gmail.com> | 2020-07-21 15:45:25 -0400 |
| commit | 16022acd45703772f62ca9ed9f8d8ef9288be9b5 (patch) | |
| tree | 96aa748d7dce2f804f9447c55018cd170e4c3751 /docs | |
| parent | 7665fb5a90f783ee5253e71fbdd0573359ca9b88 (diff) | |
Custom array formatting in the markdown converter
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/doc/depth.html | 127 | ||||
| -rw-r--r-- | docs/doc/group.html | 216 | ||||
| -rw-r--r-- | docs/doc/join.html | 31 | ||||
| -rw-r--r-- | docs/doc/logic.html | 18 | ||||
| -rw-r--r-- | docs/doc/prefixes.html | 321 | ||||
| -rw-r--r-- | docs/doc/transpose.html | 64 | ||||
| -rw-r--r-- | docs/doc/windows.html | 63 |
7 files changed, 363 insertions, 477 deletions
diff --git a/docs/doc/depth.html b/docs/doc/depth.html index 92e05dd3..e141585c 100644 --- a/docs/doc/depth.html +++ b/docs/doc/depth.html @@ -64,128 +64,75 @@ </table> <p>Functions such as Take and Drop use a single number per axis. When the left argument is a list of numbers, they apply to initial axes. But for convenience, a single number is also accepted, and applied to the first axis only. This is equivalent to ravelling the left argument before applying the function.</p> <pre> <span class='Function'>≢</span><span class='Number'>2</span><span class='Function'>↑</span><span class='Number'>7</span><span class='Ligature'>‿</span><span class='Number'>7</span><span class='Ligature'>‿</span><span class='Number'>7</span><span class='Ligature'>‿</span><span class='Number'>7</span><span class='Function'>⥊</span><span class='String'>"abc"</span> -2‿7‿7‿7 +⟨ 2 7 7 7 ⟩ <span class='Function'>≢</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='Function'>↑</span><span class='Number'>7</span><span class='Ligature'>‿</span><span class='Number'>7</span><span class='Ligature'>‿</span><span class='Number'>7</span><span class='Ligature'>‿</span><span class='Number'>7</span><span class='Function'>⥊</span><span class='String'>"abc"</span> -2‿1‿1‿7 +⟨ 2 1 1 7 ⟩ </pre> <p>In these cases the flexibility seems trivial because the left argument has depth 1 or 0: it is an array or isn't, and it's obvious what a plain number should do. But for the second row in the table, the left argument is always an array. The general case is that the left argument is a vector and its elements correspond to right argument axes:</p> <pre> <span class='Bracket'>⟨</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Separator'>,</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='Bracket'>⟩</span> <span class='Function'>⊏</span> <span class='Function'>↕</span><span class='Number'>6</span><span class='Ligature'>‿</span><span class='Number'>7</span> -┌───┬───┬───┐ -│3‿1│3‿4│3‿1│ -├───┼───┼───┤ -│2‿1│2‿4│2‿1│ -└───┴───┴───┘ +┌─ +╵ ⟨ 3 1 ⟩ ⟨ 3 4 ⟩ ⟨ 3 1 ⟩ + ⟨ 2 1 ⟩ ⟨ 2 4 ⟩ ⟨ 2 1 ⟩ + ┘ </pre> <p>This means the left argument is homogeneous of depth 2. What should an argument of depth 1, or an argument that contains non-arrays, do? One option is to continue to require the left argument to be a list, and convert any non-array argument into an array by enclosing it:</p> <pre> <span class='Bracket'>⟨</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Separator'>,</span><span class='Number'>1</span><span class='Bracket'>⟩</span> <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='Modifier'>¨</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span> <span class='Function'>↕</span><span class='Number'>6</span><span class='Ligature'>‿</span><span class='Number'>7</span> -┌───┬───┐ -│3‿1│2‿1│ -└───┴───┘ +⟨ ⟨ 3 1 ⟩ ⟨ 2 1 ⟩ ⟩ </pre> <p>While very consistent, this extension represents a small convenience and makes it difficult to act on a single axis, which for Replicate and <a href="group.html">Group</a> is probably the most common way the primitive is used:</p> <pre> <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'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span> <span class='Function'>/</span> <span class='String'>"abcde"</span> -aaabbcddeee +"aaabbcddeee" </pre> <p>With the extension above, every case like this would have to use <code><span class='Function'><</span><span class='Modifier2'>⊸</span><span class='Function'>/</span></code> instead of just <code><span class='Function'>/</span></code>. BQN avoids this difficulty by testing the left argument's depth. A depth-1 argument applies to the first axis only, giving the behavior above.</p> <p>For Select, the depth-1 case is still quite useful, but it may also be desirable to choose a single cell using a list of numbers. In this case the left argument depth can be increased from the bottom using <code><span class='Function'><</span><span class='Modifier'>¨</span></code>.</p> <pre> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>4</span> <span class='Function'><</span><span class='Modifier'>¨</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span> <span class='Function'>↕</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>2</span> -┌───────┬───────┐ -│2‿1‿4‿0│2‿1‿4‿1│ -└───────┴───────┘ +⟨ ⟨ 2 1 4 0 ⟩ ⟨ 2 1 4 1 ⟩ ⟩ </pre> <h2 id="the-depth-modifier">The Depth modifier</h2> <p>The Depth 2-modifier (<code><span class='Modifier2'>⚇</span></code>) is a generalization of Each that allows diving deeper into an array. To illustrate it we'll use a shape <code><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span></code> array of lists of lists.</p> <pre> <span class='Function'>⊢</span> <span class='Value'>n</span> <span class='Gets'>←</span> <span class='Function'><</span><span class='Modifier2'>⎉</span><span class='Number'>1</span><span class='Modifier2'>⍟</span><span class='Number'>2</span> <span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊↕</span><span class='Number'>48</span> -┌─────────────┬─────────────┬─────────────┐ -│┌───┬───┐ │┌───┬───┐ │┌───┬─────┐ │ -││0‿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││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -└─────────────┴─────────────┴─────────────┘ +┌─ +╵ ⟨ ⟨ 0 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 ⟩ ⟩ + ┘ <span class='Function'>≡</span> <span class='Value'>n</span> 3 </pre> <p>Reversing n swaps all the rows:</p> <pre> <span class='Function'>⌽</span> <span class='Value'>n</span> -┌─────────────┬─────────────┬─────────────┐ -│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│ -││36‿37│38‿39│││40‿41│42‿43│││44‿45│46‿47││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -├─────────────┼─────────────┼─────────────┤ -│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│ -││24‿25│26‿27│││28‿29│30‿31│││32‿33│34‿35││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -├─────────────┼─────────────┼─────────────┤ -│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│ -││12‿13│14‿15│││16‿17│18‿19│││20‿21│22‿23││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -├─────────────┼─────────────┼─────────────┤ -│┌───┬───┐ │┌───┬───┐ │┌───┬─────┐ │ -││0‿1│2‿3│ ││4‿5│6‿7│ ││8‿9│10‿11│ │ -│└───┴───┘ │└───┴───┘ │└───┴─────┘ │ -└─────────────┴─────────────┴─────────────┘ +┌─ +╵ ⟨ ⟨ 36 37 ⟩ ⟨ 38 39 ⟩ ⟩ ⟨ ⟨ 40 41 ⟩ ⟨ 42 43 ⟩ ⟩ ⟨ ⟨ 44 45 ⟩ ⟨ 46 47 ⟩ ⟩ + ⟨ ⟨ 24 25 ⟩ ⟨ 26 27 ⟩ ⟩ ⟨ ⟨ 28 29 ⟩ ⟨ 30 31 ⟩ ⟩ ⟨ ⟨ 32 33 ⟩ ⟨ 34 35 ⟩ ⟩ + ⟨ ⟨ 12 13 ⟩ ⟨ 14 15 ⟩ ⟩ ⟨ ⟨ 16 17 ⟩ ⟨ 18 19 ⟩ ⟩ ⟨ ⟨ 20 21 ⟩ ⟨ 22 23 ⟩ ⟩ + ⟨ ⟨ 0 1 ⟩ ⟨ 2 3 ⟩ ⟩ ⟨ ⟨ 4 5 ⟩ ⟨ 6 7 ⟩ ⟩ ⟨ ⟨ 8 9 ⟩ ⟨ 10 11 ⟩ ⟩ + ┘ </pre> <p>Depth <code><span class='Number'>¯1</span></code> is equivalent to Each, and reverses the larger vectors, while depth <code><span class='Number'>¯2</span></code> applies Each twice to reverse the smaller vectors:</p> <pre> <span class='Function'>⌽</span><span class='Modifier2'>⚇</span><span class='Number'>¯1</span> <span class='Value'>n</span> -┌─────────────┬─────────────┬─────────────┐ -│┌───┬───┐ │┌───┬───┐ │┌─────┬───┐ │ -││2‿3│0‿1│ ││6‿7│4‿5│ ││10‿11│8‿9│ │ -│└───┴───┘ │└───┴───┘ │└─────┴───┘ │ -├─────────────┼─────────────┼─────────────┤ -│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│ -││14‿15│12‿13│││18‿19│16‿17│││22‿23│20‿21││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -├─────────────┼─────────────┼─────────────┤ -│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│ -││26‿27│24‿25│││30‿31│28‿29│││34‿35│32‿33││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -├─────────────┼─────────────┼─────────────┤ -│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│ -││38‿39│36‿37│││42‿43│40‿41│││46‿47│44‿45││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -└─────────────┴─────────────┴─────────────┘ +┌─ +╵ ⟨ ⟨ 2 3 ⟩ ⟨ 0 1 ⟩ ⟩ ⟨ ⟨ 6 7 ⟩ ⟨ 4 5 ⟩ ⟩ ⟨ ⟨ 10 11 ⟩ ⟨ 8 9 ⟩ ⟩ + ⟨ ⟨ 14 15 ⟩ ⟨ 12 13 ⟩ ⟩ ⟨ ⟨ 18 19 ⟩ ⟨ 16 17 ⟩ ⟩ ⟨ ⟨ 22 23 ⟩ ⟨ 20 21 ⟩ ⟩ + ⟨ ⟨ 26 27 ⟩ ⟨ 24 25 ⟩ ⟩ ⟨ ⟨ 30 31 ⟩ ⟨ 28 29 ⟩ ⟩ ⟨ ⟨ 34 35 ⟩ ⟨ 32 33 ⟩ ⟩ + ⟨ ⟨ 38 39 ⟩ ⟨ 36 37 ⟩ ⟩ ⟨ ⟨ 42 43 ⟩ ⟨ 40 41 ⟩ ⟩ ⟨ ⟨ 46 47 ⟩ ⟨ 44 45 ⟩ ⟩ + ┘ <span class='Function'>⌽</span><span class='Modifier2'>⚇</span><span class='Number'>¯2</span> <span class='Value'>n</span> -┌─────────────┬─────────────┬─────────────┐ -│┌───┬───┐ │┌───┬───┐ │┌───┬─────┐ │ -││1‿0│3‿2│ ││5‿4│7‿6│ ││9‿8│11‿10│ │ -│└───┴───┘ │└───┴───┘ │└───┴─────┘ │ -├─────────────┼─────────────┼─────────────┤ -│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│ -││13‿12│15‿14│││17‿16│19‿18│││21‿20│23‿22││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -├─────────────┼─────────────┼─────────────┤ -│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│ -││25‿24│27‿26│││29‿28│31‿30│││33‿32│35‿34││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -├─────────────┼─────────────┼─────────────┤ -│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│ -││37‿36│39‿38│││41‿40│43‿42│││45‿44│47‿46││ -│└─────┴─────┘│└─────┴─────┘│└─────┴─────┘│ -└─────────────┴─────────────┴─────────────┘ +┌─ +╵ ⟨ ⟨ 1 0 ⟩ ⟨ 3 2 ⟩ ⟩ ⟨ ⟨ 5 4 ⟩ ⟨ 7 6 ⟩ ⟩ ⟨ ⟨ 9 8 ⟩ ⟨ 11 10 ⟩ ⟩ + ⟨ ⟨ 13 12 ⟩ ⟨ 15 14 ⟩ ⟩ ⟨ ⟨ 17 16 ⟩ ⟨ 19 18 ⟩ ⟩ ⟨ ⟨ 21 20 ⟩ ⟨ 23 22 ⟩ ⟩ + ⟨ ⟨ 25 24 ⟩ ⟨ 27 26 ⟩ ⟩ ⟨ ⟨ 29 28 ⟩ ⟨ 31 30 ⟩ ⟩ ⟨ ⟨ 33 32 ⟩ ⟨ 35 34 ⟩ ⟩ + ⟨ ⟨ 37 36 ⟩ ⟨ 39 38 ⟩ ⟩ ⟨ ⟨ 41 40 ⟩ ⟨ 43 42 ⟩ ⟩ ⟨ ⟨ 45 44 ⟩ ⟨ 47 46 ⟩ ⟩ + ┘ </pre> <p>While a negative depth tells how many levels to go down, a non-negative depth gives the maximum depth of the argument before applying the left operand. On a depth-3 array like above, depth <code><span class='Number'>2</span></code> is equivalent to <code><span class='Number'>¯1</span></code> and depth <code><span class='Number'>1</span></code> is equivalent to <code><span class='Number'>¯2</span></code>. A depth of <code><span class='Number'>0</span></code> means to loop until non-arrays are reached, that is, apply <a href="https://aplwiki.com/wiki/Pervasion">pervasively</a>, like a scalar function.</p> <pre> <span class='Bracket'>⟨</span><span class='String'>'a'</span><span class='Separator'>,</span><span class='String'>"bc"</span><span class='Bracket'>⟩</span> <span class='Function'>≍</span><span class='Modifier2'>⚇</span><span class='Number'>0</span> <span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Separator'>,</span><span class='Number'>4</span><span class='Bracket'>⟩</span> -┌─────────────┬─────────────┐ -│┌─────┬─────┐│┌─────┬─────┐│ -││'a'‿2│'a'‿3│││'b'‿4│'c'‿4││ -│└─────┴─────┘│└─────┴─────┘│ -└─────────────┴─────────────┘ +┌─ +· ⟨ ⟨ 'a' 2 ⟩ ⟨ 'a' 3 ⟩ ⟩ ⟨ ⟨ 'b' 4 ⟩ ⟨ 'c' 4 ⟩ ⟩ + ┘ </pre> <p>With a positive operand, Depth doesn't have to use the same depth everywhere. Here, Length is applied as soon as the depth for a particular element is 1 or less, including if the argument has depth 0. For example, it maps over <code><span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Separator'>,</span><span class='Bracket'>⟨</span><span class='Number'>3</span><span class='Separator'>,</span><span class='Number'>4</span><span class='Bracket'>⟩⟩</span></code>, but not over <code><span class='Bracket'>⟨</span><span class='Number'>11</span><span class='Separator'>,</span><span class='Number'>12</span><span class='Bracket'>⟩</span></code>, even though these are elements of the same array.</p> <pre> <span class='Function'>≠</span><span class='Modifier2'>⚇</span><span class='Number'>1</span> <span class='Bracket'>⟨</span><span class='Number'>1</span><span class='Separator'>,</span><span class='Bracket'>⟨</span><span class='Number'>2</span><span class='Separator'>,</span><span class='Bracket'>⟨</span><span class='Number'>3</span><span class='Separator'>,</span><span class='Number'>4</span><span class='Bracket'>⟩⟩</span><span class='Separator'>,</span><span class='Bracket'>⟨</span><span class='Number'>5</span><span class='Separator'>,</span><span class='Bracket'>⟨</span><span class='Number'>6</span><span class='Separator'>,</span><span class='Number'>7</span><span class='Bracket'>⟩</span><span class='Separator'>,</span><span class='Bracket'>⟨</span><span class='Number'>8</span><span class='Separator'>,</span><span class='Number'>9</span><span class='Separator'>,</span><span class='Number'>10</span><span class='Bracket'>⟩⟩</span><span class='Separator'>,</span><span class='Bracket'>⟨</span><span class='Number'>11</span><span class='Separator'>,</span><span class='Number'>12</span><span class='Bracket'>⟩⟩</span> -┌─┬───┬─────┬─┐ -│1│1‿2│1‿2‿3│2│ -└─┴───┴─────┴─┘ +⟨ 1 ⟨ 1 2 ⟩ ⟨ 1 2 3 ⟩ 2 ⟩ </pre> diff --git a/docs/doc/group.html b/docs/doc/group.html index 88e02f29..590b166b 100644 --- a/docs/doc/group.html +++ b/docs/doc/group.html @@ -9,115 +9,84 @@ <h2 id="definition">Definition</h2> <p>Group operates on a numeric list of indices and an array, treated as a list of its major cells or "values", to produce a list of groups, each of which is a selection from those cells. The two arrays have the same length, and each value cell is paired with the index at the same position. That index indicates the result group the cell should go into, with an "index" of ¯1 indicating that it should be dropped and not appear in the result.</p> <pre> <span class='Number'>0</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'>0</span><span class='Ligature'>‿</span><span class='Number'>1</span> <span class='Function'>≍</span> <span class='String'>"abcde"</span> <span class='Comment'># Corresponding indices and values -</span>0 1 2 0 1 -a b c d e +</span>┌─ +╵ 0 1 2 0 1 + 'a' 'b' 'c' 'd' 'e' + ┘ <span class='Number'>0</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'>0</span><span class='Ligature'>‿</span><span class='Number'>1</span> <span class='Function'>⊔</span> <span class='String'>"abcde"</span> <span class='Comment'># Values grouped by index -</span>┌──┬──┬─┐ -│ad│be│c│ -└──┴──┴─┘ +</span>⟨ "ad" "be" "c" ⟩ </pre> <p>For example, we might choose to group a list of words by length. Within each group, cells maintain the ordering they had in the list originally.</p> <pre> <span class='Value'>phrase</span> <span class='Gets'>←</span> <span class='String'>"BQN"</span><span class='Ligature'>‿</span><span class='String'>"uses"</span><span class='Ligature'>‿</span><span class='String'>"notation"</span><span class='Ligature'>‿</span><span class='String'>"as"</span><span class='Ligature'>‿</span><span class='String'>"a"</span><span class='Ligature'>‿</span><span class='String'>"tool"</span><span class='Ligature'>‿</span><span class='String'>"of"</span><span class='Ligature'>‿</span><span class='String'>"thought"</span> <span class='Function'>⥊</span><span class='Modifier'>˘</span> <span class='Function'>≠</span><span class='Modifier'>¨</span><span class='Modifier2'>⊸</span><span class='Function'>⊔</span> <span class='Value'>phrase</span> -┌───────────┐ -│⟨⟩ │ -├───────────┤ -│┌─┐ │ -││a│ │ -│└─┘ │ -├───────────┤ -│┌──┬──┐ │ -││as│of│ │ -│└──┴──┘ │ -├───────────┤ -│┌───┐ │ -││BQN│ │ -│└───┘ │ -├───────────┤ -│┌────┬────┐│ -││uses│tool││ -│└────┴────┘│ -├───────────┤ -│⟨⟩ │ -├───────────┤ -│⟨⟩ │ -├───────────┤ -│┌───────┐ │ -││thought│ │ -│└───────┘ │ -├───────────┤ -│┌────────┐ │ -││notation│ │ -│└────────┘ │ -└───────────┘ +┌─ +╵ ⟨⟩ + ⟨ "a" ⟩ + ⟨ "as" "of" ⟩ + ⟨ "BQN" ⟩ + ⟨ "uses" "tool" ⟩ + ⟨⟩ + ⟨⟩ + ⟨ "thought" ⟩ + ⟨ "notation" ⟩ + ┘ </pre> <p>(Could we define <code><span class='Value'>phrase</span></code> more easily? See <a href="#partitioning">below</a>.)</p> <p>If we'd like to ignore words of 0 letters, or more than 5, we can set all word lengths greater than 5 to 0, then reduce the lengths by 1. Two words end up with left argument values of ¯1 and are omitted from the result.</p> <pre> <span class='Number'>1</span> <span class='Function'>-</span><span class='Modifier'>˜</span> <span class='Function'>≤</span><span class='Modifier2'>⟜</span><span class='Number'>5</span><span class='Modifier2'>⊸</span><span class='Function'>×</span> <span class='Function'>≠</span><span class='Modifier'>¨</span> <span class='Value'>phrase</span> -2‿3‿¯1‿1‿0‿3‿1‿¯1 +⟨ 2 3 ¯1 1 0 3 1 ¯1 ⟩ <span class='Function'>⥊</span><span class='Modifier'>˘</span> <span class='Brace'>{</span><span class='Number'>1</span><span class='Function'>-</span><span class='Modifier'>˜</span><span class='Function'>≤</span><span class='Modifier2'>⟜</span><span class='Number'>5</span><span class='Modifier2'>⊸</span><span class='Function'>×≠</span><span class='Modifier'>¨</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Modifier2'>⊸</span><span class='Function'>⊔</span> <span class='Value'>phrase</span> -┌───────────┐ -│┌─┐ │ -││a│ │ -│└─┘ │ -├───────────┤ -│┌──┬──┐ │ -││as│of│ │ -│└──┴──┘ │ -├───────────┤ -│┌───┐ │ -││BQN│ │ -│└───┘ │ -├───────────┤ -│┌────┬────┐│ -││uses│tool││ -│└────┴────┘│ -└───────────┘ +┌─ +╵ ⟨ "a" ⟩ + ⟨ "as" "of" ⟩ + ⟨ "BQN" ⟩ + ⟨ "uses" "tool" ⟩ + ┘ </pre> <p>Note that the length of the result is determined by the largest index. So the result never includes trailing empty groups. A reader of the above code might expect 5 groups (lengths 1 through 5), but there are no words of length 5, so the last group isn't there.</p> <p>When Group is called dyadically, the left argument is used for the indices and the right is used for values, as seen above. When it is called monadically, the right argument, which must be a list, gives the indices and the values grouped are the right argument's indices, that is, <code><span class='Function'>↕≠</span><span class='Value'>𝕩</span></code>.</p> <pre> <span class='Function'>⥊</span><span class='Modifier'>˘</span> <span class='Function'>⊔</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>¯1</span><span class='Ligature'>‿</span><span class='Number'>2</span> -┌───┐ -│⟨⟩ │ -├───┤ -│⟨⟩ │ -├───┤ -│0‿3│ -├───┤ -│⟨1⟩│ -└───┘ +┌─ +╵ ⟨⟩ + ⟨⟩ + ⟨ 0 3 ⟩ + ⟨ 1 ⟩ + ┘ </pre> <p>Here, the index 2 appears at indices 0 and 3 while the index 3 appears at index 1.</p> <h3 id="multidimensional-grouping">Multidimensional grouping</h3> <p>Dyadic Group allows the right argument to be grouped along multiple axes by using a nested left argument. In this case, the left argument must be a list of numeric lists, and the result has rank <code><span class='Function'>≠</span><span class='Value'>𝕨</span></code> while its elements—as always—have the same rank as <code><span class='Value'>𝕩</span></code>. The result shape is <code><span class='Number'>1</span><span class='Function'>+⌈</span><span class='Modifier'>´¨</span><span class='Value'>𝕨</span></code>, while the shape of element <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code> is <code><span class='Value'>i</span><span class='Function'>+</span><span class='Modifier'>´</span><span class='Modifier2'>∘</span><span class='Function'>=</span><span class='Modifier'>¨</span><span class='Value'>𝕨</span></code>. If every element of <code><span class='Value'>𝕨</span></code> is sorted ascending and contains only non-negative numbers, we have <code><span class='Value'>𝕩</span><span class='Function'>≡∾</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code>, that is, Join is the inverse of Partition.</p> <p>Here we split up a rank-2 array into a rank-2 array of rank-2 arrays. Along the first axis we simply separate the first pair and second pair of rows—a partition. Along the second axis we separate odd from even indices.</p> <pre> <span class='Bracket'>⟨</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Separator'>,</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='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='Ligature'>‿</span><span class='Number'>0</span><span class='Bracket'>⟩</span><span class='Function'>⊔</span><span class='Paren'>(</span><span class='Number'>10</span><span class='Function'>×↕</span><span class='Number'>4</span><span class='Paren'>)</span><span class='Function'>+</span><span class='Modifier'>⌜</span><span class='Function'>↕</span><span class='Number'>7</span> -┌───────────┬────────┐ -│ 0 2 4 6│ 1 3 5│ -│10 12 14 16│11 13 15│ -├───────────┼────────┤ -│20 22 24 26│21 23 25│ -│30 32 34 36│31 33 35│ -└───────────┴────────┘ +┌─ +╵ ┌─ ┌─ + ╵ 0 2 4 6 ╵ 1 3 5 + 10 12 14 16 11 13 15 + ┘ ┘ + ┌─ ┌─ + ╵ 20 22 24 26 ╵ 21 23 25 + 30 32 34 36 31 33 35 + ┘ ┘ + ┘ </pre> <p>Each group <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code> is composed of the cells <code><span class='Value'>j</span><span class='Function'><</span><span class='Modifier'>¨</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code> such that <code><span class='Value'>i</span><span class='Function'>≢</span><span class='Value'>j</span><span class='Function'>⊑</span><span class='Modifier'>¨</span><span class='Value'>𝕨</span></code>. The groups retain their array structure and ordering along each argument axis. Using multidimensional Replicate we can say that <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code> is <code><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>=</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Function'>/</span><span class='Value'>𝕩</span></code>.</p> <p>The monadic case works similarly: Group Indices always satisfies <code><span class='Function'>⊔</span><span class='Value'>𝕩</span> <span class='Gets'>←→</span> <span class='Value'>𝕩</span><span class='Function'>⊔↕≠</span><span class='Modifier2'>⚇</span><span class='Number'>1</span><span class='Value'>𝕩</span></code>. As with <code><span class='Function'>↕</span></code>, the depth of the result of Group Indices is always one greater than that of its argument. A depth-0 argument is not allowed.</p> <h2 id="properties">Properties</h2> <p>Group is closely related to the inverse of Indices, <code><span class='Function'>/</span><span class='Modifier'>⁼</span></code>. In fact, inverse Indices called on the index argument gives the length of each group:</p> <pre> <span class='Function'>≠</span><span class='Modifier'>¨</span><span class='Function'>⊔</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>2</span> -0‿1‿2‿1 +⟨ 0 1 2 1 ⟩ <span class='Function'>/</span><span class='Modifier'>⁼</span><span class='Function'>∧</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>2</span> -0‿1‿2‿1 +⟨ 0 1 2 1 ⟩ </pre> <p>A related fact is that calling Indices on the result of Group sorts all the indices passed to Group (removing any ¯1s). This is a kind of counting sort.</p> <pre> <span class='Function'>/≠</span><span class='Modifier'>¨</span><span class='Function'>⊔</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</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'>2</span> -1‿2‿2‿3 +⟨ 1 2 2 3 ⟩ </pre> <p>Called dyadically, Group sorts the right argument according to the left and adds some extra structure. If this structure is removed with Join, Group can be thought of as a kind of sorting.</p> <pre> <span class='Function'>∾</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</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'>2</span> <span class='Function'>⊔</span> <span class='String'>"abcde"</span> -caeb +"caeb" <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</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'>2</span> <span class='Brace'>{</span><span class='Function'>F</span><span class='Gets'>←</span><span class='Paren'>(</span><span class='Number'>0</span><span class='Function'>≤</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>/</span> <span class='Separator'>⋄</span> <span class='Value'>𝕨</span><span class='Function'>⍋</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span><span class='Modifier2'>○</span><span class='Function'>F</span><span class='Value'>𝕩</span><span class='Brace'>}</span> <span class='String'>"abcde"</span> -caeb +"caeb" </pre> <p>Group can even be implemented with the same techniques as a bucket sort, which can be branchless and fast.</p> <h2 id="applications">Applications</h2> @@ -125,94 +94,61 @@ caeb <pre> <span class='Value'>ln</span> <span class='Gets'>←</span> <span class='String'>"Phelps"</span><span class='Ligature'>‿</span><span class='String'>"Latynina"</span><span class='Ligature'>‿</span><span class='String'>"Bjørgen"</span><span class='Ligature'>‿</span><span class='String'>"Andrianov"</span><span class='Ligature'>‿</span><span class='String'>"Bjørndalen"</span> <span class='Value'>co</span> <span class='Gets'>←</span> <span class='String'>"US"</span> <span class='Ligature'>‿</span><span class='String'>"SU"</span> <span class='Ligature'>‿</span><span class='String'>"NO"</span> <span class='Ligature'>‿</span><span class='String'>"SU"</span> <span class='Ligature'>‿</span><span class='String'>"NO"</span> <span class='Function'>⥊</span><span class='Modifier'>˘</span> <span class='Value'>co</span> <span class='Function'>⍷</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span><span class='Modifier2'>⊸</span><span class='Function'>⊔</span> <span class='Value'>ln</span> -┌────────────────────┐ -│┌──────┐ │ -││Phelps│ │ -│└──────┘ │ -├────────────────────┤ -│┌────────┬─────────┐│ -││Latynina│Andrianov││ -│└────────┴─────────┘│ -├────────────────────┤ -│┌───────┬──────────┐│ -││Bjørgen│Bjørndalen││ -│└───────┴──────────┘│ -└────────────────────┘ +┌─ +╵ ⟨ "Phelps" ⟩ + ⟨ "Latynina" "Andrianov" ⟩ + ⟨ "Bjørgen" "Bjørndalen" ⟩ + ┘ </pre> <p>If we would like a particular index to key correspondence, we can use a fixed left argument to Index Of.</p> <pre> <span class='Value'>countries</span> <span class='Gets'>←</span> <span class='String'>"IT"</span><span class='Ligature'>‿</span><span class='String'>"JP"</span><span class='Ligature'>‿</span><span class='String'>"NO"</span><span class='Ligature'>‿</span><span class='String'>"SU"</span><span class='Ligature'>‿</span><span class='String'>"US"</span> <span class='Value'>countries</span> <span class='Function'>∾</span><span class='Modifier'>˘</span> <span class='Value'>co</span> <span class='Value'>countries</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span><span class='Modifier2'>⊸</span><span class='Function'>⊔</span> <span class='Value'>ln</span> -┌──┬────────────────────┐ -│IT│⟨⟩ │ -├──┼────────────────────┤ -│JP│⟨⟩ │ -├──┼────────────────────┤ -│NO│┌───────┬──────────┐│ -│ ││Bjørgen│Bjørndalen││ -│ │└───────┴──────────┘│ -├──┼────────────────────┤ -│SU│┌────────┬─────────┐│ -│ ││Latynina│Andrianov││ -│ │└────────┴─────────┘│ -├──┼────────────────────┤ -│US│┌──────┐ │ -│ ││Phelps│ │ -│ │└──────┘ │ -└──┴────────────────────┘ +┌─ +╵ "IT" ⟨⟩ + "JP" ⟨⟩ + "NO" ⟨ "Bjørgen" "Bjørndalen" ⟩ + "SU" ⟨ "Latynina" "Andrianov" ⟩ + "US" ⟨ "Phelps" ⟩ + ┘ </pre> <p>However, this solution will fail if there are trailing keys with no values. To force the result to have a particular length you can append that length as a dummy index to each argument, then remove the last group after grouping.</p> <pre> <span class='Value'>countries</span> <span class='Gets'>↩</span> <span class='String'>"IT"</span><span class='Ligature'>‿</span><span class='String'>"JP"</span><span class='Ligature'>‿</span><span class='String'>"NO"</span><span class='Ligature'>‿</span><span class='String'>"SU"</span><span class='Ligature'>‿</span><span class='String'>"US"</span><span class='Ligature'>‿</span><span class='String'>"ZW"</span> <span class='Value'>countries</span> <span class='Function'>∾</span><span class='Modifier'>˘</span> <span class='Value'>co</span> <span class='Value'>countries</span><span class='Brace'>{</span><span class='Value'>𝕗</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span><span class='Modifier2'>⊸</span><span class='Paren'>(</span><span class='Number'>¯1</span><span class='Function'>↓⊔</span><span class='Modifier2'>○</span><span class='Paren'>(</span><span class='Function'>∾</span><span class='Modifier2'>⟜</span><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕗</span><span class='Paren'>)))</span><span class='Brace'>}</span> <span class='Value'>ln</span> -┌──┬────────────────────┐ -│IT│⟨⟩ │ -├──┼────────────────────┤ -│JP│⟨⟩ │ -├──┼────────────────────┤ -│NO│┌───────┬──────────┐│ -│ ││Bjørgen│Bjørndalen││ -│ │└───────┴──────────┘│ -├──┼────────────────────┤ -│SU│┌────────┬─────────┐│ -│ ││Latynina│Andrianov││ -│ │└────────┴─────────┘│ -├──┼────────────────────┤ -│US│┌──────┐ │ -│ ││Phelps│ │ -│ │└──────┘ │ -├──┼────────────────────┤ -│ZW│⟨⟩ │ -└──┴────────────────────┘ +┌─ +╵ "IT" ⟨⟩ + "JP" ⟨⟩ + "NO" ⟨ "Bjørgen" "Bjørndalen" ⟩ + "SU" ⟨ "Latynina" "Andrianov" ⟩ + "US" ⟨ "Phelps" ⟩ + "ZW" ⟨⟩ + ┘ </pre> <h3 id="partitioning">Partitioning</h3> <p>In examples we have been using a list of strings stranded together. Often it's more convenient to write the string with spaces, and split it up as part of the code. In this case, the index corresponding to each word (that is, each letter in the word) is the number of spaces before it. We can get this number of spaces from a prefix sum on the boolean list which is 1 at each space.</p> <pre> <span class='String'>' '</span><span class='Paren'>(</span><span class='Function'>+</span><span class='Modifier'>`</span><span class='Modifier2'>∘</span><span class='Function'>=⊔⊢</span><span class='Paren'>)</span><span class='String'>"BQN uses notation as a tool of thought"</span> -┌───┬─────┬─────────┬───┬──┬─────┬───┬────────┐ -│BQN│ uses│ notation│ as│ a│ tool│ of│ thought│ -└───┴─────┴─────────┴───┴──┴─────┴───┴────────┘ +⟨ "BQN" " uses" " notation" " as" " a" " tool" " of" " thought" ⟩ </pre> <p>To avoid including spaces in the result, we should change the result index at each space to ¯1. Here is one way to do that:</p> <pre> <span class='String'>' '</span><span class='Paren'>((</span><span class='Function'>⊢-</span><span class='Modifier'>˜</span><span class='Function'>¬×+</span><span class='Modifier'>`</span><span class='Paren'>)</span><span class='Modifier2'>∘</span><span class='Function'>=⊔⊢</span><span class='Paren'>)</span><span class='String'>"BQN uses notation as a tool of thought"</span> -┌───┬────┬────────┬──┬─┬────┬──┬───────┐ -│BQN│uses│notation│as│a│tool│of│thought│ -└───┴────┴────────┴──┴─┴────┴──┴───────┘ +⟨ "BQN" "uses" "notation" "as" "a" "tool" "of" "thought" ⟩ </pre> <p>A function with structural Under, such as <code><span class='Brace'>{</span><span class='Number'>¯1</span><span class='Modifier'>¨</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Value'>𝕩</span><span class='Modifier2'>⊸</span><span class='Function'>/</span><span class='Paren'>)</span><span class='Function'>+</span><span class='Modifier'>`</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code>, would also work.</p> <p>In other cases, we might want to split on spaces, so that words are separated by any number of spaces, and extra spaces don't affect the output. Currently our function makes a new word with each space:</p> <pre> <span class='String'>' '</span><span class='Paren'>((</span><span class='Function'>⊢-</span><span class='Modifier'>˜</span><span class='Function'>¬×+</span><span class='Modifier'>`</span><span class='Paren'>)</span><span class='Modifier2'>∘</span><span class='Function'>=⊔⊢</span><span class='Paren'>)</span><span class='String'>" string with spaces "</span> -┌──┬──┬──────┬────┬──┬──────┐ -│⟨⟩│⟨⟩│string│with│⟨⟩│spaces│ -└──┴──┴──────┴────┴──┴──────┘ +⟨ ⟨⟩ ⟨⟩ "string" "with" ⟨⟩ "spaces" ⟩ </pre> <p>However, trailing spaces are ignored because Group never produces trailing empty groups (to get them back we would use a dummy final character in the string). To avoid empty words, we should increase the word index only once per group of spaces. We can do this by taking the prefix sum of a list that is 1 only for a space with no space before it. To make such a list, we can use the <a href="windows.html">Windows</a> function. We will extend our list with an initial 1 so that leading spaces will be ignored. Then we take windows of the same length as the original list: the first includes the dummy argument followed by a shifted copy of the list, and the second is the original list. These represent whether the previous and current characters are spaces; we want positions where the previous wasn't a space and the current is.</p> <pre> <span class='Function'>≍</span><span class='Modifier2'>⟜</span><span class='Paren'>((</span><span class='Function'><</span><span class='Modifier'>´</span><span class='Function'><</span><span class='Modifier'>˘</span><span class='Paren'>)</span><span class='Function'>≠↕</span><span class='Number'>1</span><span class='Function'>∾⊢</span><span class='Paren'>)</span> <span class='String'>' '</span><span class='Function'>=</span><span class='String'>" string with spaces "</span> <span class='Comment'># All, then filtered, spaces -</span>1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 -0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 +</span>┌─ +╵ 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 + 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 + ┘ <span class='Function'>≍</span><span class='Modifier2'>⟜</span><span class='Paren'>(</span><span class='Function'>⊢-</span><span class='Modifier'>˜</span><span class='Function'>¬×+</span><span class='Modifier'>`</span><span class='Modifier2'>∘</span><span class='Paren'>((</span><span class='Function'><</span><span class='Modifier'>´</span><span class='Function'><</span><span class='Modifier'>˘</span><span class='Paren'>)</span><span class='Function'>≠↕</span><span class='Number'>1</span><span class='Function'>∾⊢</span><span class='Paren'>))</span><span class='String'>' '</span><span class='Function'>=</span><span class='String'>" string with spaces "</span> <span class='Comment'># More processing -</span> 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 -¯1 ¯1 0 0 0 0 0 0 ¯1 1 1 1 1 ¯1 ¯1 2 2 2 2 2 2 ¯1 ¯1 ¯1 +</span>┌─ +╵ 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 + ¯1 ¯1 0 0 0 0 0 0 ¯1 1 1 1 1 ¯1 ¯1 2 2 2 2 2 2 ¯1 ¯1 ¯1 + ┘ <span class='String'>' '</span><span class='Paren'>((</span><span class='Function'>⊢-</span><span class='Modifier'>˜</span><span class='Function'>¬×+</span><span class='Modifier'>`</span><span class='Modifier2'>∘</span><span class='Paren'>((</span><span class='Function'><</span><span class='Modifier'>´</span><span class='Function'><</span><span class='Modifier'>˘</span><span class='Paren'>)</span><span class='Function'>≠↕</span><span class='Number'>1</span><span class='Function'>∾⊢</span><span class='Paren'>))</span><span class='Modifier2'>∘</span><span class='Function'>=⊔⊢</span><span class='Paren'>)</span><span class='String'>" string with spaces "</span> <span class='Comment'># Final result -</span>┌──────┬────┬──────┐ -│string│with│spaces│ -└──────┴────┴──────┘ +</span>⟨ "string" "with" "spaces" ⟩ </pre> diff --git a/docs/doc/join.html b/docs/doc/join.html index b6ac1ace..f6edc533 100644 --- a/docs/doc/join.html +++ b/docs/doc/join.html @@ -4,11 +4,11 @@ <p>Join (<code><span class='Function'>∾</span></code>) is an extension of the monadic function <a href="https://aplwiki.com/wiki/Raze">Raze</a> from A+ and J to arbitrary argument ranks. It has the same relationship to Join to, the dyadic function sharing the same glyph, as Merge (<code><span class='Function'>></span></code>) does to Couple (<code><span class='Function'>≍</span></code>): <code><span class='Value'>a</span><span class='Function'>≍</span><span class='Value'>b</span></code> is <code><span class='Function'>></span><span class='Value'>a</span><span class='Ligature'>‿</span><span class='Value'>b</span></code> and <code><span class='Value'>a</span><span class='Function'>∾</span><span class='Value'>b</span></code> is <code><span class='Function'>∾</span><span class='Value'>a</span><span class='Ligature'>‿</span><span class='Value'>b</span></code>. While Merge and Couple combine arrays (the elements of Merge's argument, or the arguments themselves for Couple) along a new leading axis, Join and Join to combine them along the existing leading axis. Both Merge and Join can also be called on a higher-rank array, causing Merge to add multiple leading axes while Join combines elements along multiple existing axes.</p> <p>Join can be used to combine several strings into a single string, like <code><span class='Value'>array.join</span><span class='Paren'>()</span></code> in Javascript (but it doesn't force the result to be a string).</p> <pre> <span class='Function'>∾</span><span class='String'>"time"</span><span class='Ligature'>‿</span><span class='String'>"to"</span><span class='Ligature'>‿</span><span class='String'>"join"</span><span class='Ligature'>‿</span><span class='String'>"some"</span><span class='Ligature'>‿</span><span class='String'>"words"</span> -timetojoinsomewords +"timetojoinsomewords" </pre> <p>To join with a separator in between, we might prepend the separator to each string, then remove the leading separator after joining. Another approach would be to insert the separator array as an element between each pair of array elements before calling Join.</p> <pre> <span class='Number'>1</span><span class='Function'>↓∾</span><span class='String'>' '</span><span class='Function'>∾</span><span class='Modifier'>¨</span><span class='String'>"time"</span><span class='Ligature'>‿</span><span class='String'>"to"</span><span class='Ligature'>‿</span><span class='String'>"join"</span><span class='Ligature'>‿</span><span class='String'>"some"</span><span class='Ligature'>‿</span><span class='String'>"words"</span> -time to join some words +"time to join some words" </pre> <p>Join requires each element of its argument to be an array, and their ranks to match exactly. No rank extension is performed.</p> <pre> <span class='Function'>∾</span><span class='String'>"abc"</span><span class='Ligature'>‿</span><span class='String'>'d'</span><span class='Ligature'>‿</span><span class='String'>"ef"</span> <span class='Comment'># Includes a non-array @@ -18,18 +18,23 @@ time to join some words </pre> <p>However, Join has higher-dimensional uses as well. Given a rank-<code><span class='Value'>m</span></code> array of rank-<code><span class='Value'>n</span></code> arrays (requiring <code><span class='Value'>m</span><span class='Function'>≤</span><span class='Value'>n</span></code>), it will merge arrays along their first <code><span class='Value'>m</span></code> axes. For example, if the argument is a matrix of matrices representing a <a href="https://en.wikipedia.org/wiki/Block_matrix">block matrix</a>, Join will give the corresponding unblocked matrix as its result.</p> <pre> <span class='Function'>⊢</span> <span class='Value'>m</span> <span class='Gets'>←</span> <span class='Paren'>(</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>1</span><span class='Function'>∾</span><span class='Modifier'>⌜</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Paren'>)</span> <span class='Function'>⥊</span><span class='Modifier'>¨</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Function'>⥊↕</span><span class='Number'>6</span> -┌───────┬───┬─────────┐ -│0 0 0 0│1 1│2 2 2 2 2│ -│0 0 0 0│1 1│2 2 2 2 2│ -│0 0 0 0│1 1│2 2 2 2 2│ -├───────┼───┼─────────┤ -│3 3 3 3│4 4│5 5 5 5 5│ -└───────┴───┴─────────┘ +┌─ +╵ ┌─ ┌─ ┌─ + ╵ 0 0 0 0 ╵ 1 1 ╵ 2 2 2 2 2 + 0 0 0 0 1 1 2 2 2 2 2 + 0 0 0 0 1 1 2 2 2 2 2 + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵ 3 3 3 3 ╵ 4 4 ╵ 5 5 5 5 5 + ┘ ┘ ┘ + ┘ <span class='Function'>∾</span> <span class='Value'>m</span> <span class='Comment'># Join all that together -</span>0 0 0 0 1 1 2 2 2 2 2 -0 0 0 0 1 1 2 2 2 2 2 -0 0 0 0 1 1 2 2 2 2 2 -3 3 3 3 4 4 5 5 5 5 5 +</span>┌─ +╵ 0 0 0 0 1 1 2 2 2 2 2 + 0 0 0 0 1 1 2 2 2 2 2 + 0 0 0 0 1 1 2 2 2 2 2 + 3 3 3 3 4 4 5 5 5 5 5 + ┘ </pre> <p>Join has fairly strict requirements on the shapes of its argument elements—although less strict than those of Merge, which requires they all have identical shape. Suppose the argument to Join has rank <code><span class='Value'>m</span></code>. Each of its elements must have the same rank, <code><span class='Value'>n</span></code>, which is at least <code><span class='Value'>m</span></code>. The trailing shapes <code><span class='Value'>m</span><span class='Function'>↓</span><span class='Modifier2'>⟜</span><span class='Function'>≢</span><span class='Modifier'>¨</span><span class='Value'>𝕩</span></code> must all be identical (the trailing shape <code><span class='Value'>m</span><span class='Function'>↓≢∾</span><span class='Value'>𝕩</span></code> of the result will match these shapes as well). The other entries in the leading shapes need not be the same, but the shape of an element along a particular axis must depend only on the location of the element along that axis in the full array. For a list argument this imposes no restriction, since the one leading shape element is allowed to depend on position along the only axis. But for higher ranks the structure quickly becomes more rigid.</p> <p>To state this requirement more formally in BQN, we say that there is some list <code><span class='Value'>s</span></code> of lists of lengths, so that <code><span class='Paren'>(</span><span class='Function'>≢</span><span class='Modifier'>¨</span><span class='Value'>s</span><span class='Paren'>)</span><span class='Function'>≡≢</span><span class='Value'>𝕩</span></code>. We require element <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕩</span></code> to have shape <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Modifier'>¨</span><span class='Value'>s</span></code>. Then the first <code><span class='Value'>m</span></code> axes of the result are <code><span class='Function'>+</span><span class='Modifier'>´¨</span><span class='Value'>s</span></code>.</p> diff --git a/docs/doc/logic.html b/docs/doc/logic.html index d9d8a405..8592ca90 100644 --- a/docs/doc/logic.html +++ b/docs/doc/logic.html @@ -16,17 +16,21 @@ <h2 id="examples">Examples</h2> <p>We can form truth tables including the non-integer value one-half:</p> <pre> <span class='Function'>¬</span> <span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0.5</span><span class='Ligature'>‿</span><span class='Number'>1</span> -1‿0.5‿0 +⟨ 1 0.5 0 ⟩ <span class='Function'>∧</span><span class='Modifier'>⌜˜</span> <span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0.5</span><span class='Ligature'>‿</span><span class='Number'>1</span> -0 0 0 -0 0.25 0.5 -0 0.5 1 +┌─ +╵ 0 0 0 + 0 0.25 0.5 + 0 0.5 1 + ┘ <span class='Function'>∨</span><span class='Modifier'>⌜˜</span> <span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0.5</span><span class='Ligature'>‿</span><span class='Number'>1</span> - 0 0.5 1 -0.5 0.75 1 - 1 1 1 +┌─ +╵ 0 0.5 1 + 0.5 0.75 1 + 1 1 1 + ┘ </pre> <p>As with logical And and Or, any value and 0 is 0, while any value or 1 is 1. The other boolean values give the identity elements for the two functions: 1 and any value gives that value, as does 0 or the value.</p> <h2 id="why-not-gcd-and-lcm">Why not GCD and LCM?</h2> diff --git a/docs/doc/prefixes.html b/docs/doc/prefixes.html index 3fabf919..c085624e 100644 --- a/docs/doc/prefixes.html +++ b/docs/doc/prefixes.html @@ -3,34 +3,23 @@ <h1 id="prefixes-and-suffixes">Prefixes and Suffixes</h1> <p>The Prefixes (<code><span class='Function'>↑</span></code>) function gives a list of all prefixes of its argument array along the <a href="leading.html">first axis</a>, and Suffixes (<code><span class='Function'>↓</span></code>) gives a similar list for suffixes. Because the result can be much larger than the argument, these functions may not be used often in high-performance code, but they are a powerful conceptual tool and can make sense for algorithms that are inherently quadratic.</p> <pre> <span class='Function'>↑</span> <span class='String'>"abcde"</span> -┌──┬─┬──┬───┬────┬─────┐ -│⟨⟩│a│ab│abc│abcd│abcde│ -└──┴─┴──┴───┴────┴─────┘ +⟨ ⟨⟩ "a" "ab" "abc" "abcd" "abcde" ⟩ <span class='Function'>↓</span> <span class='String'>"abcde"</span> -┌─────┬────┬───┬──┬─┬──┐ -│abcde│bcde│cde│de│e│⟨⟩│ -└─────┴────┴───┴──┴─┴──┘ +⟨ "abcde" "bcde" "cde" "de" "e" ⟨⟩ ⟩ </pre> <p>The functions are closely related to Take and Drop, as we might expect from their glyphs. Element <code><span class='Value'>i</span><span class='Function'>⊑↑</span><span class='Value'>𝕩</span></code> is <code><span class='Value'>i</span><span class='Function'>↑</span><span class='Value'>𝕩</span></code>, and <code><span class='Value'>i</span><span class='Function'>⊑↓</span><span class='Value'>𝕩</span></code> is <code><span class='Value'>i</span><span class='Function'>↓</span><span class='Value'>𝕩</span></code>.</p> <p>In both cases, an empty array and the entire argument are included in the result, meaning its length is one more than that of the argument. Using <a href="logic.html">Span</a>, we can say that the result has elements whose lengths go from <code><span class='Number'>0</span></code> to <code><span class='Function'>≠</span><span class='Value'>𝕩</span></code>, inclusive, so there are <code><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>¬</span><span class='Number'>0</span></code> or <code><span class='Number'>1</span><span class='Function'>+≠</span><span class='Value'>𝕩</span></code> elements. The total number or cells in the result (for example, <code><span class='Function'>≠∾↑</span><span class='Value'>𝕩</span></code> or <code><span class='Function'>+</span><span class='Modifier'>´</span><span class='Function'>≠</span><span class='Modifier'>¨</span><span class='Function'>↑</span><span class='Value'>𝕩</span></code>) scales with the square of the argument length—it is quadratic in <code><span class='Function'>≠</span><span class='Value'>𝕩</span></code>. We can find the exact total by looking at Prefixes and Suffixes together:</p> <pre> <span class='Paren'>(</span><span class='Function'>↑</span> <span class='Function'>≍</span><span class='Modifier'>˘</span> <span class='Function'>↓</span><span class='Paren'>)</span> <span class='String'>"abcde"</span> -┌─────┬─────┐ -│⟨⟩ │abcde│ -├─────┼─────┤ -│a │bcde │ -├─────┼─────┤ -│ab │cde │ -├─────┼─────┤ -│abc │de │ -├─────┼─────┤ -│abcd │e │ -├─────┼─────┤ -│abcde│⟨⟩ │ -└─────┴─────┘ +┌─ +╵ ⟨⟩ "abcde" + "a" "bcde" + "ab" "cde" + "abc" "de" + "abcd" "e" + "abcde" ⟨⟩ + ┘ <span class='Paren'>(</span><span class='Function'>↑</span> <span class='Function'>∾</span><span class='Modifier'>¨</span> <span class='Function'>↓</span><span class='Paren'>)</span> <span class='String'>"abcde"</span> -┌─────┬─────┬─────┬─────┬─────┬─────┐ -│abcde│abcde│abcde│abcde│abcde│abcde│ -└─────┴─────┴─────┴─────┴─────┴─────┘ +⟨ "abcde" "abcde" "abcde" "abcde" "abcde" "abcde" ⟩ </pre> <p>Joining corresponding elements of <code><span class='Function'>↑</span><span class='Value'>𝕩</span></code> and <code><span class='Function'>↓</span><span class='Value'>𝕩</span></code> gives <code><span class='Value'>𝕩</span></code> again. This is because <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Paren'>(</span><span class='Function'>↑∾</span><span class='Modifier'>¨</span><span class='Function'>↓</span><span class='Paren'>)</span><span class='Value'>𝕩</span></code> is <code><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>⊑↑</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>∾</span><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>⊑↓</span><span class='Value'>𝕩</span><span class='Paren'>)</span></code>, or, using the Take and Drop correspondences, <code><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>↑</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>∾</span><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>↓</span><span class='Value'>𝕩</span><span class='Paren'>)</span></code>, which is <code><span class='Value'>𝕩</span></code>. Element-wise, we are combining the first <code><span class='Value'>i</span></code> cells of <code><span class='Value'>𝕩</span></code> with all but the first <code><span class='Value'>i</span></code>. Looking at the entire result, we now know that <code><span class='Paren'>(</span><span class='Function'>↑∾</span><span class='Modifier'>¨</span><span class='Function'>↓</span><span class='Paren'>)</span><span class='Value'>𝕩</span></code> is <code><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>+≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>⥊<</span><span class='Value'>𝕩</span></code>. The total number of cells in this combined array is therefore <code><span class='Paren'>(</span><span class='Number'>1</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='Number'>1</span><span class='Modifier2'>⊸</span><span class='Function'>+</span><span class='Modifier2'>⊸</span><span class='Function'>×≠</span><span class='Value'>𝕩</span></code>. Each of Prefixes and Suffixes must have the same total number of cells (in fact, <code><span class='Function'>↑</span><span class='Value'>𝕩</span></code> is <code><span class='Function'>⌽</span><span class='Modifier'>¨</span><span class='Modifier2'>∘</span><span class='Function'>↓</span><span class='Modifier2'>⌾</span><span class='Function'>⌽</span><span class='Value'>𝕩</span></code>, and Reverse doesn't change an array's shape). So the total number in either one is <code><span class='Number'>2</span><span class='Function'>÷</span><span class='Modifier'>˜</span><span class='Number'>1</span><span class='Modifier2'>⊸</span><span class='Function'>+</span><span class='Modifier2'>⊸</span><span class='Function'>×≠</span><span class='Value'>𝕩</span></code>. With <code><span class='Value'>n</span><span class='Gets'>←</span><span class='Function'>≠</span><span class='Value'>𝕩</span></code>, it is <code><span class='Number'>2</span><span class='Function'>÷</span><span class='Modifier'>˜</span><span class='Value'>n</span><span class='Function'>×</span><span class='Number'>1</span><span class='Function'>+</span><span class='Value'>n</span></code>.</p> <h2 id="definition">Definition</h2> @@ -38,189 +27,185 @@ <h2 id="working-with-pairs">Working with pairs</h2> <p>Sometimes it's useful to apply an operation to every unordered pair of elements from a list. For example, consider all possible products of numbers between 1 and 6:</p> <pre> <span class='Function'>×</span><span class='Modifier'>⌜˜</span> <span class='Number'>1</span><span class='Function'>+↕</span><span class='Number'>6</span> -1 2 3 4 5 6 -2 4 6 8 10 12 -3 6 9 12 15 18 -4 8 12 16 20 24 -5 10 15 20 25 30 -6 12 18 24 30 36 +┌─ +╵ 1 2 3 4 5 6 + 2 4 6 8 10 12 + 3 6 9 12 15 18 + 4 8 12 16 20 24 + 5 10 15 20 25 30 + 6 12 18 24 30 36 + ┘ </pre> <p>It's easy enough to use the Table modifier here, but it also computes most products twice. If we only care about the unique products, we could multiply each number by all the ones after it. "After" sounds like suffixes, so let's look at those:</p> <pre> <span class='Number'>1</span><span class='Function'>+↕</span><span class='Number'>6</span> -1‿2‿3‿4‿5‿6 +⟨ 1 2 3 4 5 6 ⟩ <span class='Function'>↓</span> <span class='Number'>1</span><span class='Function'>+↕</span><span class='Number'>6</span> -┌───────────┬─────────┬───────┬─────┬───┬───┬──┐ -│1‿2‿3‿4‿5‿6│2‿3‿4‿5‿6│3‿4‿5‿6│4‿5‿6│5‿6│⟨6⟩│⟨⟩│ -└───────────┴─────────┴───────┴─────┴───┴───┴──┘ +⟨ ⟨ 1 2 3 4 5 6 ⟩ ⟨ 2 3 4 5 6 ⟩ ⟨ 3 4 5 6 ⟩ ⟨ 4 5 6 ⟩ ⟨ 5 6 ⟩ ⟨ 6 ⟩ ⟨⟩ ⟩ </pre> <p>We want to include the diagonal, so we'll pair each element with the corresponding element of the suffixes, reducing the suffixes to the original array's length by dropping the last element, which is empty. In other cases, we might not want to include it and we should instead drop the first element.</p> <pre> <span class='Paren'>(</span><span class='Function'>⊢</span> <span class='Function'>×</span> <span class='Function'>≠</span> <span class='Function'>↑</span> <span class='Function'>↓</span><span class='Paren'>)</span> <span class='Number'>1</span><span class='Function'>+↕</span><span class='Number'>6</span> -┌───────────┬───────────┬──────────┬────────┬─────┬────┐ -│1‿2‿3‿4‿5‿6│4‿6‿8‿10‿12│9‿12‿15‿18│16‿20‿24│25‿30│⟨36⟩│ -└───────────┴───────────┴──────────┴────────┴─────┴────┘ +⟨ ⟨ 1 2 3 4 5 6 ⟩ ⟨ 4 6 8 10 12 ⟩ ⟨ 9 12 15 18 ⟩ ⟨ 16 20 24 ⟩ ⟨ 25 30 ⟩ ⟨ 36 ⟩ ⟩ <span class='Paren'>(</span><span class='Function'>⊢</span> <span class='Function'>×</span> <span class='Number'>1</span> <span class='Function'>↓</span> <span class='Function'>↓</span><span class='Paren'>)</span> <span class='Number'>1</span><span class='Function'>+↕</span><span class='Number'>6</span> -┌─────────┬─────────┬────────┬─────┬────┬──┐ -│2‿3‿4‿5‿6│6‿8‿10‿12│12‿15‿18│20‿24│⟨30⟩│⟨⟩│ -└─────────┴─────────┴────────┴─────┴────┴──┘ +⟨ ⟨ 2 3 4 5 6 ⟩ ⟨ 6 8 10 12 ⟩ ⟨ 12 15 18 ⟩ ⟨ 20 24 ⟩ ⟨ 30 ⟩ ⟨⟩ ⟩ </pre> <p>By using <code><span class='Function'>≍</span></code> instead of <code><span class='Function'>×</span></code>, we can see the argument ordering, demonstrating that we are looking at the upper right half of the matrix produced by Table. While in this case we could use <code><span class='Function'>≍</span><span class='Modifier2'>⚇</span><span class='Number'>0</span></code> to mimic the pervasion of <code><span class='Function'>×</span></code>, we'd like this to work even on nested arguments so we should figure out how the mapping structure works to apply Each appropriately.</p> <pre> <span class='Function'>≍</span><span class='Modifier'>⌜˜</span> <span class='String'>"abc"</span> -┌──┬──┬──┐ -│aa│ab│ac│ -├──┼──┼──┤ -│ba│bb│bc│ -├──┼──┼──┤ -│ca│cb│cc│ -└──┴──┴──┘ +┌─ +╵ "aa" "ab" "ac" + "ba" "bb" "bc" + "ca" "cb" "cc" + ┘ <span class='Paren'>(</span><span class='Function'><</span><span class='Modifier'>˘</span> <span class='Function'>≍</span><span class='Modifier'>¨¨</span> <span class='Function'>≠</span> <span class='Function'>↑</span> <span class='Function'>↓</span><span class='Paren'>)</span> <span class='String'>"abc"</span> -┌──────────┬───────┬────┐ -│┌──┬──┬──┐│┌──┬──┐│┌──┐│ -││aa│ab│ac│││bb│bc│││cc││ -│└──┴──┴──┘│└──┴──┘│└──┘│ -└──────────┴───────┴────┘ +⟨ ⟨ "aa" "ab" "ac" ⟩ ⟨ "bb" "bc" ⟩ ⟨ "cc" ⟩ ⟩ </pre> <p>As before, we can exclude the diagonal, and using Prefixes instead of Suffixes gives us the lower left half instead of the upper right—in terms of the arguments given to <code><span class='Function'>≍</span></code> it reverses the argument pairs and iterates in a different order.</p> <pre> <span class='Paren'>(</span><span class='Function'><</span><span class='Modifier'>˘</span> <span class='Function'>≍</span><span class='Modifier'>¨¨</span> <span class='Number'>1</span> <span class='Function'>↓</span> <span class='Function'>↓</span><span class='Paren'>)</span> <span class='String'>"abc"</span> -┌───────┬────┬──┐ -│┌──┬──┐│┌──┐│⟨⟩│ -││ab│ac│││bc││ │ -│└──┴──┘│└──┘│ │ -└───────┴────┴──┘ +⟨ ⟨ "ab" "ac" ⟩ ⟨ "bc" ⟩ ⟨⟩ ⟩ <span class='Paren'>(</span><span class='Function'><</span><span class='Modifier'>˘</span> <span class='Function'>≍</span><span class='Modifier'>¨¨</span> <span class='Number'>1</span> <span class='Function'>↓</span> <span class='Function'>↑</span><span class='Paren'>)</span> <span class='String'>"abc"</span> -┌────┬───────┬──────────┐ -│┌──┐│┌──┬──┐│┌──┬──┬──┐│ -││aa│││ba│bb│││ca│cb│cc││ -│└──┘│└──┴──┘│└──┴──┴──┘│ -└────┴───────┴──────────┘ +⟨ ⟨ "aa" ⟩ ⟨ "ba" "bb" ⟩ ⟨ "ca" "cb" "cc" ⟩ ⟩ <span class='Paren'>(</span><span class='Function'><</span><span class='Modifier'>˘</span> <span class='Function'>≍</span><span class='Modifier'>¨¨</span> <span class='Function'>≠</span> <span class='Function'>↑</span> <span class='Function'>↑</span><span class='Paren'>)</span> <span class='String'>"abc"</span> -┌──┬────┬───────┐ -│⟨⟩│┌──┐│┌──┬──┐│ -│ ││ba│││ca│cb││ -│ │└──┘│└──┴──┘│ -└──┴────┴───────┘ +⟨ ⟨⟩ ⟨ "ba" ⟩ ⟨ "ca" "cb" ⟩ ⟩ </pre> <h2 id="slices">Slices</h2> <p>Prefixes and Suffixes give certain restricted slices of the argument array, where a slice is a contiguous selection of cells. If we want all slices along the first axis, we can take the suffixes of each prefix, or vice-versa:</p> <pre> <span class='Function'>↓</span><span class='Modifier'>¨</span><span class='Function'>↑</span> <span class='String'>"abc"</span> -┌────┬──────┬─────────┬─────────────┐ -│┌──┐│┌─┬──┐│┌──┬─┬──┐│┌───┬──┬─┬──┐│ -││⟨⟩│││a│⟨⟩│││ab│b│⟨⟩│││abc│bc│c│⟨⟩││ -│└──┘│└─┴──┘│└──┴─┴──┘│└───┴──┴─┴──┘│ -└────┴──────┴─────────┴─────────────┘ +┌─ +· ⟨ ⟨⟩ ⟩ ⟨ "a" ⟨⟩ ⟩ ⟨ "ab" "b" ⟨⟩ ⟩ ⟨ "abc" "bc" "c" ⟨⟩ ⟩ + ┘ <span class='Function'>↑</span><span class='Modifier'>¨</span><span class='Function'>↓</span> <span class='String'>"abc"</span> -┌─────────────┬─────────┬──────┬────┐ -│┌──┬─┬──┬───┐│┌──┬─┬──┐│┌──┬─┐│┌──┐│ -││⟨⟩│a│ab│abc│││⟨⟩│b│bc│││⟨⟩│c│││⟨⟩││ -│└──┴─┴──┴───┘│└──┴─┴──┘│└──┴─┘│└──┘│ -└─────────────┴─────────┴──────┴────┘ +┌─ +· ⟨ ⟨⟩ "a" "ab" "abc" ⟩ ⟨ ⟨⟩ "b" "bc" ⟩ ⟨ ⟨⟩ "c" ⟩ ⟨ ⟨⟩ ⟩ + ┘ </pre> <p>Effectively, this parametrizes the slices either by ending then starting index, or by starting index then length. Four empty slices are included because in a list of length 3 there are 4 places an empty slice can start: all the spaces between or outside elements (these also correspond to all the possible positions for the result of <a href="bins.html">Bins</a>). The slices can also be parametrized by length and then starting index using <a href="windows.html">Windows</a>.</p> <pre> <span class='Paren'>((</span><span class='Function'>↕</span><span class='Number'>1</span><span class='Function'>+≠</span><span class='Paren'>)</span><span class='Function'>↕</span><span class='Modifier'>¨</span><span class='Function'><</span><span class='Paren'>)</span> <span class='String'>"abc"</span> -┌──────┬─┬──┬───┐ -│4‿0⥊⟨⟩│a│ab│abc│ -│ │b│bc│ │ -│ │c│ │ │ -└──────┴─┴──┴───┘ +┌─ +· ┌┐ ┌─ ┌─ ┌─ + ╵ ╵"a ╵"ab ╵"abc" + b bc ┘ + c ┘ + ┘ + ┘ + ┘ <span class='Paren'>((</span><span class='Function'>↕</span><span class='Number'>1</span><span class='Function'>+≠</span><span class='Paren'>)</span><span class='Function'><</span><span class='Modifier'>˘</span><span class='Modifier2'>∘</span><span class='Function'>↕</span><span class='Modifier'>¨</span><span class='Function'><</span><span class='Paren'>)</span> <span class='String'>"abc"</span> <span class='Comment'># Split them to match Prefixes/Suffixes -</span>┌─────────────┬───────┬───────┬─────┐ -│┌──┬──┬──┬──┐│┌─┬─┬─┐│┌──┬──┐│┌───┐│ -││⟨⟩│⟨⟩│⟨⟩│⟨⟩│││a│b│c│││ab│bc│││abc││ -│└──┴──┴──┴──┘│└─┴─┴─┘│└──┴──┘│└───┘│ -└─────────────┴───────┴───────┴─────┘ +</span>┌─ +· ⟨ ⟨⟩ ⟨⟩ ⟨⟩ ⟨⟩ ⟩ ⟨ "a" "b" "c" ⟩ ⟨ "ab" "bc" ⟩ ⟨ "abc" ⟩ + ┘ </pre> <p>We might view a slice as a selection for not two but <em>three</em> parameters: the number of cells before, in, and after the slice. The conditions are that each parameter, being a length, is at least 0, and the total of the three parameters is equal to the array length. With three parameters and one equality constraint, the space of slices is two-dimensional; the above ways to enumerate it each pick two parameters and allow the third to be dependent on these two. If you're familiar with <a href="https://en.wikipedia.org/wiki/Barycentric_coordinate_system">barycentric coordinates</a> on a triangle, this should sound very familiar because that's exactly what the three parameters are!</p> <p>We might also consider the question of slices along multiple axes. Because axes are orthogonal, we can choose such a slice by independently slicing along each axis. To use the homogeneous shape of arrays as much as possible, the result should still only have two added layers of nesting for the two coordinates we choose, with all possible choices for the first axis along the axes of the outer array and those for the second along the axes of each inner array. Our Windows-based solution adapts to multidimensional arrays easily:</p> <pre> <span class='Paren'>((</span><span class='Function'>↕</span><span class='Number'>1</span><span class='Function'>+≢</span><span class='Paren'>)</span><span class='Function'><</span><span class='Modifier2'>⎉</span><span class='Number'>2</span><span class='Modifier2'>∘</span><span class='Function'>↕</span><span class='Modifier'>¨</span><span class='Function'><</span><span class='Paren'>)</span> <span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='String'>"abcdef"</span> -┌──────────────────────┬───────────────┬────────┐ -│┌──────┬──────┬──────┐│┌──────┬──────┐│┌──────┐│ -││0‿0⥊⟨⟩│0‿0⥊⟨⟩│0‿0⥊⟨⟩│││0‿1⥊⟨⟩│0‿1⥊⟨⟩│││0‿2⥊⟨⟩││ -│├──────┼──────┼──────┤│├──────┼──────┤│├──────┤│ -││0‿0⥊⟨⟩│0‿0⥊⟨⟩│0‿0⥊⟨⟩│││0‿1⥊⟨⟩│0‿1⥊⟨⟩│││0‿2⥊⟨⟩││ -│├──────┼──────┼──────┤│├──────┼──────┤│├──────┤│ -││0‿0⥊⟨⟩│0‿0⥊⟨⟩│0‿0⥊⟨⟩│││0‿1⥊⟨⟩│0‿1⥊⟨⟩│││0‿2⥊⟨⟩││ -│├──────┼──────┼──────┤│├──────┼──────┤│├──────┤│ -││0‿0⥊⟨⟩│0‿0⥊⟨⟩│0‿0⥊⟨⟩│││0‿1⥊⟨⟩│0‿1⥊⟨⟩│││0‿2⥊⟨⟩││ -│└──────┴──────┴──────┘│└──────┴──────┘│└──────┘│ -├──────────────────────┼───────────────┼────────┤ -│┌──────┬──────┬──────┐│┌─────┬─────┐ │┌──┐ │ -││1‿0⥊⟨⟩│1‿0⥊⟨⟩│1‿0⥊⟨⟩│││1‿1⥊a│1‿1⥊b│ ││ab│ │ -│├──────┼──────┼──────┤│├─────┼─────┤ │├──┤ │ -││1‿0⥊⟨⟩│1‿0⥊⟨⟩│1‿0⥊⟨⟩│││1‿1⥊c│1‿1⥊d│ ││cd│ │ -│├──────┼──────┼──────┤│├─────┼─────┤ │├──┤ │ -││1‿0⥊⟨⟩│1‿0⥊⟨⟩│1‿0⥊⟨⟩│││1‿1⥊e│1‿1⥊f│ ││ef│ │ -│└──────┴──────┴──────┘│└─────┴─────┘ │└──┘ │ -├──────────────────────┼───────────────┼────────┤ -│┌──────┬──────┬──────┐│┌─┬─┐ │┌──┐ │ -││2‿0⥊⟨⟩│2‿0⥊⟨⟩│2‿0⥊⟨⟩│││a│b│ ││ab│ │ -│├──────┼──────┼──────┤││c│d│ ││cd│ │ -││2‿0⥊⟨⟩│2‿0⥊⟨⟩│2‿0⥊⟨⟩││├─┼─┤ │├──┤ │ -│└──────┴──────┴──────┘││c│d│ ││cd│ │ -│ ││e│f│ ││ef│ │ -│ │└─┴─┘ │└──┘ │ -├──────────────────────┼───────────────┼────────┤ -│┌──────┬──────┬──────┐│┌─┬─┐ │┌──┐ │ -││3‿0⥊⟨⟩│3‿0⥊⟨⟩│3‿0⥊⟨⟩│││a│b│ ││ab│ │ -│└──────┴──────┴──────┘││c│d│ ││cd│ │ -│ ││e│f│ ││ef│ │ -│ │└─┴─┘ │└──┘ │ -└──────────────────────┴───────────────┴────────┘ +┌─ +╵ ┌─ ┌─ ┌─ + ╵ ┌┐ ┌┐ ┌┐ ╵ 0‿1⥊⟨⟩ 0‿1⥊⟨⟩ ╵ 0‿2⥊⟨⟩ + └┘ └┘ └┘ 0‿1⥊⟨⟩ 0‿1⥊⟨⟩ 0‿2⥊⟨⟩ + ┌┐ ┌┐ ┌┐ 0‿1⥊⟨⟩ 0‿1⥊⟨⟩ 0‿2⥊⟨⟩ + └┘ └┘ └┘ 0‿1⥊⟨⟩ 0‿1⥊⟨⟩ 0‿2⥊⟨⟩ + ┌┐ ┌┐ ┌┐ ┘ ┘ + └┘ └┘ └┘ + ┌┐ ┌┐ ┌┐ + └┘ └┘ └┘ + ┘ + ┌─ ┌─ ┌─ + ╵ ┌┐ ┌┐ ┌┐ ╵ ┌─ ┌─ ╵ ┌─ + ╵ ╵ ╵ ╵"a" ╵"b" ╵"ab" + ┘ ┘ ┘ ┘ ┘ ┘ + ┌┐ ┌┐ ┌┐ ┌─ ┌─ ┌─ + ╵ ╵ ╵ ╵"c" ╵"d" ╵"cd" + ┘ ┘ ┘ ┘ ┘ ┘ + ┌┐ ┌┐ ┌┐ ┌─ ┌─ ┌─ + ╵ ╵ ╵ ╵"e" ╵"f" ╵"ef" + ┘ ┘ ┘ ┘ ┘ ┘ + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵ ┌┐ ┌┐ ┌┐ ╵ ┌─ ┌─ ╵ ┌─ + ╵ ╵ ╵ ╵"a ╵"b ╵"ab + c d cd + ┘ ┘ ┘ ┘ ┘ ┘ + ┌┐ ┌┐ ┌┐ ┌─ ┌─ ┌─ + ╵ ╵ ╵ ╵"c ╵"d ╵"cd + e f ef + ┘ ┘ ┘ ┘ ┘ ┘ + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵ ┌┐ ┌┐ ┌┐ ╵ ┌─ ┌─ ╵ ┌─ + ╵ ╵ ╵ ╵"a ╵"b ╵"ab + c d cd + e f ef + ┘ ┘ ┘ ┘ ┘ ┘ + ┘ ┘ ┘ + ┘ </pre> <p>This array can be <a href="join.html">joined</a>, indicating that the length of each inner axis depends only on the position in the corresponding outer axis (let's also drop those empty slices to take up less space).</p> <pre> <span class='Function'>∾</span> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>1</span> <span class='Function'>↓</span> <span class='Paren'>((</span><span class='Function'>↕</span><span class='Number'>1</span><span class='Function'>+≢</span><span class='Paren'>)</span><span class='Function'><</span><span class='Modifier2'>⎉</span><span class='Number'>2</span><span class='Modifier2'>∘</span><span class='Function'>↕</span><span class='Modifier'>¨</span><span class='Function'><</span><span class='Paren'>)</span> <span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='String'>"abcdef"</span> -┌─────┬─────┬──┐ -│1‿1⥊a│1‿1⥊b│ab│ -├─────┼─────┼──┤ -│1‿1⥊c│1‿1⥊d│cd│ -├─────┼─────┼──┤ -│1‿1⥊e│1‿1⥊f│ef│ -├─────┼─────┼──┤ -│a │b │ab│ -│c │d │cd│ -├─────┼─────┼──┤ -│c │d │cd│ -│e │f │ef│ -├─────┼─────┼──┤ -│a │b │ab│ -│c │d │cd│ -│e │f │ef│ -└─────┴─────┴──┘ +┌─ +╵ ┌─ ┌─ ┌─ + ╵"a" ╵"b" ╵"ab" + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵"c" ╵"d" ╵"cd" + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵"e" ╵"f" ╵"ef" + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵"a ╵"b ╵"ab + c d cd + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵"c ╵"d ╵"cd + e f ef + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵"a ╵"b ╵"ab + c d cd + e f ef + ┘ ┘ ┘ + ┘ </pre> <p>But Prefixes and Suffixes <a href="../problems.html#cant-take-prefixes-or-suffixes-on-multiple-axes">don't have</a> any way to specify that they should work on multiple axes, and always work on exactly one. So to extend this pattern we will have to define multi-dimensional versions. This turns out to be very easy: just replace Length with Shape in the <a href="#definition">definitions</a> above.</p> <pre> <span class='Function'>Prefs</span> <span class='Gets'>←</span> <span class='Paren'>(</span><span class='Function'>↕</span><span class='Number'>1</span><span class='Function'>+≢</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Modifier'>¨</span><span class='Function'><</span> <span class='Function'>Suffs</span> <span class='Gets'>←</span> <span class='Paren'>(</span><span class='Function'>↕</span><span class='Number'>1</span><span class='Function'>+≢</span><span class='Paren'>)</span><span class='Function'>↓</span><span class='Modifier'>¨</span><span class='Function'><</span> <span class='Function'>Prefs</span><span class='Modifier'>¨</span><span class='Function'>Suffs</span> <span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='String'>"abcdef"</span> -┌──────────────────────┬───────────────┬────────┐ -│┌──────┬──────┬──────┐│┌──────┬──────┐│┌──────┐│ -││0‿0⥊""│0‿1⥊""│0‿2⥊""│││0‿0⥊""│0‿1⥊""│││0‿0⥊""││ -│├──────┼──────┼──────┤│├──────┼──────┤│├──────┤│ -││1‿0⥊""│1‿1⥊a │ab │││1‿0⥊""│1‿1⥊b │││1‿0⥊""││ -│├──────┼──────┼──────┤│├──────┼──────┤│├──────┤│ -││2‿0⥊""│a │ab │││2‿0⥊""│b │││2‿0⥊""││ -││ │c │cd │││ │d ││├──────┤│ -│├──────┼──────┼──────┤│├──────┼──────┤││3‿0⥊""││ -││3‿0⥊""│a │ab │││3‿0⥊""│b ││└──────┘│ -││ │c │cd │││ │d ││ │ -││ │e │ef │││ │f ││ │ -│└──────┴──────┴──────┘│└──────┴──────┘│ │ -├──────────────────────┼───────────────┼────────┤ -│┌──────┬──────┬──────┐│┌──────┬──────┐│┌──────┐│ -││0‿0⥊""│0‿1⥊""│0‿2⥊""│││0‿0⥊""│0‿1⥊""│││0‿0⥊""││ -│├──────┼──────┼──────┤│├──────┼──────┤│├──────┤│ -││1‿0⥊""│1‿1⥊c │cd │││1‿0⥊""│1‿1⥊d │││1‿0⥊""││ -│├──────┼──────┼──────┤│├──────┼──────┤│├──────┤│ -││2‿0⥊""│c │cd │││2‿0⥊""│d │││2‿0⥊""││ -││ │e │ef │││ │f ││└──────┘│ -│└──────┴──────┴──────┘│└──────┴──────┘│ │ -├──────────────────────┼───────────────┼────────┤ -│┌──────┬──────┬──────┐│┌──────┬──────┐│┌──────┐│ -││0‿0⥊""│0‿1⥊""│0‿2⥊""│││0‿0⥊""│0‿1⥊""│││0‿0⥊""││ -│├──────┼──────┼──────┤│├──────┼──────┤│├──────┤│ -││1‿0⥊""│1‿1⥊e │ef │││1‿0⥊""│1‿1⥊f │││1‿0⥊""││ -│└──────┴──────┴──────┘│└──────┴──────┘│└──────┘│ -├──────────────────────┼───────────────┼────────┤ -│┌──────┬──────┬──────┐│┌──────┬──────┐│┌──────┐│ -││0‿0⥊""│0‿1⥊""│0‿2⥊""│││0‿0⥊""│0‿1⥊""│││0‿0⥊""││ -│└──────┴──────┴──────┘│└──────┴──────┘│└──────┘│ -└──────────────────────┴───────────────┴────────┘ +┌─ +╵ ┌─ ┌─ ┌─ + ╵ ┌┐ 0‿1⥊⟨⟩ 0‿2⥊⟨⟩ ╵ ┌┐ 0‿1⥊⟨⟩ ╵ ┌┐ + └┘ └┘ └┘ + ┌┐ ┌─ ┌─ ┌┐ ┌─ ┌┐ + ╵ ╵"a" ╵"ab" ╵ ╵"b" ╵ + ┘ ┘ ┘ ┘ ┘ ┘ + ┌┐ ┌─ ┌─ ┌┐ ┌─ ┌┐ + ╵ ╵"a ╵"ab ╵ ╵"b ╵ + c cd d + ┘ ┘ ┘ ┘ ┘ ┘ + ┌┐ ┌─ ┌─ ┌┐ ┌─ ┌┐ + ╵ ╵"a ╵"ab ╵ ╵"b ╵ + c cd d + e ef f + ┘ ┘ ┘ ┘ ┘ ┘ + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵ ┌┐ 0‿1⥊⟨⟩ 0‿2⥊⟨⟩ ╵ ┌┐ 0‿1⥊⟨⟩ ╵ ┌┐ + └┘ └┘ └┘ + ┌┐ ┌─ ┌─ ┌┐ ┌─ ┌┐ + ╵ ╵"c" ╵"cd" ╵ ╵"d" ╵ + ┘ ┘ ┘ ┘ ┘ ┘ + ┌┐ ┌─ ┌─ ┌┐ ┌─ ┌┐ + ╵ ╵"c ╵"cd ╵ ╵"d ╵ + e ef f + ┘ ┘ ┘ ┘ ┘ ┘ + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵ ┌┐ 0‿1⥊⟨⟩ 0‿2⥊⟨⟩ ╵ ┌┐ 0‿1⥊⟨⟩ ╵ ┌┐ + └┘ └┘ └┘ + ┌┐ ┌─ ┌─ ┌┐ ┌─ ┌┐ + ╵ ╵"e" ╵"ef" ╵ ╵"f" ╵ + ┘ ┘ ┘ ┘ ┘ ┘ + ┘ ┘ ┘ + ┌─ ┌─ ┌─ + ╵ ┌┐ 0‿1⥊⟨⟩ 0‿2⥊⟨⟩ ╵ ┌┐ 0‿1⥊⟨⟩ ╵ ┌┐ + └┘ └┘ └┘ + ┘ ┘ ┘ + ┘ </pre> diff --git a/docs/doc/transpose.html b/docs/doc/transpose.html index 51e8b91a..2020a520 100644 --- a/docs/doc/transpose.html +++ b/docs/doc/transpose.html @@ -6,51 +6,51 @@ <p>Transposing a matrix exchanges its axes, mirroring it across the diagonal. APL extends the function to any rank by reversing all axes, but this generalization isn't very natural and is almost never used. The main reason for it is to maintain the equivalence <code><span class='Value'>a</span> <span class='Function'>MP</span> <span class='Value'>b</span> <span class='Gets'>←→</span> <span class='Value'>a</span> <span class='Function'>MP</span><span class='Modifier2'>⌾</span><span class='Function'>⍉</span> <span class='Value'>b</span></code>, where <code><span class='Function'>MP</span> <span class='Gets'>←</span> <span class='Paren'>(</span><span class='Function'>+</span><span class='Modifier'>´</span><span class='Function'><</span><span class='Modifier'>˘</span><span class='Paren'>)</span><span class='Modifier2'>∘</span><span class='Function'>×</span><span class='Modifier2'>⎉</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>∞</span></code> is the generalized matrix product. But even here APL's Transpose is suspect. It does much more work than it needs to, as we'll see.</p> <p>BQN's transpose takes the first axis of its argument and moves it to the end.</p> <pre> <span class='Function'>≢</span> <span class='Value'>a23456</span> <span class='Gets'>←</span> <span class='Function'>↕</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>6</span> -<span class='Value'>[</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Value'>]</span> +<span class='Bracket'>⟨</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Bracket'>⟩</span> <span class='Function'>≢</span> <span class='Function'>⍉</span> <span class='Value'>a23456</span> -<span class='Value'>[</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Number'>2</span> <span class='Value'>]</span> +<span class='Bracket'>⟨</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Number'>2</span> <span class='Bracket'>⟩</span> </pre> <p>On the argument's ravel, this looks like a simple 2-dimensional transpose: one axis is exchanged with a compound axis made up of the other axes. Here we transpose a rank 3 matrix:</p> <pre> <span class='Value'>a322</span> <span class='Gets'>←</span> <span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊↕</span><span class='Number'>12</span> <span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'><</span><span class='Modifier2'>⟜</span><span class='Function'>⍉</span> <span class='Value'>a322</span> -<span class='Value'>┌</span> - <span class='Value'>┌</span> <span class='Value'>┌</span> - <span class='Number'>0</span> <span class='Number'>1</span> <span class='Number'>0</span> <span class='Number'>4</span> <span class='Number'>8</span> - <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>1</span> <span class='Number'>5</span> <span class='Number'>9</span> - - <span class='Number'>4</span> <span class='Number'>5</span> <span class='Number'>2</span> <span class='Number'>6</span> <span class='Number'>10</span> - <span class='Number'>6</span> <span class='Number'>7</span> <span class='Number'>3</span> <span class='Number'>7</span> <span class='Number'>11</span> - <span class='Value'>┘</span> - <span class='Number'>8</span> <span class='Number'>9</span> - <span class='Number'>10</span> <span class='Number'>11</span> - <span class='Value'>┘</span> - <span class='Value'>┘</span> +┌─ +· ┌─ ┌─ + ╎ 0 1 ╎ 0 4 8 + 2 3 1 5 9 + + 4 5 2 6 10 + 6 7 3 7 11 + ┘ + 8 9 + 10 11 + ┘ + ┘ </pre> <p>But, reading in ravel order, the argument and result have exactly the same element ordering as for the rank 2 matrix <code><span class='Function'>⥊</span><span class='Modifier'>˘</span> <span class='Value'>a322</span></code>:</p> <pre> <span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'><</span><span class='Modifier2'>⟜</span><span class='Function'>⍉</span> <span class='Function'>⥊</span><span class='Modifier'>˘</span> <span class='Value'>a322</span> -<span class='Value'>┌</span> - <span class='Value'>┌</span> <span class='Value'>┌</span> - <span class='Number'>0</span> <span class='Number'>1</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>0</span> <span class='Number'>4</span> <span class='Number'>8</span> - <span class='Number'>4</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Number'>7</span> <span class='Number'>1</span> <span class='Number'>5</span> <span class='Number'>9</span> - <span class='Number'>8</span> <span class='Number'>9</span> <span class='Number'>10</span> <span class='Number'>11</span> <span class='Number'>2</span> <span class='Number'>6</span> <span class='Number'>10</span> - <span class='Value'>┘</span> <span class='Number'>3</span> <span class='Number'>7</span> <span class='Number'>11</span> - <span class='Value'>┘</span> - <span class='Value'>┘</span> +┌─ +· ┌─ ┌─ + ╵ 0 1 2 3 ╵ 0 4 8 + 4 5 6 7 1 5 9 + 8 9 10 11 2 6 10 + ┘ 3 7 11 + ┘ + ┘ </pre> <p>To exchange multiple axes, use the Power modifier. Like Rotate, a negative power will move axes in the other direction. In particular, to move the last axis to the front, use Inverse (as you might expect, this exactly inverts <code><span class='Function'>⍉</span></code>).</p> <pre> <span class='Function'>≢</span> <span class='Function'>⍉</span><span class='Modifier2'>⍟</span><span class='Number'>3</span> <span class='Value'>a23456</span> -<span class='Value'>[</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Value'>]</span> +<span class='Bracket'>⟨</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Bracket'>⟩</span> <span class='Function'>≢</span> <span class='Function'>⍉</span><span class='Modifier'>⁼</span> <span class='Value'>a23456</span> -<span class='Value'>[</span> <span class='Number'>6</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>5</span> <span class='Value'>]</span> +<span class='Bracket'>⟨</span> <span class='Number'>6</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>5</span> <span class='Bracket'>⟩</span> </pre> <p>In fact, we have <code><span class='Function'>≢⍉</span><span class='Modifier2'>⍟</span><span class='Value'>k</span> <span class='Value'>a</span> <span class='Gets'>←→</span> <span class='Value'>k</span><span class='Function'>⌽≢</span><span class='Value'>a</span></code> for any number <code><span class='Value'>k</span></code> and array <code><span class='Value'>a</span></code>.</p> <p>To move axes other than the first, use the Rank modifier in order to leave initial axes untouched. A rank of <code><span class='Value'>k</span><span class='Function'>></span><span class='Number'>0</span></code> transposes only the last <code><span class='Value'>k</span></code> axes while a rank of <code><span class='Value'>k</span><span class='Function'><</span><span class='Number'>0</span></code> ignores the first <code><span class='Function'>|</span><span class='Value'>k</span></code> axes.</p> <pre> <span class='Function'>≢</span> <span class='Function'>⍉</span><span class='Modifier2'>⎉</span><span class='Number'>3</span> <span class='Value'>a23456</span> -<span class='Value'>[</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Number'>4</span> <span class='Value'>]</span> +<span class='Bracket'>⟨</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Number'>4</span> <span class='Bracket'>⟩</span> </pre> <p>And of course, Rank and Power can be combined to do more complicated transpositions: move a set of contiguous axes with any starting point and length to the end.</p> <pre> <span class='Function'>≢</span> <span class='Function'>⍉</span><span class='Modifier'>⁼</span><span class='Modifier2'>⎉</span><span class='Number'>¯1</span> <span class='Value'>a23456</span> -<span class='Value'>[</span> <span class='Number'>2</span> <span class='Number'>6</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>5</span> <span class='Value'>]</span> +<span class='Bracket'>⟨</span> <span class='Number'>2</span> <span class='Number'>6</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>5</span> <span class='Bracket'>⟩</span> </pre> <p>Using these forms, we can state BQN's generalized matrix product swapping rule:</p> <pre><span class='Value'>a</span> <span class='Function'>MP</span> <span class='Value'>b</span> <span class='Gets'>←→</span> <span class='Function'>⍉</span><span class='Modifier2'>⍟</span><span class='Paren'>(</span><span class='Function'>≠≢</span><span class='Value'>a</span><span class='Paren'>)</span> <span class='Value'>a</span> <span class='Function'>⍉</span><span class='Modifier'>⁼</span><span class='Modifier2'>⊸</span><span class='Function'>MP</span><span class='Modifier2'>⟜</span><span class='Function'>⍉</span> <span class='Value'>b</span> @@ -58,27 +58,27 @@ <p>Certainly not as concise as APL's version, but not a horror either. BQN's rule is actually more parsimonious in that it only performs the axis exchanges necessary for the computation: it moves the two axes that will be paired with the matrix product into place before the product, and directly exchanges all axes afterwards. Each of these steps is equivalent in terms of data movement to a matrix transpose, the simplest nontrivial transpose to perform. Also remember that for two-dimensional matrices both kinds of transposition are the same, and APL's rule holds in BQN.</p> <p>Axis permutations of the types we've shown generate the complete permutation group on any number of axes, so you could produce any transposition you want with the right sequence of monadic transpositions with Rank. However, this can be unintuitive and tedious. What if you want to transpose the first three axes, leaving the rest alone? With monadic Transpose you have to send some axes to the end, then bring them back to the beginning. For example [following four or five failed tries]:</p> <pre> <span class='Function'>≢</span> <span class='Function'>⍉</span><span class='Modifier'>⁼</span><span class='Modifier2'>⎉</span><span class='Number'>¯2</span> <span class='Function'>⍉</span> <span class='Value'>a23456</span> <span class='Comment'># Restrict Transpose to the first three axes -</span><span class='Value'>[</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>2</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Value'>]</span> +</span><span class='Bracket'>⟨</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>2</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Bracket'>⟩</span> </pre> <p>In a case like this BQN's Dyadic transpose is much easier.</p> <h2 id="dyadic-transpose">Dyadic Transpose</h2> <p>Transpose also allows a left argument that specifies a permutation of the right argument's axes. For each index <code><span class='Value'>p</span><span class='Gets'>←</span><span class='Value'>i</span><span class='Function'>⊏</span><span class='Value'>𝕨</span></code> in the left argument, axis <code><span class='Value'>i</span></code> of the argument is used for axis <code><span class='Value'>p</span></code> of the result. Multiple argument axes can be sent to the same result axis, in which case that axis goes along a diagonal of the argument array, and the result will have a lower rank than the argument.</p> <pre> <span class='Function'>≢</span> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>4</span> <span class='Function'>⍉</span> <span class='Value'>a23456</span> -<span class='Value'>[</span> <span class='Number'>5</span> <span class='Number'>2</span> <span class='Number'>4</span> <span class='Number'>3</span> <span class='Number'>6</span> <span class='Value'>]</span> +<span class='Bracket'>⟨</span> <span class='Number'>5</span> <span class='Number'>2</span> <span class='Number'>4</span> <span class='Number'>3</span> <span class='Number'>6</span> <span class='Bracket'>⟩</span> <span class='Function'>≢</span> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0</span> <span class='Function'>⍉</span> <span class='Value'>a23456</span> <span class='Comment'># Don't worry too much about this case though -</span><span class='Value'>[</span> <span class='Number'>5</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Value'>]</span> +</span><span class='Bracket'>⟨</span> <span class='Number'>5</span> <span class='Number'>2</span> <span class='Number'>3</span> <span class='Bracket'>⟩</span> </pre> <p>Since this kind of rearrangement can be counterintuitive, it's often easier to use <code><span class='Function'>⍉</span><span class='Modifier'>⁼</span></code> when specifying all axes. If <code><span class='Value'>p</span><span class='Function'>≡</span><span class='Modifier2'>○</span><span class='Function'>≠≢</span><span class='Value'>a</span></code>, then we have <code><span class='Function'>≢</span><span class='Value'>p</span><span class='Function'>⍉</span><span class='Modifier'>⁼</span><span class='Value'>a</span> <span class='Gets'>←→</span> <span class='Value'>p</span><span class='Function'>⊏≢</span><span class='Value'>a</span></code>.</p> <pre> <span class='Function'>≢</span> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>4</span> <span class='Function'>⍉</span><span class='Modifier'>⁼</span> <span class='Value'>a23456</span> -<span class='Value'>[</span> <span class='Number'>3</span> <span class='Number'>5</span> <span class='Number'>4</span> <span class='Number'>2</span> <span class='Number'>6</span> <span class='Value'>]</span> +<span class='Bracket'>⟨</span> <span class='Number'>3</span> <span class='Number'>5</span> <span class='Number'>4</span> <span class='Number'>2</span> <span class='Number'>6</span> <span class='Bracket'>⟩</span> </pre> <p>So far, all like APL. BQN makes one little extension, which is to allow only some axes to be specified. The left argument will be matched up with leading axes of the right argument. Those axes are moved according to the left argument, and remaining axes are placed in order into the gaps between them.</p> <pre> <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='Function'>⍉</span> <span class='Value'>a23456</span> -<span class='Value'>[</span> <span class='Number'>2</span> <span class='Number'>5</span> <span class='Number'>3</span> <span class='Number'>6</span> <span class='Number'>4</span> <span class='Value'>]</span> +<span class='Bracket'>⟨</span> <span class='Number'>2</span> <span class='Number'>5</span> <span class='Number'>3</span> <span class='Number'>6</span> <span class='Number'>4</span> <span class='Bracket'>⟩</span> </pre> <p>In particular, the case with only one argument specified is interesting. Here, the first axis ends up at the given location. This gives us a much better solution to the problem at the end of the last section.</p> <pre> <span class='Function'>≢</span> <span class='Number'>2</span> <span class='Function'>⍉</span> <span class='Value'>a23456</span> <span class='Comment'># Restrict Transpose to the first three axes -</span><span class='Value'>[</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>2</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Value'>]</span> +</span><span class='Bracket'>⟨</span> <span class='Number'>3</span> <span class='Number'>4</span> <span class='Number'>2</span> <span class='Number'>5</span> <span class='Number'>6</span> <span class='Bracket'>⟩</span> </pre> <p>Finally, it's worth noting that, as monadic Transpose moves the first axis to the end, it's equivalent to dyadic Transpose with a "default" left argument: <code><span class='Paren'>(</span><span class='Function'>≠</span><span class='Modifier2'>∘</span><span class='Function'>≢-</span><span class='Number'>1</span><span class='Modifier'>˜</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>⍉</span></code>.</p> <h2 id="definitions">Definitions</h2> diff --git a/docs/doc/windows.html b/docs/doc/windows.html index 79d18e77..c20d6591 100644 --- a/docs/doc/windows.html +++ b/docs/doc/windows.html @@ -6,35 +6,42 @@ <h2 id="definition">Definition</h2> <p>We'll start with the one-axis case. Here Window's left argument 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 major cells) with length <code><span class='Value'>𝕨</span></code>, starting at each possible index in order.</p> <pre> <span class='Number'>5</span><span class='Function'>↕</span><span class='String'>"abcdefg"</span> -abcde -bcdef -cdefg +┌─ +╵"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 spanned by these two endpoints.</p> <p>You can take a slice of an array <code><span class='Value'>𝕩</span></code> that has length <code><span class='Value'>l</span></code> and starts at index <code><span class='Value'>i</span></code> using <code><span class='Value'>l</span><span class='Function'>↑</span><span class='Value'>i</span><span class='Function'>↓</span><span class='Value'>𝕩</span></code> or <code><span class='Value'>l</span><span class='Function'>↑</span><span class='Value'>i</span><span class='Function'>⌽</span><span class='Value'>𝕩</span></code>. 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 you the slice starting at that cell's index:</p> <pre> <span class='Number'>2</span><span class='Function'>⊏</span><span class='Number'>5</span><span class='Function'>↕</span><span class='String'>"abcdefg"</span> -cdefg +"cdefg" <span class='Number'>5</span><span class='Function'>↑</span><span class='Number'>2</span><span class='Function'>↓</span><span class='String'>"abcdefg"</span> -cdefg +"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.</p> <h3 id="multiple-dimensions">Multiple dimensions</h3> <p>The above description applies to a higher-rank right argument. As an example, we'll look at two-row slices of a shape <code><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</span></code> array. For convenience, we will enclose each slice. Note that slices always have the same rank as the argument array.</p> <pre> <span class='Function'><</span><span class='Modifier2'>⎉</span><span class='Number'>2</span> <span class='Number'>2</span><span class='Function'>↕</span><span class='String'>"0123"</span><span class='Function'>∾</span><span class='String'>"abcd"</span><span class='Function'>≍</span><span class='String'>"ABCD"</span> -┌────┬────┐ -│0123│abcd│ -│abcd│ABCD│ -└────┴────┘ +┌─ +· ┌─ ┌─ + ╵"0123 ╵"abcd + abcd ABCD + ┘ ┘ + ┘ </pre> <p>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> <pre> <span class='Function'><</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='String'>"0123"</span><span class='Function'>∾</span><span class='String'>"abcd"</span><span class='Function'>≍</span><span class='String'>"ABCD"</span> -┌──┬──┬──┐ -│01│12│23│ -│ab│bc│cd│ -├──┼──┼──┤ -│ab│bc│cd│ -│AB│BC│CD│ -└──┴──┴──┘ +┌─ +╵ ┌─ ┌─ ┌─ + ╵"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 the left argument has length <code><span class='Number'>0</span></code>, then the argument 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 the same as the argument.</p> @@ -44,13 +51,15 @@ cdefg <h2 id="symmetry">Symmetry</h2> <p>Let's look at an earlier example, along with its transpose.</p> <pre> <span class='Brace'>{</span><span class='Bracket'>⟨</span><span class='Value'>𝕩</span><span class='Separator'>,</span><span class='Function'>⍉</span><span class='Value'>𝕩</span><span class='Bracket'>⟩</span><span class='Brace'>}</span><span class='Number'>5</span><span class='Function'>↕</span><span class='String'>"abcdefg"</span> -┌─────┬───┐ -│abcde│abc│ -│bcdef│bcd│ -│cdefg│cde│ -│ │def│ -│ │efg│ -└─────┴───┘ +┌─ +· ┌─ ┌─ + ╵"abcde ╵"abc + bcdef bcd + cdefg cde + ┘ def + efg + ┘ + ┘ </pre> <p>Although the two arrays have different shapes, they are identical where they overlap.</p> <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'>"abcdefg"</span> @@ -67,16 +76,16 @@ cdefg <h2 id="applications">Applications</h2> <p>Windows can be followed up with a reduction on each slice to give a windowed reduction. Here we take running sums of 3 values.</p> <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 +⟨ 8 7 5 8 ⟩ </pre> <p>A common task is to pair elements, with an initial or final element so the total length stays the same. This can also be done with a pairwise reduction, but another good way (and more performant without special support in the interpreter) is to add the element and then use windows matching the original length. Here both methods are used to invert <code><span class='Function'>+</span><span class='Modifier'>`</span></code>, which requires we take pairwise differences starting at initial value 0.</p> <pre> <span class='Function'>-</span><span class='Modifier'>˜´˘</span><span class='Number'>2</span><span class='Function'>↕</span><span class='Number'>0</span><span class='Function'>∾</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 +⟨ 3 2 1 1 ⟩ <span class='Paren'>((</span><span class='Function'>-</span><span class='Modifier'>˜´</span><span class='Function'><</span><span class='Modifier'>˘</span><span class='Paren'>)</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 +⟨ 3 2 1 1 ⟩ </pre> <p>This method extends to any number of initial elements. We can modify the running sum above to keep the length constant by starting with two zeros.</p> <pre> <span class='Paren'>((</span><span class='Function'>+</span><span class='Modifier'>´</span><span class='Function'><</span><span class='Modifier'>˘</span><span class='Paren'>)</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 +⟨ 2 8 8 7 5 8 ⟩ </pre> |