From 2afb23928e1984d475cc460e1672e8f6fa0e4dbe Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Wed, 11 Aug 2021 17:21:31 -0400 Subject: Allow clicking on header to get fragment link --- docs/doc/scan.html | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'docs/doc/scan.html') diff --git a/docs/doc/scan.html b/docs/doc/scan.html index 4b168b89..9d881cba 100644 --- a/docs/doc/scan.html +++ b/docs/doc/scan.html @@ -4,7 +4,7 @@ BQN: Scan
(github) / BQN / doc
-

Scan

+

Scan

@@ -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 right-to-left folds, 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 value, because scanning over an empty array simply returns that array.

-

Lists

+

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,7 +124,7 @@
 ↗️
    {"("∾𝕨∾")𝔽"∾𝕩}˜`⌾⌽ "a"‿"b"‿"c"‿"d"
 ⟨ "(a)𝔽(b)𝔽(c)𝔽d" "(b)𝔽(c)𝔽d" "(c)𝔽d" "d" ⟩
 

-
Higher ranks

+
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
 ┌─                
@@ -152,6 +152,6 @@
                ┘
 

 
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

+
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