Reduction and Iteration

Reduction

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

& o S: Op, SetEnum -> Elt

& o S: Op, SetIndx -> Elt

& o S: Op, SetMulti -> Elt

Given an enumerated, indexed, or multiset \(S = \lbrace\ a_1, a_2, \ldots, a_n \rbrace\) of elements belonging to an algebraic structure \(U\), and an (associative) operator \(\circ : U \times U \rightarrow U\), form the element \(a_{i_1} \circ a_{i_2} \circ a_{i_3} \circ \ldots \circ a_{i_n}\), for some permutation \(i_1, \ldots, i_n\) of \(1, \ldots, 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_1, \ldots, a_n\), the result is not unambiguously defined if the operation is not commutative on the arguments!

Example: Reduction (ex-50129c)

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;

Run in calculatorCopy input

So, for example:

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

Run in calculatorCopy input

Try to guess what happens if \(k < 0\).

Iteration

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. 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: Iteration (ex-00bab7)

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'

Run in calculatorCopy input

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'

Run in calculatorCopy input