3

I am attempting to map function f over tuples t0, t1, etc. to return the tuple std::tuple<f(std::get<0>(t0),std:get<0>(t1),...),f(std::get<1>(t0),std::get<1>(t1),...),...). I have a version working using car,cdr, and cons but am trying to get a version working using std::index_sequence.

The code:

// Helper
template<typename T>
using make_tuple_index = std::make_index_sequence<std::tuple_size<T>::value>;

// Implementation
template<typename F, typename... Ts, std::size_t... Is>
auto mapx_n_impl(const F& f, std::index_sequence<Is...>, const Ts&... t)
{ return std::make_tuple(f(std::get<Is>(t...))...); }

// Interface
template<typename T,
         typename F,
         typename Indices = make_tuple_index<T>>
auto map(const T& t, const F& f)
{ return mapx_impl(t, f, Indices{}); }

// Test
auto tup1 = std::make_tuple(1.0, 2.0, 3.0);
auto tup2 = std::make_tuple(0.0, 1.0, 2.0);
auto r = mapx_n([](auto x, auto y) { return x - y; }, tup1, tup2);

The problem is expanding the parameter packs in the implementation return statement. I need it to expand t in the "inner" loop and Is in the "outer" loop. How is the expansion controlled? And, how do I fix my return statement?

UPDATE:

Based on the response from @Yakk and the further elucidation by @max66, I have simplified my code as much as I think possible. The current version integrates a version of the parameter pack expansion helper from @Yakk's answer as well as factoring out the get_element call into a lambda.

// invoke_with_pack
template<std::size_t... Is, typename F>
auto invoke_with_pack(std::index_sequence<Is...>, F&& function)
{ return function(std::integral_constant<std::size_t, Is>{}...); }

// nth
template<natural N, typename... Ts>
using nth = typename std::tuple_element<N, std::tuple<Ts...>>::type;

// make_tuple_index -- Helper template for computing indices
// corresponding to a tuple.
template<typename T>
using make_tuple_index = std::make_index_sequence<std::tuple_size<T>::value>;

// map_n -- Map <function> over <tuples> t0,t1,...
template<typename F,
         typename... Ts,
         typename Indices = make_tuple_index<nth<0,Ts...>>>
auto map_n(F&& function, Ts&... tuples)
{
    auto get_element = [&](auto I) { return function(std::get<I>(tuples)...); };
    return invoke_with_pack(Indices{}, [&](auto... Is) {
            return std::make_tuple(get_element(Is)...);
        });
}

Now on to figuring out how to implement fold_left and fold_right with indexes instead of car,cdr and cons.

3 Answers 3

6

Start with this:

namespace utility {
  template<std::size_t...Is>
  auto index_over( std::index_sequence<Is...> ) {
    return [](auto&& f)->decltype(auto) {
      return decltype(f)(f)( std::integral_constant<std::size_t, Is>{}... );
    };
  }
  template<std::size_t N>
  auto index_upto( std::integral_constant<std::size_t, N> ={} ) {
    return index_over( std::make_index_sequence<N>{} );
  }
}

that lets us avoid having to write a whole pile of functions just to expand some parameter packs. index_upto<7>()([](auto...Is){ /* here */ }) gives you a context where you have a bunch of compile time integral constants 0 through 6 in a pack.

template<class F, class T0, class...Tuples>
auto map_over_tuples( F&& f, T0&... t0, Tuples&&... tuples ) {
  using tuple_size = typename std::tuple_size< std::decay_t<T0> >::type;

  auto get_element = [&](auto I){
    return f(std::get<I>(std::forward<T0>(t0)), std::get<I>(std::forward<Tuples>(tuples)...));
  };
  return index_upto<tuple_size{}>()([&](auto...Is){
    return std::make_tuple( get_element(Is)... );
  });
}

in some compilers, use of I has to be replaced with decltype(I)::value in get_element.

1
  • Interesting method for sequencing over parameter packs -- I am going to try that out at some point. Based on your answer I was able to come up with a workable solution that is similar to max66's answer below.
    – RandomBits
    Commented Nov 9, 2017 at 23:05
1

The problem is expanding the parameter packs in the implementation return statement. I need it to expand t in the "inner" loop and Is in the "outer" loop. How is the expansion controlled? And, how do I fix my return statement?

I don't see a simple and elegant way to do this.

It seems to me that you have to decouple the two packs in same way and expand first one then another.

If you see the Yakk solution, you see the inner expansion (t...) through a lambda function with single calling f() in it.

The following is a solution, based on the same principle with a template function, and the use of std::apply to leave the call of f() outside.

Frankly, I think the Yakk solution is more efficient (no need of unuseful tuples creation) so take this example as an oddity

