diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/scan.md | 20 |
1 files changed, 16 insertions, 4 deletions
diff --git a/doc/scan.md b/doc/scan.md index ab4b6669..c4e3a3ad 100644 --- a/doc/scan.md +++ b/doc/scan.md @@ -50,7 +50,7 @@ BQN's Scan is ordered differently from Scan in APL. Both include one result for Scan also differs from Fold or Insert in that it never depends on `π½`'s identity element, because scanning over an empty array simply returns that array. -## Examples +## Lists The best-known use of Scan is the [prefix sum](https://en.wikipedia.org/wiki/Prefix_sum) of a list, in which each element of the result is the sum of that element and all the ones before it. With a [shift](shift.md) this can be modified to sum the previous elements only. @@ -92,7 +92,7 @@ A more complicated boolean scan, which depends on the left-to-right ordering, is {Β¬<`'\'=π©}βΈ/ "ab\\\rs\\\\" -### Reverse scan +## 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 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. @@ -109,10 +109,22 @@ The new value is still the right argument to `π½`, even though with the revers {"("βΎπ¨βΎ")π½"βΎπ©}Λ`βΎβ½ "a"βΏ"b"βΏ"c"βΏ"d" -### Higher ranks +## Higher ranks -Scan moves along the [leading axis](leading.md) of `π©`. Results are produced in index order. +Scan moves along the [leading axis](leading.md) of `π©`: vertically, for a table. To apply a scan to later axes, use `Λ` or `β`. Since a scan returns an array with the same shape as its argument, this can't cause an error from differing result cell shapes, unlike Fold or Insert. β’ a β Β―2βΏ0.25βΏ'a'βΏβ βΎ 3βΏ4β₯Β―1βΏ0βΏ1 +` a + +If `π¨` is given, it must have the same shape as a major cell of `π©` (this is why `π¨` needs to be enclosed when `π©` is a list: in general it's an array). Then the first result cell is found by applying `π½` to elements of `π¨` and `βπ©`, and the computation continues as in the one-argument case for remaining cells. + + 3βΏ2βΏ1βΏ0 +` a + +Results are produced in index order. This means that instead of moving along each column in turn, a scan produces the first result cell one element at a time, then the next, and so on. Something like a breadth-first as opposed to depth-first ordering. + +## Definition + +Scan admits a simple recursive definition. `π©` is an array of rank one or more and `π¨`, if given, is an atom or array with shape `1ββ’π©`. The result ``zβπ¨π½`π©`` is an array with the same shape as `π©`. If it has length at least one, `βz` is `βπ©` if `π¨` isn't given and `π¨π½Β¨βπ©` if it is. For `0β€i`, `(i+1)βz` is `(iβz)π½Β¨(i+1)βπ©`. + +The ordering of `π½` application is the natural one for this definition: cells are computed in turn, and each instance of `π½Β¨` goes in index order. |
