This is a read-only-page

These operators where posted by John Scholes on November the 4th 2006 on Dyalog's web site:

array ← {ascan} (fn ##.ascana) array ⍝ Associative higher rank scan.

Provided by Phil Last and Nicolas Delcros, these operators out-perform their primitive counterparts by scanning cumulatively from left to right.

The primitive scan operator is defined as a vector of reductions:

For example:

→ +/¨(1 to 5)↑¨⊂3 1 4 1 6 → +/¨(3)(3 1)(3 1 4)(3 1 4 1)(3 1 4 1 6) → (+/3)(+/3 1)(+/3 1 4)(+/3 1 4 1)(+/3 1 4 1 6) → 3 4 8 9 15

Defn: An associative dyadic function f is one where: (A f B) f C ←→ A f (B f C).

For associative operand functions, such as + and ×, the interpreter can "cheat" by accumulating the result in a single left-to-right pass of the vector argu- ment, but for non-associative functions, it is obliged to do it the slow way us- ing reductions of increasingly longer sequences as above, resulting in an O(n×n) algorithm.

Mscan and dscan provide linear O(n) functions to simulate -\ and ÷\ respective- ly.

1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...

1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...

1 0.5 1.5 0.375 1.875 0.3125 ...

1 0.5 1.5 0.375 1.875 0.3125 ...

In general, the interpreter can "cheat" only if it can determine that scan's op- erand function is associative. For example, even though dfn {⍺+⍵} is clearly as- sociative, the interpreter cannot know this and so uses the slow O(n×n) method.

In cases such as these, where it is known that the operand function is associat- ive, ascan can be used to force a left-to-right cumulative O(n) scan.

1 3 6 10 15 21 28 36 45 55 ...

1 3 6 10 15 21 28 36 45 55 ...

Note that if the operand turns out to be non-associative, ascan will return a result that differs from primitive scan.

1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5

1 ¯1 ¯4 ¯8 ¯13 ¯19 ¯26 ¯34 ¯43 ¯53

┌→──┬───────┬───────────────┐ ↓one│one-two│ one-two-three │ ├──→┼──────→┼──────────────→┤ │un │un-deux│ un-deux-trois │ ├──→┼──────→┼──────────────→┤ │yan│yan-tan│yan-tan-tethera│ └──→┴──────→┴──────────────→┘