Tuesday, November 01, 2005

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, if A is the empty sequence; and ◊(A) = ◊(prefix(Ak))Ak, if 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:

OperatorBulk ActionIdentity
+ (addition)∑ (finite sum)0
× (multiplication)∏ (finite product)1
∧ (conjunction)∀ (universal quantification)true
∨ (disjunction)∃ (existential quantification)false
↑ (maximum)max (maximum)-∞
↓ (minimum)min (minimum)+∞
Note that I'm playing a bit fast-and-loose here in using the infinities. It just means the underlying set 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.