Consuming parameter packs recursively in C++

Question

I want to come up with a Lisp-like cons list implementation in C++. I will give you my attempt first.

template <typename E1, typename E2>
struct pair {

    constexpr pair() :first{E1{}}, second{E2{}}, empty{true} 
    {}

    constexpr pair(E1 const &f, E2 const &s)
    :first{f}, second{s}, empty{false} 
    {}

    E1 first;
    E2 second;
    bool empty;
};

template <typename Head, typename Tail>
struct cons{
    constexpr cons() :_cons{pair<Head, Tail>{}}
    {}

    constexpr cons(Head h, Tail t) :_cons{pair<Head, Tail>{h, t}}
    {}

    template <typename... Args>
    constexpr cons(Args... args)
    {
        // I want cons(1, 2, 3) to expand into below call
        // in main and cons(1, 2, 3, 4) to expand into
        // cons{1, cons{2, cons{3, cons{4, cons<int, int>()}}}}
    }

    constexpr auto car() {
        return _cons.first;
    }

    constexpr auto cdr() {
        return _cons.second;
    }

    pair<Head, Tail> _cons;
};

int main(){
    constexpr cons c{1, cons{2, cons{3, cons<int, int>{}}}};
}

Basically, I want to fill in the part below that implements a variadic constructor.

template <typename... Args>
constexpr cons(Args... args)
{
    // I want cons(1, 2, 3) to expand into below call
    // in main and cons(1, 2, 3, 4) to expand into
    // cons{1, cons{2, cons{3, cons{4, cons<int, int>()}}}}
}

I don't know how can I process parameter packs in such a recursive way. If an initializer_list solution is better, I can look at that as well. In the end, I want to be able to do:

cons c1 = {1, 2, 3, 4};

and it will become

cons{1, cons{2, cons{3, cons{4, cons<int, int>()}}}};

Here is my solution I came up with after asking the question, it is in the make_list function.

My Solution

Answer 1

Not being familiar with Lisp, I went by your description as much as I could. You write helper functions make_cons and delegate the construction to the move constructor

template<typename, typename>
struct cons;

template<typename U>
auto make_cons(U u)
{
    return cons<U, cons<U, U>>{u, {}};
}

template<typename U, typename... Args>
auto make_cons(U u, Args... args)
{
    return cons<U, decltype(make_cons(args...))>{u, make_cons(args...)};
}

template<typename H, typename T>
struct cons
{
    constexpr cons() :_cons{pair<H, T>{}} {}
    constexpr cons(H h, T t) :_cons{pair<H, T>{h, t}} {}
    template<typename... Args>
    constexpr cons(Args... args) : cons(make_cons(args...)) {}

    pair<H, T> _cons;
};

template<typename U, typename... Args>
cons(U, Args...) -> cons<U, decltype(make_cons(std::declval<Args>()...))>;

template<typename U>
cons(U) -> cons<U, cons<U, U>>;

By your example, I'm assuming you want to have as the last term be cons<U, U> where U is the same type as the terms coming before. You use it as

auto c1 = make_cons(1, 2, 3, 4);
cons c2 = {1, 2, 3, 4};
print<decltype(c1)> p1;
print<decltype(c2)> p2;

Live (read the error message to see the resulting type)

Answer 2

@PasserBy 's answer inspired me to do that:

////
template <typename Head, typename Tail>
struct cons{
    constexpr cons() :_cons{pair<Head, Tail>{}}
        {}

    constexpr cons(Head h, Tail t) :_cons{pair<Head, Tail>{h, t}}
        {}

    constexpr auto car() const {
        return _cons.first;
    }

    constexpr auto cdr() const {
        return _cons.second;
    }

    pair<Head, Tail> _cons;
};
////
template <typename Head, typename Tail>
constexpr cons<Head, Tail> makeCons(Head h, Tail t) {
    return cons<Head, Tail>(h, t);
}

template <typename Head, typename... Args>
constexpr auto makeCons(Head h, Args... args) {
    return makeCons(h, makeCons(args...));
}
////

The first part is exactly yours, but with removal of your varadic template constructor. Also made the getters const, to be able to be used in calling code (calling a constexpr with a non-const method is a compile-time error).

The second part is TWO template functions, the second is the varadic version, where it takes a head, and varadic template to recursively pass it to another version to itself, the first is the specialization of the template function where it accepts only two arguments.

So the template function will keep resolving to itself (with decreasing one argument), till it is only two, where it will be resolved to the creation of a cons with a pair.

Then call it from your code like this:

constexpr auto c = makeCons(1, 2, 3, 4);
std::cout << c.car();
std::cout << c.cdr().car();
std::cout << c.cdr().cdr().car();

makeCons(1, 2, 3, 4) will recurively resolve to makeCons(1, makeCons(2, 3, 4)), which will resolve to makeCons(1, makeCons(2, makeCons(3, 4)))

makeCons(3, 4) is the specialized version