Scan

From APL Wiki
Jump to navigation Jump to search
\ ⍀

Scan (\, ⍀) is a primitive monadic operator which takes a dyadic function operand and produces a monadic function which is equivalent to the reductions of the prefixes of the arguments. This operation is known as also known as cumulative reduction.

Explanation

Scan is similar to Reduce, however all the intermediate results will be retained. That being said, unlike Reduce, Scan does not reduce the rank of its argument, i.e. performing a scan over an N-dimensional array will produce an N-dimensional array.

Examples

      +\⍳5 ⍝ plus-scan over range of integers from 1 to 5
1 3 6 10 15

Applications

Removing disconnected trailing 1s from a boolean mask: 

      mask←1 1 1 1 0 1 1 0 0 1
      mask
1 1 1 1 0 1 1 0 0 1
      ∧\mask ⍝ and-scan mask
1 1 1 1 0 0 0 0 0 0

The scan +\ may be used to find parenthesis nesting level and ≠\ to mark quoted strings.

Ordering

Following APL's definition as a collection of reductions, the total number of function applications to evaluate Scan on a vector of length n is , specifically (n×n-1)÷2 or 2!n. Because of the use of right-to-left Reduce over prefixes of a vector, which extend from left to right, there is no way to combine these applications in general, so that many applications of Scan have quadratic complexity. If the wanted directions were the same (reduction on suffixes or left-to-right reduction on prefixes) then Scan could easily be defined to call the operand only n-1 times by reusing the result of each reduction. Because the two reduction orderings are equivalent for an associative operand, APL implementations frequently optimize using this form for common operands such as + and ≠.

Array languages K and Uiua, and APL dialect Kap, use a left-to-right reduction, which naturally gives linear evaluation on prefixes. dzaima/APL and BQN keep APL's right-to-left reduction but redefine Scan to evaluate linearly left to right. J defines operators to apply on prefixes and suffixes, so that the programmer can reduce on suffixes for linear evaluation, while TinyAPL provides both operators as well as a choice of left-to-right or right-to-left reduction, allowing linear scans in either direction.

External links

Lessons

Documentation


APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic Conjugate ∙ Negate ∙ Signum ∙ Reciprocal ∙ Magnitude ∙ Exponential ∙ Natural Logarithm ∙ Floor ∙ Ceiling ∙ Factorial ∙ Not ∙ Pi Times ∙ Roll ∙ Type ∙ Imaginary ∙ Square Root ∙ Round
Dyadic Add ∙ Subtract ∙ Times ∙ Divide ∙ Residue ∙ Power ∙ Logarithm ∙ Minimum ∙ Maximum ∙ Binomial ∙ Comparison functions ∙ Boolean functions (And, Or, Nand, Nor) ∙ GCD ∙ LCM ∙ Circular ∙ Complex ∙ Root
Non-Scalar
Structural Shape ∙ Reshape ∙ Tally ∙ Depth ∙ Ravel ∙ Enlist ∙ Table ∙ Catenate ∙ Reverse ∙ Rotate ∙ Transpose ∙ Raze ∙ Mix ∙ Split ∙ Enclose ∙ Nest ∙ Cut (K) ∙ Pair ∙ Link ∙ Partitioned Enclose ∙ Partition
Selection First ∙ Pick ∙ Take ∙ Drop ∙ Unique ∙ Identity ∙ Stop ∙ Select ∙ Replicate ∙ Expand ∙ Set functions (Intersection ∙ Union ∙ Without) ∙ Bracket indexing ∙ Index ∙ Cartesian Product ∙ Sort
Selector Index generator ∙ Grade ∙ Index Of ∙ Interval Index ∙ Indices ∙ Deal ∙ Prefix and suffix vectors
Computational Match ∙ Not Match ∙ Membership ∙ Find ∙ Nub Sieve ∙ Encode ∙ Decode ∙ Matrix Inverse ∙ Matrix Divide ∙ Format ∙ Execute ∙ Materialise ∙ Range ∙ Count In
Operators Monadic Each ∙ Commute ∙ Constant ∙ Replicate ∙ Expand ∙ Reduce ∙ Windowed Reduce ∙ Scan ∙ Outer Product ∙ Key ∙ I-Beam ∙ Spawn ∙ Function axis ∙ Identity (Null, Ident)
Dyadic Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator) ∙ Identity (Lev, Dex)
Quad names Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector
Retrieved from ‘https://aplwiki.com/index.php?title=Scan&oldid=12494’