Compile-time efficient n-ary cartesian product of parameter packs with a transformation-CodePudding

In a previous question, solutions were given on how to compute the n-ary cartesian product of parameter packs (see here, here (and here but for tuples)). Basically, we consider the following wrapper:

template <class... Types>
struct pack {};

template <class... Packs>
struct pack_product {/* SOMETHING */}

template <class... Packs>
using pack_product_t = typename pack_product<Packs...>::type;

such that pack_product_t<pack<A0, A1>, pack<B0, B1, B2>, pack<C0, C1>> produces the following:

pack<
    pack<A0, B0, C0>, pack<A0, B0, C1>, 
    pack<A0, B1, C0>, pack<A0, B1, C1>,
    pack<A0, B2, C0>, pack<A0, B2, C1>, 
    pack<A1, B0, C0>, pack<A1, B0, C1>, 
    pack<A1, B1, C0>, pack<A1, B1, C1>,
    pack<A1, B2, C0>, pack<A1, B2, C1>, 
>;

(again see here and here for solutions, even if I think they do not fully work when one of the input packs is the empty pack pack<>). This corresponds to the n-ary cartesian product of sets A×B×C={(a0, b0, c0), ..., (a1, b2, c1)} (set of tuples from a set-theoretic standpoint).

As an important note, one of the tricky part was to produce just two levels of packs, and not n-nested packs in the result (as in pack<pack<pack<A0, B0>, C0>>, ...>).

Now, what I would like to do is the combination of the n-ary cartesian product:

template <template <class> class Function, class... Packs>
struct pack_product_apply {
    using type = /* SOMETHING */
};

template <template <class> class Function, class... Packs>
using pack_product_apply_t = typename pack_product_apply<Function, Packs...>::type;

which basically computes:

pack<
    typename Function<pack<A0, B0, C0>>::type, typename Function<pack<A0, B0, C1>>::type, 
    typename Function<pack<A0, B1, C0>>::type, typename Function<pack<A0, B1, C1>>::type,
    typename Function<pack<A0, B2, C0>>::type, typename Function<pack<A0, B2, C1>>::type, 
    typename Function<pack<A1, B0, C0>>::type, typename Function<pack<A1, B0, C1>>::type, 
    typename Function<pack<A1, B1, C0>>::type, typename Function<pack<A1, B1, C1>>::type,
    typename Function<pack<A1, B2, C0>>::type, typename Function<pack<A1, B2, C1>>::type, 
>;

and just skips the elements which do not compile thanks to SFINAE: for example if the versions with B1 do not provide a valid ::type the result would just be:

pack<
    typename Function<pack<A0, B0, C0>>::type, typename Function<pack<A0, B0, C1>>::type, 
    typename Function<pack<A0, B2, C0>>::type, typename Function<pack<A0, B2, C1>>::type, 
    typename Function<pack<A1, B0, C0>>::type, typename Function<pack<A1, B0, C1>>::type, 
    typename Function<pack<A1, B2, C0>>::type, typename Function<pack<A1, B2, C1>>::type, 
>;

And example of input type function would be:

template <class Pack> 
struct my_type_function;

template <class... Types> 
struct my_type_function<pack<Types...>>: std::common_type<Types...> {};

Computing the cartesian product first and applying the function after on its result is a no-brainer. But I have the feeling (but I may be wrong) that it would be suboptimal from the compiler standpoint.

QUESTION: How to implement pack_product_apply in a compiler-efficient way where the type function would be applied "on-the-fly" when computing each element of the product instead of computing all the element first and then applying the function?

CodePudding user response：

This works with O(1) instantiation depth

template<template<typename...> class F, int N, typename...>
struct fn_typelist {};

template<typename...>
struct typelist {};

template<template<typename...> class F, int N, typename... Ts>
typelist<fn_typelist<F, N, Ts>...> layered(typelist<Ts...>);

template<template<typename...> class F, typename... Ts, typename... Us>
auto operator (fn_typelist<F, sizeof...(Ts)   sizeof...(Us), Ts...>&&,
               fn_typelist<F, sizeof...(Ts)   sizeof...(Us), Us...>&&)
    -> F<Ts..., Us...>;

template<template<typename...> class F, int N, typename... Ts, typename... Us>
auto operator (const fn_typelist<F, N, Ts...>&,
               const fn_typelist<F, N, Us...>&)
    -> fn_typelist<F, N, Ts..., Us...>;

template<typename... Ts, typename... Us>
auto operator (typelist<Ts...>, typelist<Us...>)
    -> typelist<Ts..., Us...>;

template<typename T, typename... Us>
auto operator*(typelist<T>, typelist<Us...>)
    -> typelist<decltype(T{}   Us{})...>;

template<typename... Ts, typename TL>
auto operator^(typelist<Ts...>, TL tl)
    -> decltype(((typelist<Ts>{} * tl)   ...));

template<template<typename...> class F, typename... TLs>
using product_apply_t = decltype((layered<F, sizeof...(TLs)>(TLs{}) ^ ...));

And you use as

struct A0;
struct A1;
struct B0;
struct B1;
struct C0;
struct C1;
struct C2;

using t1 = typelist<A0, A1>;
using t2 = typelist<B0, B1>;
using t3 = typelist<C0, C1, C2>;

template<typename...>
struct fn {};

using p1 = product_apply_t<fn, t1, t2>;
using p2 = product_apply_t<fn, t1, t2, t3>;

using expect1 = typelist<fn<A0, B0>,
                         fn<A0, B1>,
                         fn<A1, B0>,
                         fn<A1, B1>>;

using expect2 = typelist<fn<A0, B0, C0>,
                         fn<A0, B0, C1>,
                         fn<A0, B0, C2>,
                         fn<A0, B1, C0>,
                         fn<A0, B1, C1>,
                         fn<A0, B1, C2>,
                         fn<A1, B0, C0>,
                         fn<A1, B0, C1>,
                         fn<A1, B0, C2>,
                         fn<A1, B1, C0>,
                         fn<A1, B1, C1>,
                         fn<A1, B1, C2>>;

static_assert(std::is_same_v<p1, expect1>);
static_assert(std::is_same_v<p2, expect2>);

Where fn can be swapped with any class template or template alias with suitable parameters.

This instantiates the first (n-1)-ary cartesian product then applies the provided meta function at the n-ary cartesian product. Not being familiar with compilers, I have no idea whether this confers any speedup in compilation times.

_{The implementation is arcane, if you want to ask about it, it likely means you should just stick with producing the pack and iterating. Or Boost.}

CodePudding user response：

This is really the key insight in Boost.Mp11 is that the question you're asking here is really the same question as the other questions.

pack_product is taking the cartesian product of a bunch of packs and turning them all into packs. So that's:

template <class... Packs>
using pack_product = mp_product<pack, Packs...>;

pack_product_apply is the same thing. Or really, pack_product is a special case of pack_product_apply where the function you're applying to each list is pack:

template <template <class...> class F, class... Packs>
using pack_product_apply = mp_product<F, Packs...>;

In other words, pack_product_apply is mp_product.

Now, your formulation is slightly different - you want to take a function that applies to a typelist (F<L>) instead of a function that applies to a pack (F<Ts...>). You can still do that, it's just that you need to pass something into mp_product that first groups the pack (i.e. first applies pack then F):

template <template <class> class F, class... Packs>
using pack_product_apply = mp_product_q<mp_compose<pack, F>, Packs...>;