General Notation for a Reductive Operation, such as Sum (Σ) or Product (Π)

221 Views Asked by At

In functional programming, people often use operations like "fold" or "reduce", to convert from a collection to a single object using a binary operation.

This is analogous to the sum and product operations used in math, but more general. For example, a collection of Boolean values could be reduced using $\wedge$ or $\vee$ operations.

Is there any terminology or notation for the reduction of a set or sequence of objects using an arbitrary binary operation?

1

There are 1 best solutions below

2
On BEST ANSWER

For operations other than sums and products, it is common to use big versions of the operator in question, for example $$\bigwedge_{i=1}^n \phi_i = \phi_1 \wedge \cdots \wedge \phi_n.$$

The initial element you would have to specify when using “fold” or “reduce” is implicitly the neutral element of the operation. If there is none (as for intersections of arbitrary sets, for example), you can only use it to fold over non-empty collections. Also, there is no standard for the order in which the operations are applied, so your operator should be associative and probably also commutative. If this is not the case, you can use text to specify the order explicitly.

Lastly, some operations can be extended to arbitrary families (instead of just finite lists). We then use the notation $$\bigcup_{i\in I} A_i.$$