How to implement a variadic tuple_map operation?

Question

I want to implement a function which maps a variadic list of tuples to another tuple, given a function.

It applies an N-ary function f to a list of elements taken from a list of N tuples (each with size at least M) and creates a new M-element tuple from the result of these applications.

For a list of N tuples, each with M elements, the call to std::make_tuple would look like this pseudocode:

std::make_tuple(
  f(t1_1, t2_1, t3_1, ..., tN_1),
  f(t1_2, t2_2, t3_2, ..., tN_2),
  f(t1_3, t2_3, t3_3, ..., tN_3),
  ...
  f(t1_M, t2_M, t3_M, ..., tN_M)
)

Sometimes this operation is named zipWith in other languages.

I want this function, tuple_map, to have the following signature:

template<class Tuple1, class... Tuples2, class Function>
auto tuple_map(Tuple1&& tuple1, Tuples&&... tuples, Function f);

I've figured out the implementation for a function taking a single tuple:

#include <tuple>
#include <integer_sequence>
#include <type_traits>
#include <utility>

template<class Tuple, class Function, size_t... I>
auto tuple_map_impl(Tuple&& t, Function f, std::index_sequence<I...>)
  -> decltype(
       std::make_tuple(
         f(std::get<I>(std::forward<Tuple>(t)))...
       )
     )
{
  return std::make_tuple(
    f(std::get<I>(std::forward<Tuple>(t)))...
  );
}

template<class Tuple, class Function>
auto tuple_map(Tuple&& t, Function f)
  -> decltype(
       tuple_map_impl(
         std::forward<Tuple>(t),
         f,
         std::make_index_sequence<
           std::tuple_size<std::decay_t<Tuple>>::value
         >()
       )
     )
{
  using indices = std::make_index_sequence<
    std::tuple_size<std::decay_t<Tuple>>::value
  >;
  return tuple_map_impl(std::forward<Tuple>(t), indices());
}

When I introduce another parameter pack (Tuples) in addition to I..., it causes problems:

template<class Tuple1, class... Tuples, class Function, size_t... I>
auto tuple_map_impl(Tuple1&& tuple1, Tuples&&... tuples, Function f, std::index_sequence<I...>)
  -> decltype(
       std::make_tuple(
         f(
           std::get<I>(std::forward<Tuple1>(t1)),
           std::get<I>(std::forward<Tuples>(tuples))...
         )...
       )
     )
{
  return std::make_tuple(
    f(
      std::get<I>(std::forward<Tuple>(t)),
      std::get<I>(std::forward<Tuples>(tuples))...
    )...
  );
}

Compiler error:

error: mismatched argument pack lengths while expanding ‘get<I>(forward<Tuples>(tuples))’

This is because I've used two packs with different lengths (I and Tuples) within the same expression.

I can't think of a different way to write this function which would not use the two packs within the same expression.

What is the best way to implement tuple_map?

Answer 1

If I understand what you're trying to do correctly, this code seems to do the trick with Visual Studio 2013 (November 2013 CTP):

#include <iostream>
#include <tuple>
#include <utility>

using namespace std;

// index_sequence implementation since VS2013 doesn't have it yet
template <size_t... Ints> class index_sequence {
public:
  static size_t size() { return sizeof...(Ints); }
};

template <size_t Start, typename Indices, size_t End>
struct make_index_sequence_impl;

template <size_t Start, size_t... Indices, size_t End>
struct make_index_sequence_impl<Start, index_sequence<Indices...>, End> {
  typedef typename make_index_sequence_impl<
      Start + 1, index_sequence<Indices..., Start>, End>::type type;
};

template <size_t End, size_t... Indices>
struct make_index_sequence_impl<End, index_sequence<Indices...>, End> {
  typedef index_sequence<Indices...> type;
};

template <size_t N>
using make_index_sequence =
    typename make_index_sequence_impl<0, index_sequence<>, N>::type;

// The code that actually implements tuple_map
template <size_t I, typename F, typename... Tuples>
auto tuple_zip_invoke(F f, const Tuples &... ts) {
  return f(get<I>(ts)...);
}

template <typename F, size_t... Is, typename... Tuples>
auto tuple_map_impl(F f, index_sequence<Is...>, const Tuples &... ts) {
  return make_tuple(tuple_zip_invoke<Is>(f, ts...)...);
}

template <typename F, typename Tuple, typename... Tuples>
auto tuple_map(F f, const Tuple &t, const Tuples &... ts) {
  return tuple_map_impl(f, make_index_sequence<tuple_size<Tuple>::value>(), t,
                        ts...);
}

int sum(int a, int b, int c) { return a + b + c; }

int main() {
  auto res =
      tuple_map(sum, make_tuple(1, 4), make_tuple(2, 5), make_tuple(3, 6));
  cout << "(" << get<0>(res) << ", " << get<1>(res) << ")\n";
  return 0;
}

Output is:

(6, 15)

Answer 2

You can use recursion and std::tuple_cat() like this:

template <class Function, class Tuple, size_t... I>
auto tuple_map_impl(Function f, Tuple&& t, std::index_sequence<I...>)
{
    return std::make_tuple(f(std::get<I>(std::forward<Tuple>(t)))...);
}

template <class F, class Tuple, class... Tuples>
auto tuple_map(F f, Tuple&& t, Tuples&&... tuples)
{
    return std::tuple_cat(tuple_map_impl(f, std::forward<Tuple>(t), std::make_index_sequence<std::tuple_size<std::decay_t<Tuple>>::value>{}),
                          tuple_map(f, tuples...));
}

template <class F>
auto tuple_map(F) { return std::make_tuple(); }

Live Demo

Answer 3

I might approach this problem by factoring the mapping and the catting. Using your existing tuple_map, try this:

template <typename ...Tuple, typename F>
auto tuple_map(Tuple && tuple, F f)
{
    return std::tuple_cat(tuple_map(std::forward<Tuple>(tuple), f)...);
}