Documentation

Reduction and Iteration

Reduction

Instead of using a loop to apply the same binary associative operator to all elements of a (non-formal) set, it is in certain cases possible to use the reduction operator &.

& o S : Op, SetIndx -> Elt

& o S : Op, SetMulti -> Elt

Given an enumerated, indexed, or multiset S = { a₁, a₂, ..., a_n } of elements belonging to an algebraic structure U, and an (associative) operator : U x U -> U, form the element a_i₁ a_i₂ a_i₃ ... a_{i_n}, for some permutation i₁, ..., i_n of 1, ..., n.
Currently, the following operators may be used to reduce such sets: +, *, and, or, join, and meet. An error will occur if the operator is not defined on U.
If S contains a single element a, then the value returned is a. If S is the null set (empty and no universe specified) or S is empty with universe U (and the operation is defined in U), then the result (or error) depends on the operation and upon U. The following table defines the return value:
           EMPTY     NULL
   &+       U!0      error
   &*       U!1      error
   &and    true      true
   &or     false     false
   &join   empty     null
   &meet   error     error
Warning: since the reduction may take place in an arbitrary order on the arguments a₁, ..., a_n, the result is not unambiguously defined if the operation is not commutative on the arguments!

Example `Set_Reduction (H10E14)`

The function choose defined below takes a set S and an integer k as input, and produces a set of all subsets of S with cardinality k.

> function choose(S, k)
>    if k eq 0 then
>       return { { } };
>    else
>       return &join{ { s join { x } : s in choose(S diff { x }, k-1) } : x in S };
>    end if;
> end function;

So, for example:

>  S := { 1, 2, 3, 4 };
> choose(S, 2);
{
       { 1, 3 },
       { 1, 4 },
       { 2, 4 },
       { 2, 3 },
       { 1, 2 },
       { 3, 4 }
 }

Try to guess what happens if k < 0.

The iteration operator in can be used in loops or in the set and sequence constructors to enumerate elements of a set. Enumerated, indexed, and multisets allow enumeration of their elements; formal sets do not. For indexed sets the enumeration will occur according to the order given by the indexing.

x in S

Enumerate the elements of an enumerated, indexed, or multiset S. Note that if S is a multiset then each element will be returned a number of times equal to its multiplicity in S.

i -> x in S

Enumerate the elements x of an indexed set S, together with the corresponding index value i.

x -> v in M

Enumerate the elements x of the underlying set of the multiset M, together with the corresponding multiplicity v. Note that elements with multiplicity larger than 1 will still only be returned once by this version of the iterator.

Example `Set_Iteration (H10E15)`

We display a simple frequency count of a certain string.

> M := Multiset(Eltseq("hello world"));
> for letter -> count in M do
>    if count eq 1 then
>       are := "is"; s := "";
>    else
>       are := "are"; s := "s";
>    end if;
>    printf "There %o %o '%o'%o n", are, count, letter, s;
> end for;
There is 1 ' '
There is 1 'e'
There are 3 'l's
There is 1 'w'
There is 1 'h'
There are 2 'o's
There is 1 'd'
There is 1 'r'

Note the difference between the use of the dual iterator above and the single form below.

> for letter in M do
>    printf "'%o'n", letter;
> end for;
' '
'e'
'l'
'l'
'l'
'w'
'h'
'o'
'o'
'd'
'r'

V2.28, 13 July 2023