how to write a fold /sum function for C++ tuple?

Question

I wanted to write a fold function for std::tuple that can compute e.g. the sum (or product) of all the elements in a given tuple. For example, given

std::tuple<int,double> t = std::make_tuple(1,2);

I'd like to compute

auto s = sumT(t); //giving 3

I tried but couldn't get my template programming (c++11/1z) code below to compile. I also tried to adapt the accepted answer for my other question (How to perform tuple arithmetic in C++ (c++11/c++17)?), but can't figure out how to use std::index_sequence in this case.

The issues I have are:

1) I can't figure out the types, e.g. how to use the type of the first element as the return type. Currently, I use a _res type in the template, but I don't know if that will block c++'s auto type-inferencing.

2) I'd like to program this without using an explicit initial element 0, so that this can be used for other kinds of fold operations.

Currently, the recursion ends at the last element. I'd like to end the recursion at _size - 1 so that I can directly perform the operation on the last element without resorting to 0.

The code I have below tries to do this by recursion. But I don't know template programming well, and how the loops work for tuples.

Can someone help fix the code or come up with a better solution?

My code so far is:

#include <tuple>
#include <iostream>
#include <functional>

// helper class for fold operations
template<typename Op,typename _res, typename _Tp, size_t _i, size_t _size>
struct _tuple_fold  {
    static constexpr _res _op(Op const & op, const _Tp& _t) {
      return _res(op(std::get<_i>(_t),
                _tuple_fold<Op, _res, _Tp, _i + 1, _size>::_op(op,_t) ));
    }
};

template<typename Op,typename _res,typename _Tp, size_t _size>
struct _tuple_fold<Op, _res,_Tp, _size, _size> {
  static constexpr _res _op(Op const &, const _Tp&) { return 0; }
};

template <typename ... Ts>
auto sumT (std::tuple<Ts...> const & t1)  {
  return _tuple_fold::_op(std::plus<>{}, t1);
}

int main () {
  std::tuple<int,double> t = std::make_tuple(1,2);
  auto s = sumT(t);
  std::cout << s << std::endl;
}

The error messages for compiling with g++ -std=c++17 tuple_sum.cpp:

tuple_sum.cpp: In function ‘auto sumT(const std::tuple<_Elements ...>&)’:
tuple_sum.cpp:21:10: error: ‘template<class Op, class _res, class _Tp, long unsigned int _i, long unsigned int _size> struct _tuple_fold’ used without template parameters
   return _tuple_fold::_op(std::plus<>{}, t1);
          ^
tuple_sum.cpp: In function ‘int main()’:
tuple_sum.cpp:27:19: error: ‘void s’ has incomplete type
    auto s = sumT(t);
                   ^

I'm not sure how to supply the type parameters for _tuple_fold on the call site, especially the type for std::plus.

