**We are hiring a PhD student to do research on functional high performance computing, including work on Futhark itself. See here for more details.**Source file: no-neutral-element.fut

# Reducing or scanning without a neutral element

The `reduce`

and `scan`

functions expect you to provide a neutral
element, such as `0`

for addition or `1`

for multiplication. But
sometimes there may not be an obvious neutral element. In
mathematics, such a structure is called a
semigroup, while those
with neutral elements are called
monoids.

We can always turn any semigroup into a monoid, simply by adding a distinct new value to serve as the neutral element.

`type with_neutral 't = #neutral | #val t`

The operator must also be augmented to handle the neutral element:

```
def f_with_neutral 't (f: t -> t -> t)
(x: with_neutral t)
(y: with_neutral t)
: with_neutral t =match (x, y)
case (#val x, #val y) -> #val (f x y)
case (#neutral, _) -> y
case (_, #neutral) -> x
```

We can then define a variant of `reduce`

that does not require a
neutral element to be provided. If the input array is empty, it
will return the `#neutral`

value.

```
def reduce1 't (f: t -> t -> t) (ts: []t) : with_neutral t =
reduce (f_with_neutral f) #neutral (map (\t -> #val t) ts)
```

Try it out in the REPL:

```
> reduce1 (+) (iota 100)
#val 4950i32
> reduce1 (+) (iota 0)
#neutral
```

`reduce1`

is less efficient than `reduce`

due to the baggage of
carrying around `#neutral`

, as well as the extra control flow. It
is always better if a neutral element is more naturally available,
but this technique will do in a pinch.

Sadly, no similar trick exists for turning a non-associative function associative.