⍝ Variations on primitive scan:
 nvec ← {axis}      ##.mscan   nvec             ⍝ Minus scan.
 nvec ← {axis}      ##.dscan   nvec             ⍝ Divide scan.
 vect ←         (fn ##.ascan)  vect             ⍝ Associative vector scan.
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:
    ¯¯¯¯¯¯¯¯¯
    ⍺⍺\⍵  →  ⍺⍺/¨(1 to ⍴⍵)↑¨⊂⍵

For example:

    +\3 1 4 1 6
→   +/¨(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.

      -\⍳1000                       ⍝ slow primitive minus-scan.
1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...

      mscan ⍳1000                   ⍝ quick minus-scan.
1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...


      ÷\⍳1000                       ⍝ slow primitive divide-scan.
1 0.5 1.5 0.375 1.875 0.3125 ...

      dscan ⍳1000                   ⍝ quick divide-scan.
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.

      {⍺+⍵}\⍳10000                  ⍝ slow primitive scan.
1 3 6 10 15 21 28 36 45 55 ...

      {⍺+⍵}ascan⍳1000               ⍝ quick associative scan.
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.

      {⍺-⍵}\⍳10                     ⍝ slow primitive scan.
1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5

      {⍺-⍵}ascan⍳10                 ⍝ quick left to right accumulation.
1 ¯1 ¯4 ¯8 ¯13 ¯19 ¯26 ¯34 ¯43 ¯53

    nums← ↑('one' 'two' 'three')('un' 'deux' 'trois')('yan' 'tan' 'tethera')

    {⍺,'-',⍵} ascan nums            ⍝ left-to-right scan along rows
┌───┬───────┬───────────────┐
│one│one-two│one-two-three  │
├───┼───────┼───────────────┤
│un │un-deux│un-deux-trois  │
├───┼───────┼───────────────┤
│yan│yan-tan│yan-tan-tethera│
└───┴───────┴───────────────┘

See also: acc

Back to: contents

Back to: Workspaces