[std::accumulate](http://en.cppreference.com/w/cpp/algorithm/accumulate) with a lambda should do nicely I think. — Jesper Juhl, Nov 10 '17 at 07:00
@JesperJuhl nope, you cannot take usual iterators from an etherogeneous container ( like tuple ) — Massimiliano Janes, Nov 10 '17 at 08:25

Massimiliano Janes · Answer 1 · 2017-11-10T08:23:29.610

24

note that in c++17 we can apply() and fold:

auto t = std::make_tuple( 1, 2. );
auto sum = std::apply([]( auto... v ){ return ( v + ... ); }, t );

this will work for any tuple-like type and follows usual promotion/conversion rules for '+' out of the box ( this may or may not be desirable ). In the above I pass by value because we're dealing with arithmetic types, but you can apply your preferred forwarding strategy of course...

edited Nov 10 '17 at 08:23

answered Nov 10 '17 at 08:14

Massimiliano Janes

5,524
1
10
22

2

This works great when you know and can hard-code the folding operator +. – Vladimir Reshetnikov Mar 06 '18 at 02:06

score 6 · Accepted Answer · answered Nov 10 '17 at 05:58

Thankfully, if constexpr in C++17 allows us to avoid complicating things by introducing partially specialized helper structs, and makes it easy to terminate the recursion on whatever condition we want:

#include <functional>
#include <iostream>
#include <tuple>
#include <type_traits>

template <size_t index, class Op, class... Ts>
constexpr auto tuple_fold(Op op, const std::tuple<Ts...>& t) {
    if constexpr(index == sizeof...(Ts) - 1) {
        return std::get<index>(t);
    } else {
        return op(std::get<index>(t), tuple_fold<1 + index>(op, t));
    }
}

template <typename ... Ts>
constexpr auto sumT (std::tuple<Ts...> const & t1)  {
  return tuple_fold<0>(std::plus<>{}, t1);
}

int main () {
  std::tuple<int,double> t = {1, 2.0};
  auto s = sumT(t);
  static_assert(std::is_same_v<decltype(s), double>);
  std::cout << s << std::endl;
}

Coliru link: http://coliru.stacked-crooked.com/a/1e7051b8652fb942

This will perform a right fold, a + (b + (c + ...)) but it's easy to rewrite it to perform a left fold instead, if you want.

Yakk - Adam Nevraumont · Answer 3 · 2017-11-10T18:45:18.190

We can leverage c++17's left and right fold builtins to fold over any binary operation.

template<class F, class Lhs=void>
struct invoke_by_times_t {
  F& f;
  Lhs lhs;
  template<class Rhs>
  auto operator*( Rhs&& rhs )&&
  ->invoke_by_times_t<F, std::invoke_result_t< F&, Lhs, Rhs >>
  {
    return {
      f,
      f(std::forward<Lhs>(lhs), std::forward<Rhs>(rhs))
    };
  }
};

template<class F>
struct invoke_by_times_t<F, void> {
  F& f;
  template<class Rhs>
  invoke_by_times_t<F, Rhs> operator*( Rhs&& rhs )&&{
    return {f, std::forward<Rhs>(rhs)};
  }
};

template<class F>
auto fold_over( F&& f ) {
  return [f=std::forward<F>(f)](auto&&...args)mutable{
    return ( invoke_by_times_t<F>{f}*...*decltype(args)(args) ).lhs;
  };
}

now given any binary function we can create a function object that folds over it without doing any recursion.

Together with std::apply we are done.

template <typename ... Ts>
auto sumT (std::tuple<Ts...> const & t1)  {
  return std::apply( fold_over(std::plus<>{}), t1);
}

Live example

This is a left fold. A right fold simply involves changing the fold_over function. If you try to pass an empty pack to this, it will fail to compile. If you pass it one element, it will return that element.

Vladimir Reshetnikov · Answer 4 · 2018-09-10T22:02:29.907

#include <tuple>
#include <utility>

namespace detail {

template<class F, class T>
struct foldable : std::pair<const F&, T> {
    using std::pair<const F&, T>::pair;

    template<class V>
    constexpr decltype(auto) operator&&(foldable<F, V>&& x) {
        return detail::foldable {
            this->first,
            this->first(this->second, x.second),
        };
    }
};

template<class F, class T> foldable(const F&, T&&) -> foldable<F, T>;

}

// Folds left a parameter pack
template<class F, class... Args>
constexpr decltype(auto) fold_left_pack(const F& f, Args&&... args) {
    static_assert(sizeof...(Args) > 0, "Cannot fold an empty pack.");
    return (... && detail::foldable { f, std::forward<Args>(args) }).second;
}

// Folds right a parameter pack
template<class F, class... Args>
constexpr decltype(auto) fold_right_pack(const F& f, Args&&... args) {
    static_assert(sizeof...(Args) > 0, "Cannot fold an empty pack.");
    return (detail::foldable { f, std::forward<Args>(args) } && ...).second;
}

// Folds left a tuple
template<class F, class Tuple>
constexpr decltype(auto) fold_left(const F& f, Tuple&& tuple) {
    return std::apply(
        [&](auto&&... args) -> decltype(auto) {
            return fold_left_pack(f, std::forward<decltype(args)>(args)...);
        },
        std::forward<Tuple>(tuple));
}

// Folds right a tuple
template<class F, class Tuple>
constexpr decltype(auto) fold_right(const F& f, Tuple&& tuple) {
    return std::apply(
        [&](auto&&... args) -> decltype(auto) {
            return fold_right_pack(f, std::forward<decltype(args)>(args)...);
        },
        std::forward<Tuple>(tuple));
}

A test:

constexpr auto divide = [](auto x, auto y) { return x / y; };
constexpr auto tuple = std::make_tuple(8, 4, 2);
static_assert(1 == fold_left(divide, tuple));
static_assert(4 == fold_right(divide, tuple));

how to write a fold /sum function for C++ tuple?

4 Answers4