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
def histogram [n] (k: i64) (is: [n]i64): [k]i32 = 0 k is (replicate n 1) hist (+)
histogram 3 [0, 1, 3, 2, 1, 0, 0, 1] produces
[3, 3, 1]. Note that out-of-bounds bins (the
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 nefor j < length is: i = is[j] a = as[j]if i >= 0 && i < k: dest[i] = f(dest[i], a)
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.