implementing typelist replace operation using variadic templates

Question

I'm trying to implement a ReplaceAll metafunction for variadic template version of typelists (inspired by Modern C++ Design) and so far I could achieve the desired outcome with the following code:

template <typename... Elements> struct Typelist {};

//
// helper metafunction to set "Head" of typelist
//
template <typename TList, typename T> struct PushFrontT;

template <typename... Elements, typename T>
struct PushFrontT<Typelist<Elements...>, T> {
    using Result = Typelist<T, Elements...>;
};

//
// metafunction to replace all occurences of "T" with "U"
//
template <typename TList, typename T, typename U> struct ReplaceAll;

template <typename T, typename U>
struct ReplaceAll<Typelist<>, T, U> {
    using Result = Typelist<>;
};

template <typename... Tail, typename T, typename U>
struct ReplaceAll<Typelist<T, Tail...>, T, U> {
    using Result = typename PushFrontT<
        typename ReplaceAll<Typelist<Tail...>, T, U>::Result, U
    >::Result;
};

template <typename Head, typename... Tail, typename T, typename U>
struct ReplaceAll<Typelist<Head, Tail...>, T, U> {
    using Result = typename PushFrontT<
        typename ReplaceAll<Typelist<Tail...>, T, U>::Result, Head
    >::Result;
};

Which returns a typelist in the form of Typelist<T1, T2, T3> (effectively replacing all occurrences of type T with the target type U).

Now the problem is that when I try to not use the helper metafunction PushFrontT, a nested typelist structure would be created in the form of Typelist<T1, Typelist<T2, Typelist<T3, Typelist<>>>> which is incorrect (despite replacing all instances of T with U).

The code for the incorrect version is as follows:

template <typename T, typename U>
struct ReplaceAll<Typelist<>, T, U> {
    using Result = Typelist<>;
};

template <typename... Tail, typename T, typename U>
struct ReplaceAll<Typelist<T, Tail...>, T, U> {
    using Result = Typelist<U,
        typename ReplaceAll<Typelist<Tail...>, T, U>::Result
    >;
};

template <typename Head, typename... Tail, typename T, typename U>
struct ReplaceAll<Typelist<Head, Tail...>, T, U> {
    using Result = Typelist<Head,
        typename ReplaceAll<Typelist<Tail...>, T, U>::Result
    >;
};

Based on my limited knowledge of variadic templates, I think the additional Typelist is a side effect of a pack expansion but I'm not sure.
Here is a simple test program to check the aforementioned code:

#include <type_traits>

int main () {
    using tlist = Typelist<int, char, int, double>;

    static_assert(
        std::is_same<
        typename ReplaceAll<tlist, int, long>::Result,
        Typelist<long, char, long, double>>::value,
        "Incorrect typelist!"
    );

    return(0);
}

In short, my question is how should I get rid of the excessive nested Typelists without using an outside helper metafunction such as PushFrontT?

Answer 1

You might simplify your code and get rid of the recursion with

template <typename TList, typename T, typename U> struct ReplaceAll;

template <typename ... Ts, typename T, typename U>
struct ReplaceAll<Typelist<Ts...>, T, U>
{
    using Result = Typelist<std::conditional_t<std::is_same_v<Ts, T>, U, Ts>...>;
};

Demo