aboutsummaryrefslogtreecommitdiff
path: root/doc/windows.md
diff options
context:
space:
mode:
authorMarshall Lochbaum <mwlochbaum@gmail.com>2022-06-25 22:20:19 -0400
committerMarshall Lochbaum <mwlochbaum@gmail.com>2022-06-25 22:20:24 -0400
commitc618ade174cc2b4e428457751ad8dd01130c2239 (patch)
tree2c0840b92204d77ec982a6cf7cb6a1e4f738545f /doc/windows.md
parente62c37d34604f6a2293e981d2fd986729e70d2c9 (diff)
Back to editing docs
Diffstat (limited to 'doc/windows.md')
-rw-r--r--doc/windows.md63
1 files changed, 30 insertions, 33 deletions
diff --git a/doc/windows.md b/doc/windows.md
index 379bf644..6c009143 100644
--- a/doc/windows.md
+++ b/doc/windows.md
@@ -2,75 +2,72 @@
# Windows
-In BQN, it's strongly preferred to use functions, and not modifiers, for array manipulation. Functions are simpler as they have fewer moving parts. They are more concrete, since the array results can always be viewed right away. They are easier to implement with reasonable performance as well, since there is no need to recognize many possible function operands as special cases.
+The Windows function returns all slices, or contiguous subarrays, with shape (well, shape prefix) `𝕨` from `𝕩`. It might also be seen as sliding a moving window along `𝕩`.
-The Window function replaces APL's Windowed Reduction, J's more general Infix operator, and Dyalog's Stencil, which is adapted from one case of J's Cut operator.
+This function replaces APL's Windowed Reduction, J's more general Infix operator, and Dyalog APL's Stencil, which is adapted from one case of J's Cut operator. In BQN, it's strongly preferred to use functions, and not modifiers, for array manipulation. Functions are simpler with fewer moving parts, and more concrete, since the array results can always be viewed right away.
-## Definition
+## Basic case
-We'll start with the one-axis case. Here Window's left argument is a number between `0` and `1+≠𝕩`. The result is composed of slices of `𝕩` (contiguous sections of major cells) with length `𝕨`, starting at each possible index in order.
+We'll start with the one-axis case. Here `𝕨` is a number between `0` and `1+≠𝕩`. The result is composed of slices of `𝕩` (contiguous sections of [major cells](array.md#cells)) with length `𝕨`, starting at each possible index in order.
5↕"abcdefg"
There are `1+(≠𝕩)-𝕨`, or `(≠𝕩)¬𝕨`, of these sections, because the starting index must be at least `0` and at most `(≠𝕩)-𝕨`. Another way to find this result is to look at the number of cells in or before a given slice: there are always `𝕨` in the slice and there are only `≠𝕩` in total, so the number of slices is the range [spanned](logic.md) by these two endpoints.
-You can take a slice of an array `𝕩` that has length `l` and starts at index `i` using [Take](take.md) with Drop or [Rotate](reverse.md#rotate): `l↑i↓𝕩` or `l↑iβŒ½π•©`. The [Prefixes](prefixes.md) function returns all the slices that end at the end of the array (`(≠𝕩)=i+l`), and Suffixes gives the slices that start at the beginning (`i=0`). Windows gives yet another collection of slices: the ones that have a fixed length `l=𝕨`. Selecting one cell from its result gives you the slice starting at that cell's index:
+A single slice of an array `𝕩` with length `l` and starting index `i` is `l↑i↓𝕩`, using [Take and Drop](take.md). The [Prefixes](prefixes.md) function returns all the slices that end at the end of the array (`(≠𝕩)=i+l`), and Suffixes gives the slices that start at the beginning (`i=0`). Windows gives yet another collection of slices: the ones that have a fixed length `l=𝕨`. Selecting one cell from its result gives the slice starting at that cell's index:
2⊏5↕"abcdefg"
- 5↑2↓"abcdefg"
-
-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.
-### Multiple dimensions
+ 5↑2↓"abcdefg"
-The above description applies to a higher-rank right argument. As an example, we'll look at two-row slices of a shape `3β€Ώ4` array. For convenience, we will enclose each slice. Note that slices always have the same rank as the argument array.
+Windows differs from Prefixes and Suffixes in that it doesn't add a layer of nesting (it doesn't enclose each slice). This is possible because the slices have a fixed size, so they fit together as cells of an array.
- <βŽ‰2 2↕"0123"∾"abcd"≍"ABCD"
+## Windowed reduction
-Passing a list as the left argument to Windows takes slices along any number of leading axes. Here are all the shape `2β€Ώ2` slices:
+Windows can be followed up with [Insert](fold.md#insert) on each slice to give a windowed reduction or fold. Here we take running sums of 3 values.
- <βŽ‰2 2β€Ώ2↕"0123"∾"abcd"≍"ABCD"
+ +˝˘3↕ ⟨2,6,0,1,4,3⟩
-The slices are naturally arranged along multiple dimensions according to their starting index. Once again the equivalence `i⊏l↕x` ←→ `l↑i↓x` holds, provided `i` and `l` have the same length.
+A common task is to act on windows with an initial or final element so the total length stays the same. When using windows of length 2, the best way to accomplish this is with a [shift](shift.md) `Β«` or `Β»`. If the window length is longer or variable, then a trick with Windows works better: add the elements, and then use windows matching the original length. Here we invert Plus [Scan](scan.md) `` +` ``, which requires we take pairwise differences starting at initial value 0.
-If `𝕨` has length `0`, then `𝕩` 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 `𝕩`, unchanged.
+ -⟜(0»⊒) +` 3β€Ώ2β€Ώ1β€Ώ1
-### More formally
+ (-ΛœΛβ‰ β†•0∾⊒) +` 3β€Ώ2β€Ώ1β€Ώ1
-`𝕩` is an array. `𝕨` is a number, or numeric list or unit, with `𝕨≀○≠≒𝕩`. The result `z` has shape `π•¨βˆΎΒ¬βŸœπ•¨βŒΎ((≠𝕨)βŠΈβ†‘)≒𝕩`, and element `iβŠ‘z` is `π•©βŠ‘Λœ(≠𝕨)(↑+⌾((≠𝕨)βŠΈβ†‘)↓)i`.
+With Windows, we can modify the 3-element running sum from before to keep the length constant by starting with two zeros.
-Using [Group](group.md) we could also write `iβŠ‘z` ←→ `π•©βŠ‘Λœ(π•¨βˆΎβ—‹(β†•βˆ˜β‰ )≒𝕩) +Β΄Β¨βˆ˜βŠ” i`.
+ (+˝≠↕(2β₯Š0)⊸∾) ⟨2,6,0,1,4,3⟩
## Symmetry
-Let's look at an earlier example, along with its [Transpose](transpose.md) (`⍉`).
+Let's look at the first example, paired with its [Transpose](transpose.md) (`⍉`).
- {βŸ¨π•©,β‰π•©βŸ©}5↕"abcdefg"
+ β‹ˆβŸœβ‰ 5↕"abcdefg"
-Although the two arrays have different shapes, they are identical where they overlap.
+Although the two arrays have different shapes, they're identical in the 3Γ—3 region where they overlap.
- ≑○(3β€Ώ3βŠΈβ†‘)βŸœβ‰5↕"abcdefg"
+ ≑○(3β€Ώ3βŠΈβ†‘)βŸœβ‰ 5↕"abcdefg"
-In other words, the i'th element of slice j is the same as the j'th element of slice i: it is the `i+j`'th element of the argument. So transposing still gives a possible result of Windows, but with a different slice length.
+More concretely, the `i`th element of slice `j` is the same as the `j`th element of slice `i`: it's the `i+j`th element of the argument. So transposing still gives a possible result of Windows, but with a different slice length. The two lengths are related by [Span](logic.md), which converts between length and number of slices.
{(5↕𝕩)≑⍉(3↕𝕩)}"abcdefg"
-In general, we need a more complicated transposeβ€”swapping the first set of `≠𝕨` axes with the second set. Note again the use of [Span](logic.md), our slice-length to slice-number converter.
+ (β‰ "abcdefg") Β¬ 3
- {((5β€Ώ6Β¬2β€Ώ2)↕𝕩) ≑ 2β€Ώ3⍉(2β€Ώ2↕𝕩)} ↕5β€Ώ6β€Ώ7
+## Multiple dimensions
-## Applications
+The right argument can have rank more than 1, and it's viewed as a list of major cells following [leading axis](leading.md) principles. As an example, Windows can take two-row slices of a shape `3β€Ώ4` array.
-Windows can be followed up with a [reduction](fold.md#insert) on each slice to give a windowed reduction. Here we take running sums of 3 values.
+ 2↕["0123","abcd","ABCD"]
- +˝˘3↕ ⟨2,6,0,1,4,3⟩
+ <βŽ‰2 2↕["0123","abcd","ABCD"]
-A common task is to act on windows with an initial or final element so the total length stays the same. When using windows of length 2, the best way to accomplish this is with a [shift](shift.md) `Β«` or `Β»`. If the window length is longer or variable, then a trick with Windows works better: add the elements, and then use windows matching the original length. Here we invert Plus [Scan](scan.md) `` +` ``, which requires we take pairwise differences starting at initial value 0.
+In the second version we've enclosed each slice with `<βŽ‰2` for viewingβ€”a slice has rank 2, the same as `𝕩`. Passing a list as the left argument to Windows takes slices along any number of leading axes. Here are all the shape `2β€Ώ2` slices:
- -⟜(0»⊒) +` 3β€Ώ2β€Ώ1β€Ώ1
+ <βŽ‰2 2β€Ώ2↕["0123","abcd","ABCD"]
- (-ΛœΛβ‰ β†•0∾⊒) +` 3β€Ώ2β€Ώ1β€Ώ1
+The slices are naturally arranged along multiple dimensions according to their starting index. Once again the equivalence `i⊏l↕x` ←→ `l↑i↓x` holds, provided `i` and `l` have the same length.
-With Windows, we can modify the 3-element running sum from before to keep the length constant by starting with two zeros.
+If `𝕨` has length `0`, then `𝕩` 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 `𝕩`, unchanged.
- (+˝≠↕(2β₯Š0)⊸∾) ⟨2,6,0,1,4,3⟩
+Here's a more formal definition: `𝕩` is an array. `𝕨` is a number, or numeric list or unit, with `𝕨≀○≠≒𝕩`. The result `z` has shape `π•¨βˆΎΒ¬βŸœπ•¨βŒΎ((≠𝕨)βŠΈβ†‘)≒𝕩`, and element `iβŠ‘z` is `iβŠ‘z` ←→ `π•©βŠ‘Λœ+´¨(π•¨βˆΎβ—‹(β†•βˆ˜β‰ )≒𝕩)βŠ”i`.