### Binary operators and the zero case

Suppose we have a binary operator **•**: *S* × *S* → *S* with a left identity *e*. Let's define a new function ◊ on finite sequences of elements of *S* as follows: *A*) = *e**A* is the empty sequence; and *A*) = ◊(*prefix*(*A*, *k*))**•***A _{k}*

*A*is a sequence of length

*k*+1. I've found this new function referred to as the "bulk action" of

**•**, as an "iterated binary operation", and in the context of parallel programming, as the "prefix operation", but couldn't find evidence that any of these terms is in widespread use. I'll use the phrase "bulk action" until someone points me to a better phrase.

The bulk action is well-known for some common operators, and less well-known for others:

Operator | Bulk Action | Identity |
---|---|---|

+ (addition) | ∑ (finite sum) | 0 |

× (multiplication) | ∏ (finite product) | 1 |

∧ (conjunction) | ∀ (universal quantification) | true |

∨ (disjunction) | ∃ (existential quantification) | false |

↑ (maximum) | max (maximum) | -∞ |

↓ (minimum) | min (minimum) | +∞ |

*S*can't be the integers or the reals, but must instead be extended to include the infinity elements, with the natural extension of the min and max operators.

As a programmer, I've frequently found code that behaved incorrectly or was overly complex because of a failure to make the behavior on empty lists consistent with the identity element. Consider it a red flag if you have to unroll the first loop iteration.

## 0 Comments:

Post a Comment

## Links to this post:

Create a Link

<< Home