aboutsummaryrefslogtreecommitdiff
path: root/doc
diff options
context:
space:
mode:
authorMarshall Lochbaum <mwlochbaum@gmail.com>2022-07-04 22:25:39 -0400
committerMarshall Lochbaum <mwlochbaum@gmail.com>2022-07-04 22:25:39 -0400
commitdf5ddc0ed2fe48411645228c6e2d596be239a0c6 (patch)
tree3a18a3674130c5aa646ac23106de3570eb03ae8d /doc
parent81c0f0844edeb2a92f6644455c100700cab6c3c8 (diff)
A few edits more
Diffstat (limited to 'doc')
-rw-r--r--doc/fill.md28
-rw-r--r--doc/find.md8
-rw-r--r--doc/fold.md34
3 files changed, 42 insertions, 28 deletions
diff --git a/doc/fill.md b/doc/fill.md
index d330537a..d33c0d85 100644
--- a/doc/fill.md
+++ b/doc/fill.md
@@ -4,19 +4,19 @@
A few array operations need an array element to use when no existing element applies. BQN tries to maintain a "default" element for every array, known as a fill element, for this purpose. If it's known, the fill element is a nested array structure where each atom is either `0` or `' '`. If no fill is known, a function that requests it results in an error.
-Fills are used by [Take](take.md) (`↑`) when a value in `𝕨` is larger than the corresponding length in `𝕩`, by the two [Nudge](shift.md) functions (`»«`) when `𝕩` is non-empty, by [Merge](couple.md) (`>`) when `𝕩` is empty, and by [Reshape](reshape.md) (`⥊`) when `𝕨` contains `↑`. Except for these specific cases, the fill value an array has can't affect the program. The result of [Match](match.md) (`≡`) doesn't depend on fills, and any attempt to compute a fill can't cause side effects.
+Fills are used by [Take](take.md) (`↑`) when a value in `𝕨` is larger than the corresponding length in `𝕩` and [Reshape](reshape.md) (`⥊`) when `𝕨` contains `↑`, by the two [Nudge](shift.md) functions (`»«`) when `𝕩` is non-empty, by [Merge](couple.md) (`>`) and [Join](join.md) when `𝕩` is empty, and by [Cells and Rank](rank.md) when the result has an empty frame. These are the only ways that an array's fill value can affect the program. The result of [Match](match.md) (`≡`) doesn't depend on fills, and any attempt to compute a fill can't cause side effects.
## Using fills
-For the examples in this section we'll use the fact that an all-number array usually has `0` as a fill while a string has `' '` (BQN maintains fills alongside array values rather than deriving them from arrays, so it's possible to construct arrays where this isn't true, but this probably wouldn't happen in ordinary code).
+For the examples in this section we'll use the fact that an all-number array usually has `0` as a fill while a string has `' '` (it's not too rare to end up with such an array that has no fill, and possible but very unusual for an array to have a fill that conflicts with those rules).
-[Take](take.md) (`↑`) and [Nudge](shift.md) (`»«`) in either direction use the fill for padding, to extend the array past its boundary. For example, `𝕨↑𝕩` will add elements to one side when a number in `|𝕨` is larger than the corresponding length in `≢𝕩`.
+[Take](take.md) (`↑`) and [Nudge](shift.md) (`»«`) in either direction use the fill for padding, to extend the array past its boundary. For example, `𝕨↑𝕩` adds elements to one side if a number in `|𝕨` is larger than the corresponding length in `≢𝕩`.
¯7 ↑ 4⥊3 # Fill with 0
¯7 ↑ "qrst" # Fill with space
-Nudge Left or Right shifts the array over and places a fill in the vacated space, effectively extending it backwards by one. If `𝕩` is empty then it shouldn't give an error, but it's safer not to rely on this.
+Nudge Left or Right shifts the array over and places a fill in the vacated space. If `𝕩` is empty then it doesn't need the fill and can't error.
»¨ ⟨4⥊3,"qrst"⟩
@@ -24,8 +24,6 @@ Nudge Left or Right shifts the array over and places a fill in the vacated space
»⟨⟩ # Fill not needed
-If the argument to [Merge](couple.md) is empty then its result will be as well, since the shape `≢𝕩` is a prefix of `≢>𝕩`. However, the remainder of the result shape is determined by the elements of `𝕩`, so if there are none then Merge uses the fill element to decide what the result shape should be.
-
[Reshape](reshape.md#computed-lengths) (`⥊`) uses the fill when `𝕨` contains `↑` and the product of the rest of `𝕨` doesn't evenly divide the number of elements in `𝕩`.
↑‿8 ⥊ "completepart"
@@ -34,19 +32,33 @@ If for some reason you need to find an array's fill element, the easiest general
⊑»1↑⥊"string"
+## Edge cases
+
+The above functions use the fill as part of their core definition. A few other functions use fills only when they encounter empty arrays. The goal of this behavior is to make programs working on empty arrays more similar to the non-empty case, so if all goes well you don't need to be thinking about these cases.
+
+If the argument to [Merge](couple.md) is empty then its result will be as well, since the shape `≢𝕩` is a prefix of `≢>𝕩`. However, the remainder of the result shape is determined by the elements of `𝕩`, so if there are none then Merge uses the fill element to decide what the result shape should be. [Join](join.md) is similar, although it multiplies the shape of `𝕩` by the leading shape of the fill instead of concatenating them.
+
+ ≢ > 2‿0⥊<3‿4‿1⥊0
+
+ ≢ ∾ 2‿0⥊<3‿4‿1⥊0
+
+[Cells and Rank](rank.md) rely on fills in a slightly more complicated way. If one of the argument frames is empty, that means the result will be empty, but the shape of a result cell still needs to be known to determine its shape (and similarly for the fill, but that's optional). BQN implementations may try to find it by running `𝔽` using a cell of fills for the argument. As in Each (`¨`) described below, this evaluation is not allowed to produce side effects. If it doesn't work, the result cell shape is assumed to be `⟨⟩`.
+
+ ≢ ⌽˘ ↕0‿4‿3 # Shape is determined by fills
+
## How fills are computed
For the exact requirements placed on fill, see [the specification](../spec/inferred.md#fill-elements) (particularly "required functions"). This section loosely describes behavior in existing BQN implementations, and includes some parts that aren't required in the specification.
A fill element should encompass something that's necessarily true for all elements of an array. If the way an array is computed implies it's all numbers, the fill should be `0`. If every element is a list of two numbers, then the fill should be `⟨0,0⟩`. If every element is a list but the lengths might vary, `⟨⟩` is probably a reasonable fill element.
-For [arithmetic](arithmetic.md) primitives, the fill is found by the rules of pervasion, applying the function to both argument fills. Generally this means it consists of `0`, but character arithmetic also allows space fills.
+For [arithmetic](arithmetic.md) primitives, the fill is found by the rules of pervasion, applying the function to both argument fills. Generally this means it consists of `0`, but [character arithmetic](arithmetic.md#character-arithmetic) can produce space for a fill value.
» "abc" + 4‿3‿2
[Mapping](map.md) modifiers Each and Table (`¨⌜`) might try to follow a similar strategy, applying `𝔽` to argument fills to obtain the result fill. The absolute rule here is that this computation can't cause side effects or an error, so for a complicated `𝔽` such as a block function this procedure is likely to be aborted to avoid disrupting the rest of the program.
-Most other primitives fit in one of three broad categories as shown in the table below. Structural primitives, indicated by `⊢`, don't change the fill of `𝕩`. Combining structural primitives, indicated by `∩`, only depend on the fill of all combined arrays—elements of `𝕩` in the one-argument case, or `𝕨` and `𝕩` in the two-argument case. Finally, many functions such as [search functions](search.md) return only numbers and have a fill of `0`.
+Most other primitives fit in one of three broad categories as shown in the table below. Structural primitives, indicated by `⊢`, don't change the fill of `𝕩`. Combining structural primitives, indicated by `∩`, only depend on the fill of all combined arrays—elements of `𝕩` in the one-argument case, or `𝕨` and `𝕩` in the two-argument case. If these fills are the same value, then that's the fill; otherwise, the result has no fill. Finally, many functions such as [search functions](search.md) return only arrays of numbers and have a fill of `0`.
| Fill | Monads | Dyads | Modifiers
|--------|--------------|-------------|----------
diff --git a/doc/find.md b/doc/find.md
index 5309909f..6958365a 100644
--- a/doc/find.md
+++ b/doc/find.md
@@ -6,7 +6,7 @@ Find (`⍷`) searches for occurrences of an array `𝕨` within `𝕩`. The resu
"xx" ⍷ "xxbdxxxcx"
-More precisely `𝕨` needs to [match](match.md) a contiguous selection from `𝕩`, which for strings means a substring. These subarrays of `𝕩` are also exactly the cells in the result of [Windows](windows.md). In fact we can use Windows to see all the arrays `𝕨` will be compared against.
+More precisely, `𝕨` needs to [match](match.md) a contiguous selection from `𝕩`, which for strings means a substring. These subarrays of `𝕩` are also exactly the cells in the result of [Windows](windows.md). So we can use Windows to see all the arrays `𝕨` will be compared against.
2 ↕ "xxbdxxxcx"
@@ -18,7 +18,7 @@ Like Windows, the result usually doesn't have the same dimensions as `𝕩`. Thi
"string" (≢∘⊢↑⍷) "substring" # APL style
-If `𝕨` is larger than `𝕩`, the result is empty, and there's no error even in cases where Windows would fail. One place this tends to come up is when applying [First](pick.md#first) (`⊑`) the result: `⊑⍷` tests whether `𝕨` appears in `𝕩` at the first position, that is, whether it's a prefix of `𝕩`. If `𝕨` is longer than `𝕩` it shouldn't be a prefix. First will fail but using a [fold](fold.md) `0⊣´⥊∘⍷` instead gives a 0 in this case.
+If `𝕨` is larger than `𝕩`, the result is empty, and there's no error even in cases where Windows would fail. One place this tends to come up is when applying [First](pick.md#first) (`⊑`) to the result: `⊑⍷` tests whether `𝕨` appears in `𝕩` at the first position, that is, whether it's a prefix of `𝕩`. If `𝕨` is longer than `𝕩` it shouldn't be a prefix. First will fail but using a [fold](fold.md) `0⊣´⍷` instead gives a 0 in this case.
"loooooong" ⍷ "short"
@@ -26,7 +26,7 @@ If `𝕨` is larger than `𝕩`, the result is empty, and there's no error even
0 ⊣´ "loooooong" ⍷ "short"
-This pattern also works in the high-rank case discussed below, testing whether `𝕨` is a multi-dimensional prefix starting at the lowest-index corner of `𝕩`.
+Adding a [Deshape](reshape.md#deshape) gives `0⊣´⥊∘⍷`, which works with the high-rank case discussed below. It tests whether `𝕨` is a multi-dimensional prefix starting at the lowest-index corner of `𝕩`.
### Higher ranks
@@ -36,6 +36,6 @@ If `𝕨` and `𝕩` are two-dimensional then Find does a two-dimensional search
(0‿3‿0≍0‿1‿0) ⍷ a
-It's also allowed for `𝕨` to have a smaller rank than `𝕩`; in this case leading axes of `𝕩` are mapped over so that axes of `𝕨` correspond to trailing axes of `𝕩`. This is a minor violation of the [leading axis](leading.md) principle, which would match axes of `𝕨` to leading axes of `𝕩` in order to make a function that's useful with the Rank operator, but such a function would be quite strange and hardly ever useful.
+It's also allowed for `𝕨` to have a smaller rank than `𝕩`; the axes of `𝕨` then correspond to trailing axes of `𝕩`, so that leading axes of `𝕩` are mapped over. This is a minor violation of the [leading axis](leading.md) principle, which would match axes of `𝕨` to leading axes of `𝕩` in order to make a function that's useful with the Rank operator, but such a function would be quite strange and hardly ever useful.
0‿1‿0‿1 ⍷ a
diff --git a/doc/fold.md b/doc/fold.md
index 2cd7fdb7..cbd05ff9 100644
--- a/doc/fold.md
+++ b/doc/fold.md
@@ -48,7 +48,7 @@ lp ← 0.35
The closely related 1-modifiers Fold (`´`) and Insert (`˝`) apply a dyadic operand function `𝔽` repeatedly between elements or major cells of `𝕩`. Neither is quite like the APL2-style Reduce operator (`/` or `⌿` in APL), although I sometimes use the term "reduction" to mean either Fold or Insert. There are a bunch of other names like "accumulate" and "aggregate" for this class of calculations—I don't know which is best but I know "catamorphism" is worst.
-A distinguishing feature of APL-family reductions is that they don't use an initial value, and try to derive an "identity element" from the operand if the argument array is empty. BQN retains this capability but also allows the programmer to supply an initial value as `𝕨`.
+A distinguishing feature of APL-family reductions is that they don't use an initial value, and try to derive an "identity element" for `𝔽` if the argument array is empty. BQN retains this capability but also allows the programmer to supply an initial value as `𝕨`.
## Fold
@@ -57,7 +57,7 @@ As its glyph suggests, Fold is slightly simpler than Insert. The argument `𝕩`
+´ 2‿4‿3‿1
+´ ⟨2‿4, 3‿1⟩
-Any function can be used as an operand. With Maximum (`⌈`) you can find the largest number out of an entire list, and likewise for Minimum (`⌊`).
+Any function can be used as an operand. You can find the largest number out of an entire list with Maximum (`⌈`), or the smallest with Minimum (`⌊`).
⌈´ 2‿4‿3‿1
⌊´ 2‿4‿3‿1
@@ -80,7 +80,7 @@ Folding over a list of two values applies `𝔽` once, since `𝔽` is always ca
⌈´ ⟨⟩ # The smallest number
∧´ ⟨⟩ # All the elements in the list are true…
-The full list of identity values Fold has to use is shown below.
+Here's the full list of identity values Fold has to support.
| Id | Fn | Fn | Id |
|-----:|:---:|:---:|-----:|
@@ -100,7 +100,7 @@ The functions we've shown so far are associative (ignoring floating point imprec
'a' ⋈ 'b' ⋈ 'c' ⋈ 'd' # Expanded form
-Using [Pair](pair.md) (`⋈`) as an operand shows the structure nicely. This fold first pairs the final two characters `'c'` and `'d'`, then pairs `'b'` with that and so on. This matches BQN's right-to-left order of evaluation. More declaratively we might say that each character is paired with the result of folding over everything to its right.
+[Pair](pair.md) (`⋈`) as an operand shows the structure nicely. This fold first pairs the final two characters `'c'` and `'d'`, then pairs `'b'` with that and so on. This matches BQN's right-to-left order of evaluation. More declaratively we might say that each character is paired with the result of folding over everything to its right.
BQN doesn't provide a left Fold (`` ` `` is [Scan](scan.md)). However, you can fold from the left by [reversing](reverse.md#reverse) (`⌽`) the argument list and also reversing (`˜`) the operand function's argument order.
@@ -110,13 +110,13 @@ One consequence of this ordering is that folding with Minus (`-`) gives an alter
-´ 30‿1‿20‿2‿10
-The operand `+⟜÷` is a quick way to compute a [continued fraction](https://en.wikipedia.org/wiki/Continued_fraction)'s value from a list of numbers. Here are a few terms from the continued fraction for *e*.
+And the operand `+⟜÷` is a quick way to compute a [continued fraction](https://en.wikipedia.org/wiki/Continued_fraction)'s value from a list of numbers. Here are a few terms from the continued fraction for *e*.
+⟜÷´ 2‿1‿2‿1‿1‿4‿1‿1
### Initial element
-When the operand isn't just an arithmetic primitive, folding with no initial element can be dangerous. Even if you know `𝕩` isn't empty, saving you from an "Identity not found" error, the case with only one element can easily violate expectations. Here's a somewhat silly example of a function meant to merge elements of the argument into a single list (`∾⥊¨` is a much better way to do this):
+When `𝔽` isn't just an arithmetic primitive, folding with no initial element can be dangerous. Even if you know `𝕩` isn't empty, saving you from an "Identity not found" error, the case with only one element can easily violate expectations. Here's a somewhat silly example of a function meant to merge elements of the argument into a single list (`∾⥊¨` is a much better way to do this):
∾○⥊´ ⟨2‿4≍6‿8,"abcd",0⟩
@@ -126,11 +126,11 @@ When the operand isn't just an arithmetic primitive, folding with no initial ele
The result always has rank 1, until the one-element case, when `∾○⥊` is never applied and can't deshape anything. Using Fold with lots of complex operands and no initial element can make a program fragile.
-However, it's easy to specify an initial element for Fold: simply pass it as `𝕨`. Because `𝕨` behaves like an element of `𝕩`, it doesn't need to be enclosed and will usually have one smaller depth. For `∾○⥊` the natural starting element for a fold that returns a list is the empty list.
+The left argument, if given, is the initial right argument to `𝔽`. This puts `𝕨` on the same level as an element of `𝕩`, so it doesn't need to be enclosed and will usually have one smaller depth. For `∾○⥊´` the natural starting element is the empty list.
⟨⟩ ∾○⥊´ ⟨2‿4≍6‿8⟩
-The initial element is used in the first function application, so it behaves as though it's added to the end of the list (`∾⟜<˜` would accomplish this as well).
+With a non-empty `𝕨` we can see it's placed at the end of the result list, because it's passed to `𝔽` before any elements of `𝕩`.
"end" ∾○⥊´ ⟨"start","middle"⟩
@@ -146,22 +146,22 @@ Fold only works on lists. What if you want to, say, sum the columns of a table?
+˝ tab
-The Insert (`˝`) modifier will do this for you. Because it works on the [leading axis](leading.md) of the argument, Insert can be applied to axes other than the first with Rank. Sum each row (second axis) with `˘`, for example.
+The Insert (`˝`) modifier will do this for you. And because it works on the [leading axis](leading.md) of the argument, Insert can be applied to axes other than the first with Rank. Sum each row (second axis) with [Cells](rank.md#cells) (`˘`), for example.
+˝˘ tab
-This case is tricky, because `+´˘ tab` yields the same result but is actually unsound—if `tab` contains arrays then they will be merged together at the end. Remember that if you want to reduce along one axis of an array but get an array of results out, you should use Insert (possibly adding Each to work on elements instead of cells; see [APL2 reduction](#apl2-reduction) below).
+This case is tricky, because `+´˘ tab` yields the same result but is actually unsound—if `tab` contains arrays then they will be merged together at the end. Remember: if you want to reduce along one axis of an array and get an array of results out, you should use Insert (possibly adding Each to work on elements instead of cells; see [APL2 reduction](#apl2-reduction) below).
A function with Insert `𝔽˝` is nearly equivalent to `𝔽´<˘` (and both fail on unit arguments, because there's no axis to apply along). Besides being more convenient, `𝔽˝` is a little safer because it takes the argument shape into account when returning an identity value:
+´<˘ 0‿4⥊0
+˝ 0‿4⥊0
-Just like Fold, Insert allows an initial element for the left argument, so that you don't need to rely on the interpreter knowing the identity. A more complete translation into Fold is therefore `{𝕨𝔽´<˘𝕩}`. The expression below shows that the operand function is called on the last major cell when the identity, then the next-to-last major cell and so on. In total there are `≠𝕩` calls, while there would be `1-˜≠𝕩` without the left argument.
+Just like Fold, Insert allows an initial element for the left argument, so that you don't need to rely on the interpreter knowing the identity (in Fold terms it's `{𝕨𝔽´<˘𝕩}`). Below, we see that `𝔽` is called on the last major cell and `𝕨`, then the next-to-last major cell and so on. This makes `≠𝕩` calls, while there would be `1-˜≠𝕩` without the initial value.
- "id" ⋈˝ "row0 "∾"row1 "≍"row2 "
+ "id" ⋈˝ ["row0 ","row1 ","row2 "]
-One trick involving Insert is `∾˝`, which merges the first two axes of `𝕩` into one long axis. It even works on empty arrays, because BQN knows that there's only one result shape that makes sense (in contrast to `∾´⟨⟩`, where many results sometimes work but none of them always work).
+One trick involving Insert is `∾˝`, which uses [Join to](join.md#join-to) to merge the first two axes of `𝕩` into one long axis. It even works on empty arrays, because BQN knows that there's only one result shape that makes sense (unlike `∾´⟨⟩`, where many results sometimes fit but none of them always fit).
⊢ let ← ("AHW"-'A') +⌜ "aA" +⌜ ↕4
@@ -175,13 +175,15 @@ As a historical note, Insert is named after J's adverb `/`, which comes from SHA
## APL2 reduction?
-If you try an expression like `⍪⌿` in Dyalog APL, you'll get results very different from BQN's `∾˝`. Instead of combining the cells like we see above, APL applies the function on pairs of *elements* much like Fold. The difference is that, because reduction happens only along one axis but an array might have other axes, there can be multiple values in the result, so that it will always be an array like the argument. BQN can perform this operation as well: `⍪⌿` is written `∾¨˝` in BQN.
+The function `⍪⌿` in Dyalog APL gives very different results from BQN's `∾˝`. Instead of combining the cells like we see above, APL applies the function on pairs of *elements* much like Fold. The difference is that, because reduction happens only along one axis but an array might have other axes, there can be multiple values in the result, so that it will always be an array like the argument. BQN can perform this operation as well: `⍪⌿` is written `∾¨˝` in BQN (but please use `<˘⍉` instead).
+
+ tab
∾¨˝ tab
-This kind of reduction has an interesting property that the other two lack: it always removes exacly one axis, so that the result's shape is the argument's major cell shape. When applied to a later axis using the Rank or Cells modifier, it removes that axis instead.
+This kind of reduction has an interesting property not found in `´` or `˝`: it always removes exactly one axis, so that the result's shape is `𝕩`'s major cell shape. When applied to a later axis using [Rank or Cells](rank.md), it removes that axis instead.
- ≢ ∾¨˝ ↕4‿2‿3 # Reduce out the first axis
+ ≢ ∾¨˝ ↕4‿2‿3 # Reduce out the first axis
≢ ∾¨˝˘ ↕4‿2‿3 # Reduce out the second
When the operand is an arithmetic function, say `⌊`, APL2-style reduction is no different from Insert: `⌊¨˝` is the same as `⌊˝`, because `⌊¨` and `⌊` are the same on arrays. That means that Insert with an arithmetic operand also has this axis-removing property.