C++ generic reduction using reducer and monoid (for more flexible parallel STL)

reduce.cpp

#include <iostream>
#include <algorithm>
#include <functional>
#include <limits>
#include <utility>
#include <vector>
#include <string>
#include <random>
#include <cassert>

template <typename ForwardIterator, typename Reducer>
inline typename Reducer::accumulator_type
reduce(ForwardIterator first,
       ForwardIterator last,
       Reducer         reducer) {
  auto reduce_impl = [&](ForwardIterator f, ForwardIterator l) {
    auto acc = reducer.identity();
    for (auto it = f; it != l; ++it) {
      reducer(acc, *it);
    }
    return acc;
  };
  auto mid = first + (last - first) / 2;
  // The following two functions can be computed in parallel
  auto acc1 = reduce_impl(first, mid);
  auto acc2 = reduce_impl(mid, last);
  // Combine results
  reducer(acc1, acc2);
  return acc1;
}

template <typename T>
struct default_identity_provider {
  static T value() {
    return T{};
  }
};

template <typename T, typename BinaryOp, typename IdentityProvider = default_identity_provider<T>>
struct monoid_reducer {
  using value_type       = T;
  using accumulator_type = T;

  void operator()(accumulator_type& t1, const value_type& t2) const {
    t1 = bop_(t1, t2);
  }

  accumulator_type identity() const {
    return IdentityProvider::value();
  }

private:
  static constexpr auto bop_ = BinaryOp();
};

template <typename T>
struct one {
  static_assert(std::is_arithmetic_v<T>);
  static constexpr T value() {
    return T{1};
  }
};

template <typename T>
struct lowest {
  static_assert(std::is_arithmetic_v<T>);
  static constexpr T value() {
    return std::numeric_limits<T>::lowest();
  }
};

template <typename T>
struct highest {
  static_assert(std::is_arithmetic_v<T>);
  static constexpr T value() {
    return std::numeric_limits<T>::max();
  }
};

template <typename T = void>
struct min_functor {
  constexpr T operator()(const T& x, const T& y) const {
    return std::min(x, y);
  }
};

template <>
struct min_functor<void> {
  template <typename T, typename U>
  constexpr auto operator()(T&& v, U&& u) const {
    return std::min(std::forward<T>(v), std::forward<U>(u));
  }
};

template <typename T = void>
struct max_functor {
  constexpr T operator()(const T& x, const T& y) const {
    return std::max(x, y);
  }
};

template <>
struct max_functor<void> {
  template <typename T, typename U>
  constexpr auto operator()(T&& t, U&& u) const {
    return std::max(std::forward<T>(t), std::forward<U>(u));
  }
};

template <typename T>
using plus_reducer = monoid_reducer<T, std::plus<>>;

template <typename T>
using multiplies_reducer = monoid_reducer<T, std::multiplies<>, one<T>>;

template <typename T>
using min_reducer = monoid_reducer<T, min_functor<>, highest<T>>;

template <typename T>
using max_reducer = monoid_reducer<T, max_functor<>, lowest<T>>;

template <typename T>
struct minmax_reducer {
  using value_type       = T;
  using accumulator_type = std::pair<T, T>;

  void operator()(accumulator_type& acc, const value_type& x) const {
    acc.first = std::min(acc.first, x);
    acc.second = std::max(acc.second, x);
  }

  void operator()(accumulator_type& acc1, const accumulator_type& acc2) const {
    acc1.first = std::min(acc1.first, acc2.first);
    acc1.second = std::max(acc1.second, acc2.second);
  }

  accumulator_type identity() const {
    return std::make_pair(std::numeric_limits<T>::max(), std::numeric_limits<T>::lowest());
  }
};

template <typename T, typename Counter = std::size_t>
struct histogram_reducer {
  using value_type       = T;
  using accumulator_type = std::vector<Counter>;

  histogram_reducer(std::size_t n) : n_(n) {}
  histogram_reducer(std::size_t n, const value_type& lowest, const value_type& highest)
    : n_(n), lowest_(lowest), highest_(highest) {}

  void operator()(accumulator_type& acc, const value_type& x) const {
    if (lowest_ <= x && x <= highest_) {
      auto delta = (highest_ - lowest_) / n_;
      std::size_t key = (x - lowest_) / delta;
      assert(0 <= key);
      assert(key < n_);
      acc[key]++;
    }
  }

  void operator()(accumulator_type& acc1, const accumulator_type& acc2) const {
    // acc1 += acc2
    std::transform(acc1.begin(), acc1.end(), acc2.begin(), acc1.begin(),
                   [](const Counter& c1, const Counter& c2) { return c1 + c2; });
  }

  accumulator_type identity() const {
    return std::vector<Counter>(n_, 0);
  }

private:
  std::size_t n_;
  value_type lowest_ = std::numeric_limits<value_type>::lowest();
  value_type highest_ = std::numeric_limits<value_type>::max();
};

int main() {
  // monoid: (int, +, 0)
  std::vector<int> v1 = {1, 2, 3, 4, 5};

  int sum = ::reduce(v1.begin(), v1.end(), plus_reducer<int>{});
  std::cout << sum << std::endl;

  // monoid: (double, *, 1)
  std::vector<double> v2 = {0.1, 0.2, 0.3, 0.4, 0.5};

  double product = ::reduce(v2.begin(), v2.end(), multiplies_reducer<double>{});
  std::cout << product << std::endl;

  // monoid: (double, <min>, double_max)
  double min = ::reduce(v2.begin(), v2.end(), min_reducer<double>{});
  std::cout << min << std::endl;

  // monoid: (double, <max>, double_min)
  double max = ::reduce(v2.begin(), v2.end(), max_reducer<double>{});
  std::cout << max << std::endl;

  // minmax reducer
  auto [min2, max2] = ::reduce(v2.begin(), v2.end(), minmax_reducer<double>{});
  std::cout << min2 << " " << max2 << std::endl;

  // string concatenation
  std::vector<std::string> v3 = {"H", "e", "l", "l", "o", ", ", "world!"};

  std::string concatenated = ::reduce(v3.begin(), v3.end(), plus_reducer<std::string>{});
  std::cout << concatenated << std::endl;

  // histogram for normal distribution
  std::size_t n = 10000;
  std::mt19937 engine(std::random_device{}());
  std::normal_distribution<> dist(0.0, 1.0);

  std::vector<double> samples(n);
  for (auto&& x : samples) {
    x = dist(engine);
  }

  int rows = 10;
  int columns = 40;
  auto histogram = ::reduce(samples.begin(), samples.end(), histogram_reducer<double>(rows, -3.0, 3.0));

  auto max_count = ::reduce(histogram.begin(), histogram.end(), max_reducer<std::size_t>{});
  for (const auto& count : histogram) {
    auto n_chars = count * columns / max_count;
    std::cout << std::string(n_chars, '*') << std::endl;
  }
}

The output will be:

15
0.0012
0.1
0.5
0.1 0.5
Hello, world!
*
*****
*************
****************************
****************************************
***************************************
****************************
**************
****
*