Musings on Reduction

In one man’s humble opinion, reduction () is the Queen of Operators.

Each (¨) comes a close second, but doesn’t get the cigar because each can be written in terms of reduction.

Two special cases are of interest: reduction along axes of length 1 (or reduction of a scalar) and reduction along axes of length 0.

With a length-1 axis (or scalar), the operand function is not applied (+⌿'A' → 'A'). This can be useful as an implicit no-op – see DFS video on YouTube.

With a length-0 axis, a primitive operand returns its right identity item – but only if one is defined (⌊⌿⍬). Otherwise: DOMAIN ERROR.

Another way to think about the 0-length axis case is that a right identity item (if there is one) is catenated to the argument prior to the reduction. Functional Programming languages tend to define reduction in this way by supplying an explicit initial value (ival) to the reduction:

    fold fn ival [] = ival
    fold fn ival (x:xs) = fn x (fold fn ival xs)

We can write such a variant of in APL, supplying the initial value as right operand ⍵⍵:

      fold ← {⍺⍺⌿⍵⍪⍵⍵}        ⍝ right operand ⍵⍵ is initial value

      × fold 1 ⊢2 3 4         ⍝ same as regular ×⌿
24

      {⍺×⍵}fold 1 ⊢2 3 4      ⍝ non-primitive operand function
24

      {⍺×⍵}fold 1 ⊢⍬          ⍝ initial value returned for empty argument
1

Whilst it doesn’t provide the no-op trick for length-1 axes, fold gives us better control for null cases than does primitive reduction, which relies on the single prototypical item of its argument array:

      ⊢mat ← 2 3 ∘.+ 0(0 0)
┌─┬───┐
│2│2 2│
├─┼───┤
│3│3 3│
└─┴───┘

Notice the discontinuity in the depth of the result with regular +⌿ as the number of rows reaches 0:

      +⌿ 2↑mat
┌─┬───┐
│5│5 5│
└─┴───┘

      +⌿ 1↑mat
┌─┬───┐
│2│2 2│
└─┴───┘

      +⌿ 0↑mat              ⍝ Eh?
0 0

Supplying the variant with a prototypical row produces a more uniform convergence:

      +fold 0(0 0) ⊢2↑mat
┌─┬───┐
│5│5 5│
└─┴───┘

      +fold 0(0 0) ⊢1↑mat
┌─┬───┐
│2│2 2│
└─┴───┘

      +fold 0(0 0) ⊢0↑mat   ⍝ Ah!
┌─┬───┐
│0│0 0│
└─┴───┘

A similar discontinuity can be seen even for axes of length 1, with non-scalar primitive operand functions:

      ⊢mat ← 3 3⍴⍳9
1 2 3
4 5 6
7 8 9

Now:

      ,⌿ 3↑mat              ⍝ join reduction
┌─────┬─────┬─────┐
│1 4 7│2 5 8│3 6 9│
└─────┴─────┴─────┘

      ,⌿ 2↑mat
┌───┬───┬───┐
│1 4│2 5│3 6│
└───┴───┴───┘

      ,⌿ 1↑mat              ⍝ Tsk!
1 2 3

      ,⌿ 0↑mat              ⍝ Bah!
DOMAIN ERROR

But:

      ,fold(⊂⍬) ⊢3↑mat
┌─────┬─────┬─────┐
│1 4 7│2 5 8│3 6 9│
└─────┴─────┴─────┘

      ,fold(⊂⍬) ⊢2↑mat
┌───┬───┬───┐
│1 4│2 5│3 6│
└───┴───┴───┘

      ,fold(⊂⍬) ⊢1↑mat      ⍝ Ooh!
┌─┬─┬─┐
│1│2│3│
└─┴─┴─┘

      ,fold(⊂⍬) ⊢0↑mat      ⍝ Aah!
┌┬┬┐
││││
└┴┴┘

Although we have no specific plans to do so, it is conceivable that this definition of fold could be introduced as a variant of primitive reduction:

        nums ← ⍠(⊂⍬)        ⍝ possible variant for numeric reduction

      ,⌿nums 1↑mat          ⍝ Ooh!
┌─┬─┬─┐
│1│2│3│
└─┴─┴─┘
      ,⌿nums 0↑mat          ⍝ Aah!
┌┬┬┐
││││
└┴┴┘
      ,/nums 3 1↑mat        ⍝ Mmm! reduction along last axis
┌─┬─┬─┐
│1│4│7│
└─┴─┴─┘

Notice that the left and right arguments of a reduction’s operand function need not be of the same kind. Using an informal type notation:

      ⌿ :: (⍺ ∇ ⍵ → ⍵) ∇∇ [⍺]⍪⍵ → ⊂⍵

which, given an argument of uniform kind, collapses to:

      ⌿ :: (⍺ ∇ ⍺ → ⍺) ∇∇ [⍺] → ⊂⍺

I hope to say more about this style of polymorphic type notation in a future posting. In the meantime, the significant point is only that, in the general case, the operand function is of “kind” (⍺ ∇ ⍵ → ⍵), which means that the kind of its left argument may differ from that of its right argument and result. See more discussion on this idea in the notes for foldl in dfns.dws.

5 thoughts on “Musings on Reduction

  1. The topic of user-specified identity elements was discussed in https://github.com/ngn/apl/issues/16
    Gist of what we came up with:

    f←{…} ⍝ a user-defined function
    f/⍬ ⍝ domain error
    g←f⍁I ⍝ f bound with an identity element I
    g/⍬ ⍝ returns I

    The advantage of this design over f/⍠I is you don’t need to specify the identity element every time you do reduction.

  2. I know you said this is one man’s opinion, but I have several bones to pick with this.

    0. You don’t need any operator to be Queen to make the point of the blog.

    1. The criterion seems to be, if you can define B in terms of A, then A is superior to B. By the same criteria the successor function ⍵+1 would be the Queen of Functions. (Do you in fact consider ⍵+1 to be so?)

    2. I can define f¨ in terms of f⌿ , but I had to use laminate (⍺,[¯0.5]⍵), not the prettiest of APL functions, or something even uglier in terms of shape and reshape. Moreover, to define how f⌿ works it seems best to use each.

    3. I note that in the APL standard, there are two definitions of reduction, enclose-reduction-style and insert-reduction-style. Two queens?

    Roger Hui

  3. I’m excited having found “bones” in Roger’s and John’s argument and am thrilled to now battle you about it – an “operator” is male, so how then can we have one or “queens” of operators? It has to be one or two KINGS – forget political correctness!

    • Gauss said “Mathematics is the queen of the sciences and number theory is the queen of mathematics”. I am content to follow his lead and talk about queens rather than kings.