Scans and reductions
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:
def average (xs: f64) = 0.0 xs / f64.i64 (length xs) reduce (+)
There are some restrictions to enable parallel execution. In an
reduce f ne xs, the function
f must be
ne as neutral element. Intuitively, associativity means
that we can move around the parantheses in an application:
f (f x y) z == f x (f y z)
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.
If we pass
reduce a function that is not associative, or does not
have the provided neutral element, we will get wrong results at
run-time. What’s worse, the compiler will not be able to detect
that we messed up (it’s actually impossible in general), however
techniques exist for testing associativity
empirically. You can also invent a
neutral element if necessary.
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 each element is conceptually a reduction of a prefix of the array:
scan (+) 0 [1, 2, 3, 4] == [reduce (+) 0 , 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.
Reducing the result of a filter.