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

First, you only need non-empty packs (no-args call is already handled earlier). Should be straightforward:

template<typename... Tl> cons(Head h, Tl &&...tl)
    : cons_(std::move(h), Tail(std::forward<Tl>(tl)...)) {}

Btw, don't start identifiers with underscore.

---

Every answer here has one notable flaw: the structure constructed is an improper list: the last cdr in the sequence is not an empty list but rather a sequence. To construct proper lists, you'd have to end them properly. Something like:

struct Nil {};
inline bool operator==(Nil, Nil) { return true; }
inline bool operator!=(Nil, Nil) { return false; }
inline Nil make_cons() { return Nil{}; }

template<typename Car> inline auto make_cons(Car &&h) {
     return cons<std::remove_reference_t<Car>, Nil>{std::forward<Car>(h), Nil{}};
}

template<typename Car, typename Cadr, typename... Tail>
inline auto make_cons(Car &&first, Cadr &&second, Tail &&...rest) {
     return make_cons(std::forward<Car>(first)
                      , make_cons(std::forward<Cadr>(second), std::forward<Tail>(rest)...));
}

(For those unfamiliar with Lisp, Alexandrescu's type lists, that were probably one of the inspirations for C++11's variadic patterns, are basically the same.)

Answer 2

Every answer here has one serious flaw: the structure constructed is an improper list: the last cdr in the sequence is not an empty list but rather a sequence. To construct proper lists, you'd have to end them properly. Something like:

struct Nil {};
inline bool operator==(Nil, Nil) { return true; }
inline bool operator!=(Nil, Nil) { return false; }
inline Nil make_cons() { return Nil{}; }

template<typename Car> inline cons<std::remove_reference_t<Car>, Nil> make_cons(Car &&h) {
     return cons<Car, Nil>{std::forward<Car>(h), Nil{}};
}
template<typename Car, typename Cadr, typename... Tail> inline auto make_cons(Car &&first, Cadr &&second, Tail &&...rest) {
     return make_cons(std::forward<Car>(first)
                      , make_cons(std::forward<Cadr>(second), std::forward<Tail>(rest)...));
}

Answer 3

If you want to avoid recursions in instantiation, you might do something like that:

template <typename T>
struct wrap_cons
{
    T&& t;
};


template <typename T, typename Head, typename Tail>
constexpr auto operator +(wrap_cons<T>&& w, cons<Head, Tail> c)
{
    return cons<T, cons<Head, Tail>>{std::forward<T>(w.t), std::move(c)};
}

template <typename T, typename U>
constexpr auto operator +(wrap_cons<T>&& w, wrap_cons<U>&& c)
{
    return cons<T, U>{std::forward<T>(w.t), std::forward<U>(c.t)};
}

template<typename... Args>
constexpr auto make_cons(Args... args)
{
    return (wrap_cons<Args>{std::forward<Args>(args)} + ...);
}

Demo

It might help to have bigger list.

Btw, std::tuple seems more appropriated that the old type-list.

Answer 4

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 5

@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