#include <tuple>
#include <iostream>

template <std::size_t I, typename ... Ts>
auto getN (Ts const & ... t)
 { return std::make_tuple(std::get<I>(t)...); }

template<typename F, typename... Ts, std::size_t... Is>
auto mapx_n_impl(const F& f, std::index_sequence<Is...>, const Ts&... t)
{ return std::make_tuple(std::apply(f, getN<Is>(t...))...); }

template <typename F, typename T0, typename ... Ts>
auto mapx_n (F const & f, T0 const & t0, Ts const & ... ts)
{ return mapx_n_impl(f,
     std::make_index_sequence<std::tuple_size<T0>::value> {}, t0, ts...); }

int main ()
 {
   // Test
   auto tup1 = std::make_tuple(1.0, 2.0, 3.0);
   auto tup2 = std::make_tuple(0.0, 1.0, 2.0);
   auto r = mapx_n([](auto x, auto y) { return x - y; }, tup1, tup2);

   std::cout << std::get<0U>(r) << std::endl;
   std::cout << std::get<1U>(r) << std::endl;
   std::cout << std::get<2U>(r) << std::endl;
 }
1
  • This clearly demonstrates the challenge. Based on Yakk's solution, I ended up with something similar to this solution -- only because it fit neatly with the way I was already approaching the problem.
    – RandomBits
    Commented Nov 9, 2017 at 23:03
1

Based on the great solutions I've developed a more general function to transform and fold (reduce) tuples. As you were mentioning fold_left and fold_right in your question, this might be of interest for the discussion.

The basic idea is to apply a second functor to the mapped (a.k.a. transformed) tuple rather than calling std::make_tuple as you did in your solution. This allows many algorithms (e.g. count_if, all_of, any_of etc.) to be implemented easily.

Live example here.

#include <tuple>
#include <functional>

#define FWD(x) std::forward<decltype(x)>(x)

namespace tuple_utils {
    template<class UnaryFunc, std::size_t... Idx>
    constexpr auto apply_for_each_index(std::index_sequence<Idx...>, UnaryFunc&& f) {
        return FWD(f)(std::integral_constant<std::size_t, Idx>{}...);
    }

    template<typename T>
    using make_tuple_index = std::make_index_sequence<std::tuple_size<std::decay_t<T>>::value>;

    template<class... Ts>
    using first_element_t =  typename std::tuple_element<0, std::tuple<Ts...>>::type;

    template<class T>
    constexpr size_t tuple_size_v = std::tuple_size_v<std::decay_t<T>>;

    template<class Map, class Reduce, class... Tuples>
    constexpr auto
    transform_reduce(Map &&transform_func, Reduce &&reduce_func, Tuples&&... tuples) {

        using first_tuple_t = first_element_t<Tuples...>;
        constexpr size_t first_tuple_size = tuple_size_v<first_tuple_t>;
        static_assert(((tuple_size_v<Tuples> == first_tuple_size) && ...), "all tuples must be of same size!");

        auto transform_elements_at = [&](auto Idx){
            return FWD(transform_func)(std::get<Idx>(FWD(tuples))...);
        };
        using Indices = make_tuple_index<first_tuple_t>;
        return apply_for_each_index(
            Indices{},
            [&](auto... Indices) {
                return FWD(reduce_func)(transform_elements_at(Indices)...);
            }
        );
    }
}

int main()
{   
    using tuple_utils::transform_reduce;

    auto make_tuple = [](auto&&... xs) { return std::make_tuple(FWD(xs)...); };

    auto equal = [](auto&& first, auto&&... rest){return ((FWD(first) == FWD(rest)) && ... ); };
    constexpr auto all = [](auto... bs) { return (bs && ...);};
    constexpr auto any = [](auto... bs) { return (bs || ...);};
    constexpr auto count = [](auto... bs) { return (bs + ...); };

    static_assert(transform_reduce(std::equal_to<>(), make_tuple, std::tuple{1,2,3,4}, std::tuple{1,2,7,8}) == std::tuple{true, true, false, false});

    static_assert(transform_reduce(equal, all, std::tuple{1,2,3,4}, std::tuple{1,2,7,8}) == false);
    static_assert(transform_reduce(equal, all, std::tuple{1,2,3,4}, std::tuple{1,2,3,4}, std::tuple{1,2,3,4}) == true);
    static_assert(transform_reduce(equal, any, std::tuple{1,2,3,4}, std::tuple{1,2,7,8}) == true);
    static_assert(transform_reduce(equal, count, std::tuple{1,2,3,4}, std::tuple{1,2,7,8}) == 2);
}

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.