From 7c24de80e86c8a7eba9ae3eb4adc64bb93977e33 Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Thu, 1 Jul 2021 19:34:17 -0400 Subject: Finish Scan documentation --- doc/scan.md | 20 ++++++++++++++++---- docs/doc/scan.html | 21 +++++++++++++++++---- 2 files changed, 33 insertions(+), 8 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. diff --git a/docs/doc/scan.html b/docs/doc/scan.html index 64deae85..1f572239 100644 --- a/docs/doc/scan.html +++ b/docs/doc/scan.html @@ -61,7 +61,7 @@

The 1-modifier Scan (`) moves along the first axis of the array 𝕩, building up an array of results by applying 𝔽 repeatedly beginning with 𝕨 or βŠπ•©. It's related to the fold modifiers, and most closely resembles the APL2-style reduction ¨˝, but it traverses the array in forward rather than reverse index order, and includes all intermediate results of 𝔽 in its output instead of just the final one.

BQN's Scan is ordered differently from Scan in APL. Both include one result for each non-empty prefix of 𝕩. In BQN this is a left-to-right fold, so that each new result requires one application of 𝔽. APL uses a right-to-left ordering, which matches with reduction, but requires starting over at the end for each new prefix, except in special cases. If needed, this definition can be obtained with a fold on each prefix except the first (which is empty). In the particular case of -⍀, that nested solution isn't needed: negate odd-indexed elements and then apply +`.

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 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 this can be modified to sum the previous elements only.

↗️
    +` 2β€Ώ4β€Ώ3β€Ώ1
 ⟨ 2 6 9 10 ⟩
@@ -108,7 +108,7 @@
     {Β¬<`'\'=𝕩}⊸/ "ab\\\rs\\\\"
 "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 (`⌾⌽) does the trick.

↗️
    ∨`   0β€Ώ0β€Ώ1β€Ώ0β€Ώ0β€Ώ1β€Ώ0
 ⟨ 0 0 1 1 1 1 1 ⟩
@@ -124,8 +124,8 @@
 ↗️
    {"("βˆΎπ•¨βˆΎ")𝔽"βˆΎπ•©}˜`⌾⌽ "a"β€Ώ"b"β€Ώ"c"β€Ώ"d"
 ⟨ "(a)𝔽(b)𝔽(c)𝔽d" "(b)𝔽(c)𝔽d" "(c)𝔽d" "d" ⟩
 

-
Higher ranks

-
Scan moves along the leading axis of 𝕩. Results are produced in index order.

+
Higher ranks

+
Scan moves along the leading axis 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
 β”Œβ”€                
 β•΅ Β―2 0.25 'a' ∞   
@@ -142,3 +142,16 @@
   ¯2 0.25 '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
+β”Œβ”€              
+β•΅ 1 2.25 'b' ∞  
+  0 2.25 'c' ∞  
+  0 3.25 'b' ∞  
+  1 2.25 'b' ∞  
+               β”˜
+

+
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.

-- 
cgit v1.2.3