CODEWITHSUNDEEP
c++list
meguli
meguli

Reputation: 1526

C++ constexpr list with size in its type

I am trying to develop a constexpr, functional list data structure in C++. I am also trying to take advantage of recursive structure of the cons list approach. I had couple of attempts and for those, you can see my past questions. For now, I have settled on to the idea of making the size a part of type, ie. `List. Here is the code: 

#include <iostream>
#include <type_traits>

template <typename T, unsigned int N>
struct list {
    public:

    constexpr list(const T& head, const list<T, N-1> &tail)
    :_length{N}, _head{head}, _tail{tail}
    {}

    const unsigned int _length;
    const T _head;
    const list<T, N-1> _tail;
};

template <typename T, unsigned int N>
constexpr auto head(const list<T, N> &li) {
    return li._head;
}

template <typename T, unsigned int N>
constexpr auto tail(const list<T, N> &li) {
    return li._tail;
}

template <typename T, unsigned int N>
constexpr auto prepend(const T &new_head, const list<T, N> &li){
    return list<T, N + 1>{new_head,
                          list<T, N>{head(li), tail(li)}};
}

template <typename T>
struct list<T, 0>
{
    constexpr static const bool nil = true;
};

template <typename T>
using nil = list<T, 0>;

template <typename Functor, typename T, unsigned int N>
constexpr auto fmap(Functor f, const list<T, N> &li) {
    if constexpr(N == 0)
        return nil<T>{};
    else
        return list{f(head(li)), fmap(f, tail(li))};
}

template <typename T, unsigned int N>
std::ostream& operator<<(std::ostream& str, const list<T, N> &li) {
    if constexpr(N == 0)
        return str;
    else{
        str << head(li) << ' ' << tail(li);
        return str;
    }
}

int main(){
    constexpr auto f = [](int x){ return x * x; };

    constexpr list<char, 2> p2{'U', list<char, 1>{'S', nil<char>{}}};
    constexpr auto p3 = prepend('S', p2);

    constexpr list<int, 2> i1{1, list<int, 1>{2, nil<int>{}}};
    constexpr auto i2 = fmap(f, i1);

    std::cout << p3;
}

Some of it works to some extent. fmap is the one keeping my program from compiling. I get the error

prog.cc:47:16: error: no viable constructor or deduction guide for deduction of template arguments of 'list' return list{f(head(li)), fmap(f, tail(li))};

prog.cc:47:34: note: in instantiation of function template specialization 'fmap<(lambda at prog.cc:61:24), int, 1>' requested here return list{f(head(li)), fmap(f, tail(li))};

prog.cc:67:25: note: in instantiation of function template specialization 'fmap<(lambda at prog.cc:61:24), int, 2>' requested here constexpr auto i2 = fmap(f, i1);

prog.cc:8:15: note: candidate template ignored: couldn't infer template argument 'N' constexpr list(const T& head, const list &tail)

and similar. I am lost here, what is the cause of this error? It seems like compiler deduced the argument N correctly, as it says N=2. I feel like I need to add some base cases related to lists of size zero but could not figure it out.

Upvotes: 0

Views: 1095

Answers (1)

3CxEZiVlQ
3CxEZiVlQ

Reputation: 38824

You have a typo: missing type specifiers when using template struct list. Bellow should work

template <typename Functor, typename T, unsigned int N>
constexpr auto fmap(Functor f, const list<T, N> &li) {
    if constexpr(N == 0)
        return nil<T>{};
    else 
        return list<T, N-1>{f(head(li)), fmap(f, tail(li))};
}

Upvotes: 0

Related Questions