CODEWITHSUNDEEP
c++
meguli
meguli

Reputation: 1526

Compile-time constexpr cons lists like lisp in C++

I want to have a linked list like lisp cons lists. I want to do this on compile time in C++, utilizing templates and constexpr as much as I can. Here is my attempt, I think you'll see immediately what is wrong.

#include <iostream>

namespace chops {
template <typename E1, typename E2>
struct pair {

    constexpr pair()
    : _car{}, _cdr{}
    {}

    constexpr pair(const E1 &car)
    :_car{car}, _cdr{}
    {}

    constexpr pair(const E1 &car, const E2 &cdr)
    :_car{car}, _cdr{cdr}
    {}

    constexpr auto car() const{
        return _car;
    }

    constexpr auto cdr() const{
        return _cdr;
    }

    const E1 _car;
    const E2 _cdr;
};

template <typename E1, typename E2>
std::ostream& operator<<(std::ostream& str,
                         pair<E1, E2> p){
    str << p.car() << " " << p.cdr();
    str << "\n";
    return str;
}

template <typename Head, typename Tail>
class list{
    public:
    constexpr list():p{}
    {}

    constexpr list(Head h)
    :p{h}
    {}

    constexpr list(Head h, Tail t)
    :p{h, t}
    {}

    constexpr auto append(Head h) const{
        return list<Head, decltype(p)>{h, p};
    }

    friend std::ostream& operator<<(std::ostream& str,
                                    list<Head, Tail> l){
        str << l.p;
        return str;
    }

    private:
    pair<Head, Tail> p;
};
}



int main()
{
    //constexpr const chops::pair p1{3, 4};
    //constexpr const chops::pair<int, decltype(p1)> p2{2, p1};
    //constexpr const chops::pair<int, decltype(p2)> p3(1, p2);

    constexpr chops::list<int, int> l1{6, 5};
    auto l2 = l1.append(4); 
    auto l3 = l2.append(3); 
    auto l4 = l3.append(2); 
    auto l5 = l4.append(1); 
    std::cout << l5;
}

You can see that my list is just a wrapper around pair actually and I am losing the type safety. l1 has type list<int, int> and others are just nested pairs. This is not good, I want all of them to have the type list<T>. How can I handle the type Tail without getting it into template parameter of list class. Things should stay constexpr, of course.

Upvotes: 0

Views: 371

Answers (1)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275800

add a copy ctor:

constexpr list(list const& l):p{l.p}
{}

then:

template<class NewHead>
constexpr auto prepend(NewHead h) const{
    return list<NewHead, list>{h, *this};
}

(I renamed the function; it pushes in front, not at the tail).

To append you need some pattern matching. It is best done as a free function.

template<class Head, class Tail>
constexpr auto append( Head h, Tail t ) {
  return list<Head, Tail>(h, t);
}

and within list:

template<class NewTail>
friend constexpr auto append( list h, NewTail t ) {
  return append( car(h.p), append( cdr(h.p), t ) );
}

that might work if I got the overloading right.

Use would look like:

auto l2 = append(l1,4);

Upvotes: 2

Related Questions