# 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$.

```magma
> 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:

```magma
>  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$.

## 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.

```magma
> 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.

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

```