**Announcement: We are hiring a PhD student to do research on functional high performance computing, including work on Futhark itself. See here for more details.**

# Scans and reductions

The `reduce`

function reduces an array to a single value by conceptually inserting a binary operator (or any two-parameter function) between each element.

```
reduce (+) 0 [1, 2, 3, 4]
== [1 + 2 + 3 + 4]
== 10
```

We can use them to define a function for computing averages:

There are some restrictions to enable parallel execution. In an expression `reduce f ne xs`

, the function `f`

must be associative and have `ne`

as neutral element. Intuitively, associativity means that we can move around the parantheses in an application:

`f (g x y) z == f x (g y)`

It’s a bit easier to understand if we write the function as an infix operator instead:

`(x + y) + z == x + (y + z)`

`ne`

being a neutral element means that it does not affect the result of the function:

`f x ne == f ne x == x`

As a simple example, 0 is the neutral element for addition, and 1 for multiplication.

Scans (also called prefix sums) are similar to reductions, but rather than producing a single result, they produce an array of the same size as the input, where ach element is conceptually a reduction of a prefix of the array:

```
scan (+) 0 [1, 2, 3, 4]
== [reduce (+) 0 [1],
reduce (+) 0 [1,2],
reduce (+) 0 [1,2,3],
reduce (+) 0 [1,2,3,4]]
== [1, 3, 6, 10]
```

Somewhat surprisingly, these can also be efficiently computed in parallel, and have the same restrictions with respect to associativity and a neutral element as `reduce`

. For now, scans may look a bit exotic, and they certainly are, but we’ll return to them in other examples, as they are an important building block in advanced parallel algorithms.