diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/README.md | 1 | ||||
| -rw-r--r-- | doc/compose.md | 2 | ||||
| -rw-r--r-- | doc/constant.md | 2 | ||||
| -rw-r--r-- | doc/group.md | 2 | ||||
| -rw-r--r-- | doc/identity.md | 2 | ||||
| -rw-r--r-- | doc/primitive.md | 2 | ||||
| -rw-r--r-- | doc/replicate.md | 2 | ||||
| -rw-r--r-- | doc/reshape.md | 2 | ||||
| -rw-r--r-- | doc/scan.md | 2 | ||||
| -rw-r--r-- | doc/search.md | 2 | ||||
| -rw-r--r-- | doc/selfcmp.md | 2 | ||||
| -rw-r--r-- | doc/under.md | 78 | ||||
| -rw-r--r-- | doc/undo.md | 4 |
13 files changed, 91 insertions, 12 deletions
diff --git a/doc/README.md b/doc/README.md index f0db0011..110482f2 100644 --- a/doc/README.md +++ b/doc/README.md @@ -72,6 +72,7 @@ Primitives: - [Solo, Couple, and Merge: `≍>`](couple.md) - [Take and Drop: `↑`](take.md) - [Transpose: `⍉`](transpose.md) +- [Under: `⌾`](under.md) - [Undo: `⁼`](undo.md) - [Valences: `⊘`](valences.md) - [Windows: `↕`](windows.md) diff --git a/doc/compose.md b/doc/compose.md index c848b9d5..9c8c2106 100644 --- a/doc/compose.md +++ b/doc/compose.md @@ -50,4 +50,4 @@ Another example is `/○⥊`, used to filter elements in a high-rank array. Alon (a<'a') /○⥊ a -Over is closely connected with the Under modifier, which performs all the same steps but then undoes `𝔾` afterwards. +Over is closely connected with the [Under](under.md) modifier, which performs all the same steps but then undoes `𝔾` afterwards. diff --git a/doc/constant.md b/doc/constant.md index 73413a03..55c95f82 100644 --- a/doc/constant.md +++ b/doc/constant.md @@ -23,6 +23,6 @@ When programming with [first-class functions](functional.md), the constant appli M ← - m {𝕨⌾(2⊸⊑) 𝕩} 1‿2‿3‿4 -Here `m` is applied to `2⊑𝕩` even though we want to discard that value. Spelled as `m`, our [context-free grammar](context.md) knows it's a function argument, but this [doesn't affect](../problems.md#syntactic-type-erasure) later usage. Under always applies `𝔽` as a function. The proper definition of the insertion function should use a `˙`, like this: +Here `m` is applied to `2⊑𝕩` even though we want to discard that value. Spelled as `m`, our [context-free grammar](context.md) knows it's a function argument, but this [doesn't affect](../problems.md#syntactic-type-erasure) later usage. [Under](under.md) always applies `𝔽` as a function. The proper definition of the insertion function should use a `˙`, like this: m {𝕨˙⌾(2⊸⊑) 𝕩} 1‿2‿3‿4 diff --git a/doc/group.md b/doc/group.md index aceea8ed..7156c24b 100644 --- a/doc/group.md +++ b/doc/group.md @@ -151,7 +151,7 @@ To avoid including spaces in the result, we should change the result index at ea ' '((⊢-˜¬×+`)∘=⊔⊢)"BQN uses notation as a tool of thought" -A function with structural Under, such as `` {¯1¨⌾(𝕩⊸/)+`𝕩} ``, would also work. +A function with structural [Under](under.md), such as `` {¯1¨⌾(𝕩⊸/)+`𝕩} ``, would also work. 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: diff --git a/doc/identity.md b/doc/identity.md index 5876a885..e8682ea5 100644 --- a/doc/identity.md +++ b/doc/identity.md @@ -26,7 +26,7 @@ The right argument `↕5` could be any length-5 list, as its values aren't used. (⌽↕4) ⊣¨ ↕4‿5 -A more powerful pattern is with dyadic Under (`⌾`): unselected parts of the result will use values from `𝕩`. If `𝔽` is `⊣`, then the selected ones will use values from `𝕨`, merging these arrays together. +A more powerful pattern is with dyadic [Under](under.md) (`⌾`): unselected parts of the result will use values from `𝕩`. If `𝔽` is `⊣`, then the selected ones will use values from `𝕨`, merging these arrays together. "ABCDE" ⊣⌾(0‿1‿1‿0‿0⊸/) "abcde" diff --git a/doc/primitive.md b/doc/primitive.md index f29dea71..a48d6602 100644 --- a/doc/primitive.md +++ b/doc/primitive.md @@ -73,7 +73,7 @@ Glyph | Name(s) | Definition | Description `○` | [Over](compose.md) | `{(𝔾𝕨)𝔽𝔾𝕩}` | Apply `𝔾` to each argument and `𝔽` to the results `⊸` | [Before/Bind](hook.md) | `{(𝔽𝕨⊣𝕩)𝔾𝕩}` | `𝔾`'s left argument comes from `𝔽` `⟜` | [After/Bind](hook.md) | `{(𝕨⊣𝕩)𝔽𝔾𝕩}` | `𝔽`'s right argument comes from `𝔾` -`⌾` | Under | `{𝔾⁼∘𝔽○𝔾}` OR `{(𝔾𝕩)↩𝕨𝔽○𝔾𝕩⋄𝕩}` | Apply `𝔽` over `𝔾`, then undo `𝔾` +`⌾` | [Under](under.md) | `{𝔾⁼∘𝔽○𝔾}` OR `{(𝔾𝕩)↩𝕨𝔽○𝔾𝕩⋄𝕩}` | Apply `𝔽` over `𝔾`, then undo `𝔾` `⊘` | [Valences](valences.md) | `{𝔽𝕩;𝕨𝔾𝕩}` | Apply `𝔽` if there's one argument but `𝔾` if there are two `◶` | [Choose](choose.md) | `{f←(𝕨𝔽𝕩)⊑𝕘 ⋄ 𝕨F𝕩}` | Select one of the functions in list `𝕘` based on `𝔽` diff --git a/doc/replicate.md b/doc/replicate.md index 426b6d2c..66905116 100644 --- a/doc/replicate.md +++ b/doc/replicate.md @@ -39,7 +39,7 @@ Ll ← Line∘⍉ ≍ + (0≍0.05×-○⊑)≍˘0.45‿¯0.55˙ The functions Indices and Replicate are used to copy or filter data. They might be described as transforming a [run-length encoding](https://en.wikipedia.org/wiki/Run-length_encoding) into unencoded form. On the other hand, Indices might be described as giving a sparse representation of `𝕩`, which is smaller if `𝕩` mostly consists of zeros. -BQN doesn't have any of the various features used in APL to add fills to the result of Replicate, like negative numbers in `𝕨` or an Expand (`\`) primitive. An alternative to Expand is to use Replicate with structural Under (`⌾`) to insert values into an array of fills. +BQN doesn't have any of the various features used in APL to add fills to the result of Replicate, like negative numbers in `𝕨` or an Expand (`\`) primitive. An alternative to Expand is to use Replicate with structural [Under](under.md) (`⌾`) to insert values into an array of fills. ## Replicate diff --git a/doc/reshape.md b/doc/reshape.md index fa939ce4..38bbe203 100644 --- a/doc/reshape.md +++ b/doc/reshape.md @@ -131,7 +131,7 @@ Computed Reshape might also be used in actual data processing: for example, to s +´˘ ↑‿4 ⥊ ⟨0,2,1,1, 5,9,6,4, 3,3,3,3, 9,7⟩ -Computed Reshape can even be used with structural Under. Only the `∘` case really makes sense, although `⌊`, which leaves trailing elements unchanged, could conceivably be useful. Below, we split one argument into three groups and [reverse](reverse.md) their order, and reverse groups of three in another. +Computed Reshape can even be used with [structural Under](under.md#structural-under). Only the `∘` case really makes sense, although `⌊`, which leaves trailing elements unchanged, could conceivably be useful. Below, we split one argument into three groups and [reverse](reverse.md) their order, and reverse groups of three in another. ⌽⌾(3‿∘⊸⥊) ↕15 diff --git a/doc/scan.md b/doc/scan.md index 73ce3f0a..f87580e4 100644 --- a/doc/scan.md +++ b/doc/scan.md @@ -94,7 +94,7 @@ A more complicated boolean scan, which depends on the left-to-right ordering, is ## Reverse scan -We've discussed how the scan moves forward along `𝕩`, so that each time `𝔽` takes an old result as `𝕨` and a new value as `𝕩`. This means that results correspond to [prefixes](prefixes.md) and go left to right on each one. Since the most important scans have associative, commutative operands, the left-to-right ordering often doesn't make a difference. But sometimes a suffix rather than prefix scan is wanted. For these cases, Scan Under [Reverse](reverse.md) (`` `⌾⌽ ``) does the trick. +We've discussed how the scan moves forward along `𝕩`, so that each time `𝔽` takes an old result as `𝕨` and a new value as `𝕩`. This means that results correspond to [prefixes](prefixes.md) and go left to right on each one. Since the most important scans have associative, commutative operands, the left-to-right ordering often doesn't make a difference. But sometimes a suffix rather than prefix scan is wanted. For these cases, Scan [Under](under.md) [Reverse](reverse.md) (`` `⌾⌽ ``) does the trick. ∨` 0‿0‿1‿0‿0‿1‿0 diff --git a/doc/search.md b/doc/search.md index 7c0aa7dd..af2c9e7e 100644 --- a/doc/search.md +++ b/doc/search.md @@ -135,7 +135,7 @@ Just as bad, this result has the right information, but is enclosed and could br stuff ⊑∘⊐⟜< "string" -If `𝕨` is fixed, then the version I prefer is to use Under to enclose the argument and then un-enclose the result. It requires `𝕨` to be bound to `⊐` because otherwise Under would enclose `𝕨` as well, since it applies `𝔾` to both arguments. +If `𝕨` is fixed, then the version I prefer is to use [Under](under.md) to enclose the argument and then un-enclose the result. It requires `𝕨` to be bound to `⊐` because otherwise Under would enclose `𝕨` as well, since it applies `𝔾` to both arguments. stuff⊸⊐⌾< "string" diff --git a/doc/selfcmp.md b/doc/selfcmp.md index 967f7974..41114a1d 100644 --- a/doc/selfcmp.md +++ b/doc/selfcmp.md @@ -131,7 +131,7 @@ A more efficient way when `⊒` doesn't have a fast implementation is `` /(¯1 *There's also an [APL Wiki page](https://aplwiki.com/wiki/Unique) on this function.* -Deduplicate removes every major cell from the argument that matches an earlier cell, resulting in an array with the same rank but possibly a shorter length. It might also be described as returning the unique major cells of the argument, ordered by first occurrence. Deduplicate Under Reverse (`⍷⌾⌽`) orders by last occurrence instead. +Deduplicate removes every major cell from the argument that matches an earlier cell, resulting in an array with the same rank but possibly a shorter length. It might also be described as returning the unique major cells of the argument, ordered by first occurrence. Deduplicate [Under](under.md) Reverse (`⍷⌾⌽`) orders by last occurrence instead. ⍷ >"take"‿"drop"‿"drop"‿"pick"‿"take"‿"take" diff --git a/doc/under.md b/doc/under.md index 23f7fe89..b7819f97 100644 --- a/doc/under.md +++ b/doc/under.md @@ -35,3 +35,81 @@ rdim ← 4‿4×d ⟩ ⟩ --> + +The Under 2-modifier expresses the idea of modifying *part* of an array, or applying a function in a different domain, such as working in logarithmic space. It works with a transformation `𝔾` that applies to the original argument `𝕩`, and a function `𝔽` that applies to the result of `𝔾` (and if `𝕨` is given, `𝔾𝕨` is used as the left argument to `𝔽`). Under does the "same thing" as `𝔽`, but to the original argument, by applying `𝔾`, then `𝔽`, then undoing `𝔾` somehow. + +It's not always possible to undo `𝔾`, so only some right operands will work. BQN supports two cases. **Computational** Under tries the [Undo](undo.md) modifier, so that `𝔽⌾𝔾` is `𝔾⁼∘𝔽○𝔾`. + + 3 +⌾(ט) 4 # Square root of sum of squares + +**Structural** Under is used when `𝔾` selects part of the array. BQN tracks what was selected and puts the results from `𝔽` back where they came from. + + +`⌾∾ ⟨3‿1‿0, 2‿5, 0‿0‿6⟩ # Prefix sum, keeping structure + +Structural Under is an essential part of BQN because of how it can "change" an immutable [array](array.md), and it supports more functions and is always well defined. Computational Under's nice, but not so important. The reason they can both be supported as a single primitive is that they follow this unifying principle: + + (𝔾 𝕨𝔽⌾𝔾𝕩) ≡ 𝕨𝔽○𝔾𝕩 + +That is, when you apply `𝔽⌾𝔾` *before* applying `𝔾`, you get the value that comes from applying `𝔽` *after* `𝔾`. The definition of computational under comes from applying `𝔾⁼` to both sides and cancelling `𝔾⁼𝔾`, which solves the constraint but doesn't have to be a unique solution. For structural Under, the reason this works is that `𝔾` selects out the parts of `𝔽⌾𝔾` that were placed back in by Under. Other parts are defined to be the same as it was in `𝕩`, so the result is fully specified. + +## Structural Under + +A *structural function* is one that moves elements around without performing computation on them. It's okay if it performs computation, but it has to be based on the structure of its argument—shape, and element structure—and not on the values of atoms in it. As an example, the function `⊏˘` selects the first column of an array. + + ⊢ a ← 4‿3⥊↕12 + + 1⊸⌽⌾(⊏˘) a + +When used with Under, the function `1⊸⌽` applies to the first column, rotating it. The result of `𝔽` needs to be compatible with the selection function, so Rotate works but trying to remove an element is no good: + + 1⊸↓⌾(⊏˘) a + +BQN can detect lots of structural functions when written in [tacit](tacit.md) form; see the list of functions [in the spec](../spec/inferred.md#required-structural-inverses). You can also include computations on the shape. For example, here's a function to reverse the first half of a list. + + ⌽⌾(⊢↑˜≠÷2˙) "abcdef" + +Under is useful with [scans](scan.md), as discussed in a section on [reverse scan](scan.md#reverse-scan). In this case, `⌽` is exactly invertible, so `⌾` can just as easily be seen as computational Under. When `𝔾` has an exact inverse, there can only be one solution to the constraint on Under, and both forms must be the same. + + ∧`⌾⌽ 1‿0‿1‿0‿1‿1‿1 + +## Computational Under + +Computational Under is based on [Undo](undo.md) (`⁼`), and applies whenever structural Under doesn't. It's still limited, because Undo doesn't work on many or even most functions. One common use is with the square function `ט`, for computations such as finding the magnitude of a vector, or a [root-mean-square](https://en.wikipedia.org/wiki/Root_mean_square) average like the one below. + + (+´÷≠)⌾(ט) 2‿3‿4‿5 + +This average is the square root of the average of the squares of the arguments, and `⌾` lets us combine the two square-y steps. Similarly, `⌾÷` can be used for a harmonic sum or mean (you might notice that computational Under is a lot more mathy than the structural one). + +Under is the idiomatic way to do a round-to-nearest function: + + ⌊⌾(10⊸×) 3.524‿6.799‿2.031 + +See how it works? `⌊` rounds down to an integer, but we can get it to round down to a decimal by first multiplying by 10 (single decimals are now integers), then rounding, then undoing that multiplication. A related idea is to not just round but produce a range. Suppose I want the arithmetic progression 4, 7, 10, ... <20. If I had the right range `↕n`, then it would be `4+3×↕n`, or `(4+3×⊢)↕n`. By using the *inverse* of this transformation function on the desired endpoint, I can make sure it's applied on the way out, and BQN figures out what to do on the way in as if by magic. + + ↕∘⌈⌾((4+3×⊢)⁼) 20 + +Well, really it's a bit of simple algebra, but if it wants to wear a pointy hat and wave a wand around I won't judge. + +## Left argument + +When called dyadically, Under applies `𝔽` dyadically, like [Over](compose.md#over). This doesn't affect the undoing part of Under, which still tries to put the result of `𝔽` back into `𝕩` for structural Under or invert `𝔾` for computational. In fact, `𝕨 𝔽⌾𝔾 𝕩` is equivalent to `(𝔾𝕨)˙⊸𝔽⌾𝔾 𝕩` so no exciting language stuff is happening here at all. + +But you can still do some cool stuff with it! One pattern is simply to set `𝔽` to `⊣`, the [identity](identity.md) function that just returns its left argument. Now structural Under will replace everything that `𝔾` selects from `𝕩` with the corresponding values in `𝕨`. Here's an example that replaces elements with indices `1` and `2`. + + "abcd" ⊣⌾(1‿2⊸⊏) "0123" + +This method can replace deeper structure too. Below, `𝔾` is `¯1⊑¨2↑⊢`, selecting the last element of each of the first two elements of its argument. The elements that aren't selected don't have to match up. + + ⟨"ab", "cde", "fg"⟩ ⊣⌾(¯1⊑¨2↑⊢) ↕¨3‿2‿1‿1 + +In fact, the elements that *are* selected don't really have to match up before being selected. So here's an example with [Join](join.md) where the same pattern is used to "re-flow" `𝕨` into the structure of `𝕩`. + + ⟨"ab", "cde", "fg"⟩ ⊣⌾∾ ⟨"---", "----"⟩ + +### And getting it not to do that + +The Over-based action on `𝕨` shows up more than you might think, but sometimes you just want to pass a left argument to `𝔽` without `𝔾` getting involved. In this case you have to [bind](hook.md#bind) it in: call `𝕨⊸𝔽⌾𝔾 𝕩`. + + 1‿2‿3⊸+⌾(1‿1‿0‿1⊸/) 10‿20‿30‿40 + +This [gets bad](../problems.md#underbind-combination-is-awkward) when you want `𝕨` to be an argument. In the worst case you might need to write out an operator `{𝕨⊸𝔽⌾𝔾𝕩}`. diff --git a/doc/undo.md b/doc/undo.md index 08099e8f..4afa2c00 100644 --- a/doc/undo.md +++ b/doc/undo.md @@ -2,7 +2,7 @@ # Undo -Oh no, you've deleted a function after spending half an hour writing it! Well… hopefully your editor can help with that. But maybe you'll be interested to hear that BQN can reverse the action of some functions—ones that *don't* lose information. This capability is also used by [Repeat](repeat.md) (`⍟`) to repeat a negative number of times. +Oh no, you've deleted a function after spending half an hour writing it! Well… hopefully your editor can help with that. But maybe you'll be interested to hear that BQN can reverse the action of some functions—ones that *don't* lose information. This capability is also used by [Repeat](repeat.md) (`⍟`) to repeat a negative number of times, and [Under](under.md) (`⌾`) in some cases. 2 ⌽ "abcde" @@ -14,7 +14,7 @@ Above is one example of Undo (`⁼`) in action. [Rotate](reverse.md) shifts the Fn⁼ Fn "BQN" -Here it undoes a function to decrement the last character by incrementing that character. In part this is enabled by the clean design of BQN primitives, because better-behaved functions like those using structural Under are easier to invert. +Here it undoes a function to decrement the last character by incrementing that character. In part this is enabled by the clean design of BQN primitives, because better-behaved functions like those using structural [Under](under.md) are easier to invert. ## The rules |