How do I implement accumulation in APL?

Question

Consider the following simple piece of code:

  a ← ⍳5
  el1 ← a+2
  el2 ← +/el1 
  el1 el2

  ┌─────────┬──┐
  │3 4 5 6 7│25│
  └─────────┴──┘

I am simply adding 2 to a and summing the array up, then returning array containing results of both operations. As I understand it, APL interpreter would in this case have to go 2 times over the array.

Is this the correct way to do this in APL or does the language have some kind of accumulators, similar to what functional programming languages provide (which would let me go only 1 time over the array)?

Answer 1

As such, there isn't any specific accumulation functionality in APL. I imagine most APLers view +/A and X+2 as primitive operations where the interpreter must iterate repeatedly over arrays a fact of life.

However, assuming your APL system supports user-defined operators, you can easily write a kind of accumulation operator. That is, if the goal is to make a single pass over an array. Something like

(⍳5) (+ accum +) 2

Where the code would be something like

     ∇ r←a(fn1 accum fn2)b;x                                                                             
[1]    r←0                                                                                             
[2]    :For x :In a                                                                                    
[3]        r←r fn1 x fn2 b                                                                             
[4]    :End                                                                                            
     ∇      

This is a very simplistic solution which would work correctly with + and x and other functions where fn1's identity is 1. Performance would not be as good as that of the example. Note also the solution starts to resemble reduction.

Back to normal APL, if you don't need the intermediate result, +/ a + 2 would be fine. As a practical matter, code fragments of +/ a x 2 or +/ a * 2 are very common. Also for vector a, inner product could also work, a +.x 2 and a +.* 2 are also not uncommon.

Last and certainly least, a future optimising APL interpreter or compiler could employ loop fusion to do this operation internally with only one loop instead of two.

Answer 2

I'd say this is the way to do it. But when thinking about performance, it might be interesting to optimise a bit:

{(2×⍴⍵)++/⍵}⍳5
25

because in that case you'd be going through the array once only and be adding two scalars afterwards. But the 'advantage' depends on the length of the array:

]runtime  {(2×⍴⍵)++/⍵}⍳5 {+/2+⍳⍵}5 -compare

  {(2×⍴⍵)++/⍵}⍳5 → 2.0E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
* {+/2+⍳⍵}5      → 1.4E¯6 | -29% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕            

For short arrays, it is faster to add to every element. But the more elements, the more you can gain:

]runtime  {(2×⍴⍵)++/⍵}⍳5 {+/2+⍳⍵}500 -compare                                                                             
  {(2×⍴⍵)++/⍵}⍳5 → 1.5E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕                
* {+/2+⍳⍵}500    → 2.4E¯6 | +59% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 

]runtime  {(2×⍴⍵)++/⍵}⍳5 {+/2+⍳⍵}5000 -compare                                                                              
  {(2×⍴⍵)++/⍵}⍳5 → 1.6E¯6 |    0% ⎕⎕⎕⎕                                     
* {+/2+⍳⍵}5000   → 1.5E¯5 | +822% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 

Answer 3

If I understand your question then you are first mapping +2 to a, then reducing it with addition. For example in haskell: (note reduce is foldl)

foldl (+) 0 $ map (2+) [1..5] 

Obviously this requires two passes if done without optimizations e.g. loop fusion.

However

I suspect this is a case of asking the wrong question and what you're actually looking for is scan (which in some languages is accumulate).

Haskell:

scanl (+) 0 [1..5]
-- [0,1,3,6,10,15]

APL:

+\⍳5
⍝  1 3 6 10 15

In this case the output sequence will contain the intermediate values, and the result.