5
\$\begingroup\$

I have written an accumulate function similar to std::accumulate that works on a std::array. The goal is to remove the loop using fold expressions.

This code currently works in c++17:

#include <array>

template<class U, class F>
class array_accumulate_helper
{
public:
    array_accumulate_helper(U& u, F f)
        : r(u), f(f)
    {
    }

    array_accumulate_helper& operator<<(const U& u)
    {
        r = f(r, u);
        return *this;
    }

private:
    F f;
    U& r;
};

template<class U, std::size_t N, class F, std::size_t... Is>
constexpr U array_accumulate_impl(const std::array<U, N>& u, U r, F f, std::index_sequence<Is...>)
{
    array_accumulate_helper h(r, f);
    (h << ... << u[Is]);
    return r;
}

template<class U, std::size_t N, class F>
constexpr U accumulate(const std::array<U, N>& u, U r, F f)
{
    return array_accumulate_impl(u, r, f, std::make_index_sequence<N>());
}

template<class U, std::size_t N>
constexpr U accumulate(const std::array<U, N>& u)
{
    return accumulate(u, {}, [](const U& a, const U& b) { return a + b; });
}

Is it possible to rewrite array_accumulate_impl using a fold expression that doesn't use array_accumulate_helper?

I can use a fold expression with an operator. ie. using << in array_accumulate_impl above.

I have been unable to write one using a function recursively. ie. for a std::array<int, 3> it should expand to:

f(f(f(r, a[0]), a[1]), a[2]);
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Can you add a main that exercises the code a little? I couldn't get it to work without making the member functions in array_accumulate_helper constexpr too. example \$\endgroup\$
    – Ted Lyngmo
    Commented Oct 1, 2020 at 7:50

1 Answer 1

6
\$\begingroup\$

Unfortunately c++ fold expression supports only binary operators: "any of the following 32 binary operators: + - * / % ^ & | = < > << >> += -= = /= %= ^= &= |= <<= >>= == != <= >= && || , . ->*." So you can't call your custom function in pack expansion without using a wrapper.

But if your function accepts a variadic number of arguments you can use std::apply

static constexpr std::array arr{ 1, 2, 3, 4, 5, 6, 7};

static constexpr auto sum = [](auto&&... items) {
  return (... + items);
};

static constexpr auto accumulate = [](auto&& fn, const auto& u) {
  return std::apply([fn = std::forward<decltype(fn)>(fn)](auto... item) { return fn(item...); }, u);
};

constexpr auto result = accumulate(sum, arr);

Example here.

Otherwise, you can take advantage of the comma operator:

static constexpr std::array arr{ 1, 2, 3, 4, 5, 6, 7};

static constexpr auto accumulate_impl = [](const auto& a, auto init, auto&& fn) {
  return std::apply([fn = std::forward<decltype(fn)>(fn), &init](auto... items) {
    ((void)(init = fn(std::move(init), items)), ...);
    return init;
  }, a);
};

template<class U, std::size_t N>
static constexpr U accumulate(const std::array<U, N>& u) {
  return accumulate_impl(u, U{},  [](auto&& a, auto&& b){return a+b;});
}

static constexpr auto result = accumulate(arr);

Example here.

\$\endgroup\$
2
  • \$\begingroup\$ Also worthwhile: std::plus<void> \$\endgroup\$ Commented Oct 2, 2020 at 3:38
  • \$\begingroup\$ Nice. Thanks for expanding my knowledge. \$\endgroup\$ Commented Oct 2, 2020 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.