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 --- docs/doc/scan.html | 21 +++++++++++++++++---- 1 file changed, 17 insertions(+), 4 deletions(-) (limited to 'docs/doc') 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