Fork me on GitHub
Source file: histograms.fut

# Computing histograms

Mathematically, a histogram is a discretised representation of a probability distribution. A histogram computation takes as input a collection of elements, maps each to one of k bins, and counts the number of elements that fall into each bin (discarding invalid bins). In Futhark, histogram-like computations can be done with `hist`:

``````def histogram [n] (k: i64) (is: [n]i64): [k]i32 =
hist (+) 0 k is (replicate n 1)``````

For example, `histogram 3 [0, 1, 3, 2, 1, 0, 0, 1]` produces `[3, 3, 1]`. Note that out-of-bounds bins (the `3`) are ignored.

`hist` is a surprisingly flexible function. In imperative pseudocode, we can describe the behaviour of `hist f ne k is as` as:

``````dest = replicate k ne
for j < length is:
i = is[j]
a = as[j]
if i >= 0 && i < k:
dest[i] = f(dest[i], a)``````

The `f` function must be associative and have `ne` as its neutral element (like with scans and reductions). Furthermore, it must also be commutative, which simply means that `f x y == f y x`.

There is also a variant, `reduce_by_index`, where the destination array is updated operationally in-place.