diff options
| author | Marshall Lochbaum <mwlochbaum@gmail.com> | 2021-07-16 18:23:52 -0400 |
|---|---|---|
| committer | Marshall Lochbaum <mwlochbaum@gmail.com> | 2021-07-16 18:24:01 -0400 |
| commit | 2010e8b2897a5741e211980c9f8ec9177299c939 (patch) | |
| tree | 4b3476744be928724da2fd5d83b0bf2e9a8ba502 /doc/shift.md | |
| parent | e3366f9e18a8791c43110e080b9ea45cfceefed8 (diff) | |
Finish links and editing documentation pass
Diffstat (limited to 'doc/shift.md')
| -rw-r--r-- | doc/shift.md | 24 |
1 files changed, 15 insertions, 9 deletions
diff --git a/doc/shift.md b/doc/shift.md index 13c388cc..d20d4eff 100644 --- a/doc/shift.md +++ b/doc/shift.md @@ -2,9 +2,9 @@ # Shift functions -The shift functions `«` and `»` are two new primitives added to BQN based on a pattern used heavily in the compiler and a reasonable amount everywhere else. Shifts resemble but are more general than the bit-based shift operations used in low-level languages. They replace the APL pattern of a 2-wise reduction after appending or prepending an element (APL's `2≠/0,v` translates to `»⊸≠v`), one of the more common uses of 2-wise reduction. +The shift functions `«` and `»` add major cells to one side an array, displacing cells on the opposite side and moving those in between. Shifts resemble but are more general than the bit-based shift operations used in low-level languages. They replace the APL pattern of a 2-wise reduction after appending or prepending an element (APL's `2≠/0,v` translates to `»⊸≠v`), one of the more common uses of 2-wise reduction. -The result of a shift function always has the same shape as its right argument. The function adds major cells to the beginning (`»`) or end (`«`) of `𝕩`, moving the cells already in `𝕩` to accomodate them. Some cells on the opposite side from those added will "fall off" and not be included in the result. +The result of a shift function always has the same shape as `𝕩`. The function adds major cells to the beginning (`»`) or end (`«`) of `𝕩`, moving the cells already in `𝕩` to accomodate them. Some cells on the opposite side from those added will "fall off" and not be included in the result. 0‿0 » 3‿2‿1 # Shift Before "end" « "add to the " # Shift After @@ -18,7 +18,7 @@ If `𝕨` is longer than `𝕩`, some cells from `𝕨` will be discarded, as we ## Sequence processing with shifts -When working with a sequence of data such as text, daily measurements, or audio data, shift functions are generally the best way to handle the concept of "next" or "previous" in the data. In the following example `s` is shown alongside the shifted-right data `»s`, and each element is compared to the previous with `-⟜»`, which we see is the inverse of `` +` ``. +When working with a sequence of data such as text, daily measurements, or audio data, shift functions are generally the best way to handle the concept of "next" or "previous". In the following example `s` is shown alongside the shifted-right data `»s`, and each element is compared to the previous with `-⟜»`, which we see is the inverse of Plus [Scan](scan.md) `` +` ``. s ← 1‿2‿2‿4‿3‿5‿6 s ≍ »s @@ -29,6 +29,7 @@ When working with a sequence of data such as text, daily measurements, or audio In this way `»` refers to a sequence containing the previous element at each position. By default the array's fill is used for the element before the first, and a right argument can be given to provide a different one. ∞ » s + ⊏⊸» s It may appear backwards that `»`, which typically means "go to the next item", is used to represent the previous item. In fact there is no conflict: the symbol `»` describes what position each cell of `𝕩` will have in the result, but in this context we are interested in knowing what argument value occurs in a particular result position. By moving all numbers into the future we ensure that a number in the present comes from the past. To keep your intuition functioning in these situations, it may help to think of the arrow point as fixed at some position in the result while the tail stretches back to land on the argument position where it comes from. @@ -64,15 +65,17 @@ With a number in big-endian format, a right shift might be logical, shifting in ## Other examples -In Take (`↑`), there's no way to specify the fill element when the result is longer than the argument. To take along the first axis with a specified, constant fill value, you can use Shift Before instead, where the right argument is an array of fills with the desired final shape. +In [Take](take.md) (`↑`), there's no way to specify the fill element when the result is longer than the argument. To take along the first axis with a specified, constant fill value, you can use Shift Before instead, where the right argument is an array of fills with the desired final shape. "abc" » 5⥊'F' -When using Scan (`` ` ``), the result at a particular index is obtained from values up to and including the one at that index. But it's common to want to use the values up to but not including that one instead. This can be done either by joining or shifting in that value before scanning. The difference is that with Join the result is longer than the argument. Either form might be wanted depending on how it will be used. +When using [Scan](scan.md) (`` ` ``), the result at a particular index is obtained from values up to and including the one at that index. But it's common to want to use the values up to but not including that one instead. This can be done either by [joining](join.md#join-to) or shifting in that value before scanning. The difference is that with Join the result is longer than the argument. Either form might be wanted depending on how it will be used. + + 2 +` 1‿0‿1‿0 # Initial value not retained + + 2 +`∘∾ 1‿0‿1‿0 # All values - +` 1‿1‿1‿1 - 2 +`∘∾ 1‿1‿1‿1 - 2 +`∘» 1‿1‿1‿1 + 2 +`∘» 1‿0‿1‿0 # Final value not created The *strides* of an array are the distances between one element and the next along any given axis. It's the product of all axis lengths below that axis, since these are all the axes that have to be "skipped" to jump along the axis. The strides of an array `𝕩` are `` (×`1»⊢)⌾⌽∘≢𝕩 ``. @@ -83,14 +86,17 @@ The *strides* of an array are the distances between one element and the next alo Shifting always works on the first axis of `𝕩` (which must have rank 1 or more), and shifts in major cells. A left argument can have rank equal to `𝕩`, or one less than it, in which case it becomes a single cell of the result. With no left argument, a cell of fills `1↑0↑𝕩` is nudged in. ⊢ a ← ⥊⟜(↕×´) 4‿3 + » a # Nudge adds a cell of fills + "one" « a # Shift in a cell + ("two"≍"cel") « a # Shift in multiple cells ## Definition In any instance of `»` or `«`, `𝕩` must have rank at least 1. -For a dyadic shift function, `𝕨` must be Join-compatible with `𝕩` (that is, `𝕨∾𝕩` completes without error) and cannot have greater rank than `𝕩`. Then Shift Before (`»`) is `{(≠𝕩)↑𝕨∾𝕩}` and Shift After (`«`) is `{(-≠𝕩)↑𝕩∾𝕨}` +For a dyadic shift function, `𝕨` must be [Join](join.md#join-to)-compatible with `𝕩` (that is, `𝕨∾𝕩` completes without error) and cannot have greater rank than `𝕩`. Then Shift Before (`»`) is `{(≠𝕩)↑𝕨∾𝕩}` and Shift After (`«`) is `{(-≠𝕩)↑𝕩∾𝕨}` When called monadically, the default argument is a cell of fills `1↑0↑𝕩`. That is, Nudge (`»`) is `(1↑0↑⊢)⊸»` and Nudge Back (`«`) is `(1↑0↑⊢)⊸«`. This default argument always satisfies the compatibility requirement above and so the only conditions for nudge are that `𝕩` has rank at least 1 and has a fill element. |
