Permuting a typelist

Question

Given a typelist, return a typelist of all the permutations of it. For example:

using Types = typelist<char, int, double>;
using Permutations = typelist<
    typelist<char, int, double>,
    typelist<char, double, int>,
    typelist<int, char, double>,
    typelist<int, double, char>,
    typelist<double, char, int>,
    typelist<double, int, char>
    >;

static_assert(std::is_same<permute_t<Types>, Permutations>{}, "!");

There are two different ways of writing metafunction "overloads": partial specialization or function overloading. I'm still unsure of which is "better", and in this solution I ended up using both, which strikes me as questionable.

The algorithm here is: the permutations of a list is the concatenation of (each element in the list prepended to all the permutations of the list with that element removed).

template <class...> struct typelist { };
template <class T> struct tag { using type=T; };

// remove first instance of type from a typelist
template <class T, class... Ts, class... Rs>
auto remove_first(tag<T>, typelist<T, Ts...>, typelist<Rs...>)
    -> tag<typelist<Rs..., Ts...>>;

template <class T, class F, class... Ts, class... Rs>
auto remove_first(tag<T>, typelist<F, Ts...>, typelist<Rs...>)
    -> decltype(remove_first(tag<T>{}, typelist<Ts...>{}, typelist<Rs..., F>{}));

template <class T, class TL>
using remove_first_t = typename decltype(remove_first(tag<T>{}, TL{}, typelist<>{}))::type;

// concatenate lots of typelists into one typelist
template <class TL>
auto concat(TL ) -> tag<TL>;

template <class... A, class... B, class... Cs>
auto concat(typelist<A...>, typelist<B...>, Cs... cs)
    -> decltype(concat(typelist<A..., B...>{}, cs...));

template <class... Ts>
using concat_t = typename decltype(concat(Ts{}...))::type;

// prepend a type onto a typelist of typelists
template <class T, class... TLs>
auto prepend(tag<T>, typelist<TLs...>)
    -> tag<typelist<concat_t<typelist<T>, TLs>...>>;

template <class T, class TL>
using prepend_t = typename decltype(prepend(tag<T>{}, TL{}))::type;

// get all the permutations of a typelist
template <class T, class=void>
struct permute : tag<typelist<T>> { };

template <class T>
using permute_t = typename permute<T>::type;

template <class... Ts>
struct permute<typelist<Ts...>, std::enable_if_t<(sizeof...(Ts)>1)>>
    : tag<
        concat_t<
            prepend_t<
                Ts,
                permute_t<remove_first_t<Ts, typelist<Ts...>>>
            >...
        >
    >
{ };

Answer 1

You might have some bug in the algorithm.

"testdata"

struct A {};
struct B {};
struct C {};
struct D {};

using Types = typelist<A, B, C, D>;
using Permutations = typelist<
    typelist<A,B,C,D>,
    typelist<A,B,D,C>,
    typelist<A,C,B,D>,
    typelist<A,C,D,B>,
    typelist<A,D,B,C>,
    typelist<A,D,C,B>,
    typelist<B,A,D,C>,
    typelist<B,A,C,D>,
    typelist<B,C,D,A>,
    typelist<B,C,A,D>,
    typelist<B,D,C,A>,
    typelist<B,D,A,C>,
    typelist<C,A,B,D>,
    typelist<C,A,D,B>,
    typelist<C,B,A,D>,
    typelist<C,B,D,A>,
    typelist<C,D,A,B>,
    typelist<C,D,B,A>,
    typelist<D,A,C,B>,
    typelist<D,A,B,C>,
    typelist<D,B,C,A>,
    typelist<D,B,A,C>,
    typelist<D,C,B,A>,
    typelist<D,C,A,B>
>;
static_assert(std::is_same<permute_t<Types>, Permutations>{}, "!");

results in:

prog.cpp:90:1: error: static assertion failed: !
 static_assert(std::is_same<permute_t<Types>, Permutations>{}, "!");
 ^