Recursively folding a parameter pack to resolve placeholder types

Question

Notice: Followup to this question

After asking this question about parameter pack folding into pairs, I noticed that I need to retain the complete type of the previously folded type as the left pair type.

For example:

Fold<char, int, long, double> f;

must evaluate to

std::tuple<
    std::pair<char
             , int>,
    std::pair<std::pair<char, int> /* <-- the previous resulting type */
             , long>,
    std::pair<std::pair<std::pair<char, int>, long> /* the previous type again */
             , double>
> f;

Context to this problem

The reason why I need this, is because the types which have to be "folded" can be placeholder types. The placeholders "real" type can only be known when both having the fully expanded type to the left as well as the unexpanded type. The leftmost type never contains placeholders.

Let me illustrate this with a quick example:

struct CopyTypeFromPreviousArgumentTag { };

template<typename T = CopyTypeFromPreviousArgumentTag>
struct Foo;

template<typename T...>
struct Bar {
    /* Here fold will not use std::pair, but a resolver type that takes both A and B and gives back the resolved B */
    Fold<T...> expanded;
};

Now Bar can be used like this:

Bar< Foo<int>
   , Foo<>
   , Foo<>
   , Foo<double>
   , Foo<>
   > f;

and the internal type decltype(f::expanded) will be:

std::tuple< Foo<int>
          , Foo<int>
          , Foo<int>
          , Foo<double>
          , Foo<double>
          >;

EDIT: The Bar class is actually not restricted to any class type it might hold. It can be a mixture of several types. So see the Foo class as a placeholder for some type Foo where a resolver type traits exists given the previous resolved type: ResolveType<PreviouslyResolvedType, CurrentType>::Type will give the resolved type correctly. Hence the std::pair idiom.

My current attempt

I tried to implement the recursion by building upon the answer from the linked question, but can't get it to work.

namespace Detail {

template<typename, typename...>
struct Fold;

template
    < size_t... Indices
    , typename... Types
> struct Fold<std::index_sequence<Indices...>, Types...> {
    using Tuple = std::tuple<Types...>;
    using Type = std::tuple<std::pair /* use std::pair just to match the first example */
        //< std::tuple_element_t<Indices, Tuple>
        < typename Fold
            < std::tuple_element_t<Indices, Tuple>
            , std::make_index_sequence<Indices>
            , Types...>::Type; /* Tuple can't be expanded :( */
        , std::tuple_element_t<Indices + 1, Tuple>
        >::Type...>;
};

} /* namespace Detail */


template<typename... Types>
using Fold = typename Detail::Fold<std::make_index_sequence<sizeof...(Types) - 1>, Types...>::Type;

Sorry but I don't understand: from `Bar, Foo<>, Foo<>, Foo, Foo<>> f;` do you want obtain a `type` `std::tuple< Foo, Foo, Foo, Foo, Foo>;`? And what about `std::pair`s? Another question: all types that you want to fold are of type `Foo`? — max66, Feb 24 '18 at 20:43
@NirFriedman I have edited the question to include the extended example using four types. — nyronium, Feb 24 '18 at 22:37

Passer By · Answer 1 · 2018-02-24T21:42:42.770

4

The linked question is a very convoluted way of doing this. If it was a runtime problem, it will obviously be solved with a one-pass algorithm, metaprogramming is no different.

struct copy_prev {};

template<typename T = copy_prev>
struct Foo {};

template<typename... Ts, typename T>
auto operator+(std::tuple<Ts...>, Foo<T>)
    -> std::tuple<Ts..., Foo<T>>;

template<typename... Ts>
auto operator+(std::tuple<Ts...> t, Foo<copy_prev>)
    -> std::tuple<Ts..., select_last_t<Ts...>>;

template<typename... Ts>
using fold_t = decltype((std::tuple<>{} + ... + std::declval<Ts>()));

Where select_last_t is implemented as

template<typename T>
struct tag
{
    using type = T;
};

template<typename... Ts>
struct select_last
{
    using type = typename decltype((tag<Ts>{}, ...))::type;
};

template<typename... Ts>
using select_last_t = typename select_last<Ts...>::type;

Live

edited Feb 24 '18 at 21:42

answered Feb 24 '18 at 21:20

Passer By

19,325
6
49
96

Again, thanks for the great answer. Maybe I oversimplified the problem, but the `Foo` class can actually be any class with any amount of template parameters. This is the reason why I wanted to use a type trait like `ResolveType::Type` to resolve the type. Can this be adopted in a similar scheme? – nyronium Feb 24 '18 at 22:20
I had never thought to use comma to detect the last type in a list. Great. But is really necessary the use of `tag`? I mean... what about `template struct lastType { using type = std::remove_reference_t(),...))>; };`? – max66 Feb 24 '18 at 22:28
@max66 You'd run into a few issues, first is decaying and references, which can be undesirable in typelists, mentioned in Yakk's answer . Then is the problem of overloaded comma operators. Having a tag type just makes it all nicer. – Passer By Feb 25 '18 at 03:32
@nyronium Use SFINAE and overload `operator+` to get practically any functionality you want. And yes if you can't generalize from an answer to your question, you are oversimplifying – Passer By Feb 25 '18 at 03:35
@PasserBy - you're right: to use `std::declval` ins't a good idea 'cause the risk of an overloaded comma operator. I didn't think about it. – max66 Feb 25 '18 at 12:57

