This is a read-only-page

Example "ScanOperator"

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

⍝ 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') disp {⍺,'-',⍵} 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│ └──→┴──────→┴──────────────→┘