-- # Computing histograms
--
-- Mathematically, a
-- [histogram](https://en.wikipedia.org/wiki/Histogram#Mathematical_definition)
-- 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](scan-reduce.html)).
-- 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*.
--
-- ## See also
--
-- [Removing duplicates](removing-duplicates.html)