score 2 · Answer 2 · answered Feb 24 '18 at 21:15

Not sure to understand what do you want... but if your Bar struct accept only Foo types... that is: if can be written as follows

template <typename ...>
struct Bar;

template <typename ...Ts>
struct Bar<Foo<Ts>...>
 { /* something */ };

and in Bar you want a type so that from

 Bar<Foo<int>, Foo<>, Foo<>, Foo<double>, Foo<>>

you want the internal type

 std::tuple<Foo<int>, Foo<int>, Foo<int>, Foo<double>, Foo<double>>

where the unexpressed (defaulted) argument for Foo are substituted with the last expressed argument... I don't see an elegant solution.

The best I can imagine is the development of a type helper as follows (where, for the sake of brevity, I've renamed ctfpat the former CopyTypeFromPreviousArgumentTag)

template <typename...>
struct fooFolder;

// error case: the first type of Bar is ctfpat (non impemented;
// generate compile time error)
template <typename ... Ts>
struct fooFolder<std::tuple<>, ctfpat, ctfpat, Ts...>;

template <typename ... Tps, typename Tprev, typename T0, typename ... Ts>
struct fooFolder<std::tuple<Tps...>, Tprev, T0, Ts...>
   : fooFolder<std::tuple<Tps..., Foo<T0>>, T0, Ts...>
 { };

template <typename ... Tps, typename Tprev, typename ... Ts>
struct fooFolder<std::tuple<Tps...>, Tprev, ctfpat, Ts...>
   : fooFolder<std::tuple<Tps..., Foo<Tprev>>, Tprev, Ts...>
 { };

template <typename Tpl, typename Tprev>
struct fooFolder<Tpl, Tprev>
 { using type = Tpl; };

and Bar become

template <typename ...>
struct Bar;

template <typename ...Ts>
struct Bar<Foo<Ts>...>
 {
   using foldedType = typename fooFolder<std::tuple<>, ctfpat, Ts...>::type;

   foldedType expanded;
 };

The following is a full compiling example

#include <tuple>
#include <type_traits>

struct ctfpat // copy type from previous argument tag
 { };

template <typename T = ctfpat>
struct Foo
 { };

template <typename ...>
struct fooFolder;

// error case: the first type of Bar is ctfpat (non impemented;
// generate compile time error)
template <typename ... Ts>
struct fooFolder<std::tuple<>, ctfpat, ctfpat, Ts...>;

template <typename ... Tps, typename Tprev, typename T0, typename ... Ts>
struct fooFolder<std::tuple<Tps...>, Tprev, T0, Ts...>
   : fooFolder<std::tuple<Tps..., Foo<T0>>, T0, Ts...>
 { };

template <typename ... Tps, typename Tprev, typename ... Ts>
struct fooFolder<std::tuple<Tps...>, Tprev, ctfpat, Ts...>
   : fooFolder<std::tuple<Tps..., Foo<Tprev>>, Tprev, Ts...>
 { };

template <typename Tpl, typename Tprev>
struct fooFolder<Tpl, Tprev>
 { using type = Tpl; };

template <typename ...>
struct Bar;

template <typename ... Ts>
struct Bar<Foo<Ts>...>
 {
   using foldedType = typename fooFolder<std::tuple<>, ctfpat, Ts...>::type;

   foldedType expanded;
 };

int main()
 {
   using t1 = typename Bar<Foo<>, Foo<int>, Foo<>, Foo<double>,
                           Foo<>>::foldedType;
   using t2 = std::tuple<Foo<int>, Foo<int>, Foo<int>, Foo<double>,
                         Foo<double>>;

   static_assert( std::is_same<t1, t2>{}, "!" );
 }

I apologize if I have oversimplified my problem. See my edited question please. — nyronium, Feb 24 '18 at 22:23

score 0 · Accepted Answer · answered Feb 25 '18 at 00:09

I start my solution by building something that knows how to create the nth type. It's just a pair of the previous created type, and the current source type, so:

template <std::size_t I, class T>
struct element {
  using type = std::pair<typename element<I - 1, T>::type,
                         std::tuple_element_t<I + 1, T>>;
};

template <class T>
struct element<0, T> {
  using type =
      std::pair<std::tuple_element_t<0, T>, std::tuple_element_t<1, T>>;
};

All we really need to do now is put the input types into a tuple, grab an integer pack, and feed the tuple and unfold the integer pack through element, into a new tuple. No problem:

template <class I, class... Ts>
class fold_helper;

template <std::size_t... Is, class... Ts>
class fold_helper<std::index_sequence<Is...>, Ts...> {

  using tup = std::tuple<Ts...>;

public:
  using type = std::tuple<typename element<Is, tup>::type...>;
};

template <class... Ts>
using Fold = typename fold_helper<std::make_index_sequence<sizeof...(Ts)-1>,
                                  Ts...>::type;

Finally, let's check this works:

int main() {

  static_assert(
      std::is_same<Fold<char, int, long, double>,
                   std::tuple<std::pair<char, int>, //
                              std::pair<std::pair<char, int>, long>,
                              std::pair<std::pair<std::pair<char, int>, long>,
                                        double>>>::value,
      "");

  return 0;
};

This program compiled for me.

Recursively folding a parameter pack to resolve placeholder types

Notice: Followup to this question

Context to this problem

My current attempt

3 Answers3

Linked