List<Char> typed constexpr string in C++

Question

I am trying to emulate cons-celllike list structures from functional programming languages, in C++ using constexpr. I have a pair type, to begin with. This is a holder of two different things but supports nested pairs as well. Here is the code.

template <typename E1, typename E2>
struct pair {

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

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

    constexpr auto car() const{
        return _car;
    }

    constexpr auto cdr() const{
        return _cdr;
    }

    friend std::ostream& operator<<(std::ostream& str,
                                    pair<E1, E2> p){
        if(p == pair{})
            return str;
        str << p.car() << " " << p.cdr();
        return str;
    }

    template <typename Functor>
    friend constexpr auto fmap(Functor f,
                               const pair<E1, E2> p){
        if constexpr (std::is_fundamental<E1>::value &&
                      std::is_fundamental<E2>::value)
            return pair{f(p.car()), f(p.cdr())};
        else if(std::is_fundamental<E1>::value &&
                !std::is_fundamental<E2>::value)
        return pair{f(p.car()), fmap(f, p.cdr())};
    }

    const E1 _car;
    const E2 _cdr;
};

template <typename E1, typename E2>
constexpr bool operator==(const pair<E1, E2>& p1, const pair<E1, E2>& p2)
{
    return (p1.car() == p2.car()) && (p1.cdr() == p2.cdr());
}

As a wrapper around this type I have a nested_pair type. This makes it easier for me to work with nested_pairs .aka lists. The actual list is just a typedef around this wrapper. Here is the code.

template <typename Head, typename Tail>
class nested_pair{
    public:

    constexpr nested_pair():p{}
    {}

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

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

    constexpr auto head() const {
        return p.car();
    }

    constexpr auto tail() const {
        return nested_pair<decltype(p.cdr().car()),
                    decltype(p.cdr().cdr())>
                    {p.cdr().car(),
                     p.cdr().cdr()
                    };
    }

    constexpr bool is_empty() const {
        return p == pair<decltype(p.car()),
                         decltype(p.cdr())>
                         {};
    }

    template <typename Functor>
    friend constexpr auto fmap(Functor f, const nested_pair l) {
        const auto res = fmap(f, l.p);
        return nested_pair{res.car(), res.cdr()};
    }

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

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

My nested_pair only allows prepend because append requires O(n) recursive calls if you store your list as a pair of head and tail. Here, I delegate a lot of work to the pair and nested_pair constructor that packs a pair. These works fine I believe. I use following variable template to define lists as nested pairs.

template <typename T>
using list = nested_pair<T, T>;

Now, to the meat of the question, I want to use this list to make a string type, as in list<char>. This should again be all constexpr, as much as we can make it. I have an other version taking const char [] to build constexpr strings but now I want to use structural recursion. Here is my failed attempt.

class lstring{
    public:

    template <std::size_t N>
    constexpr lstring(const char(&cont)[N]) :size{N} {
        size_t ind = N - 1;
        while(ind >= 0){
            content = content.prepend(cont[ind]);
            ind--;
        }
    }

    private:
    const size_t size;
    const list<char> content;
};

Of course this does not work. constexpr constructor goes through a while loop and violates the rules of constexpr, I believe we can't loop in a constexpr function. This also, do not take advantage of recursive structure of lists as well. How can I construct a string this way? Should I use a variadic template that takes a char... args? How can I unpack this structurally? I want to be able to initialize this from a string literal like list<char> s{"hello world"}.

Answer 1

You have a conceptual issue:

Your lstring contains a list<char> which actually is a nested_pair<char, char> which in turn contains a pair<char, char>. Your strings contain always two chars.

Both the string class as well as the list class need to encode their length as part of their type. I.e. you need a list<char, 5> for a list of 5 char (thus containing a pair<char, pair<char, pair<char, pair<char, char>>>>). Otherwise you'd need dynamic memory -- which is a clear no for compile time constant code.

---

Now, on for a demonstration. I hope it'll give you some ideas on how certain things can be implemented. Also it was fun for me ;) Contrary to your design choice I go with a special sentinel value - nil - to mark the end of a list. All of the following code is in a namespace list:

 struct nil {
  template<typename U>
  constexpr auto prepend(U && u) const;
 };

nil (the empty list) has a member function template to add something to the front. It's only declared - not defined - here to break a cyclic dependency.

Note: Whether to even use member functions or free functions here is a matter of personal taste/style. Normally I'd go with free functions (prepend(mylist, element)) but I wanted to mirror your intended usage (mylist.prepend(element)).

Next comes the most important structure - the "pair" - on which lists are built. Named after Lisp's cons cells:

 namespace implementation {
  template<typename T>
  using no_ref_cv = std::remove_cv_t<std::remove_reference_t<T>>;
 }

 template<typename Car, typename Cdr>
 struct cons {
  Car car;
  Cdr cdr;

  template<typename U>
  constexpr auto prepend(U && u) const {
   using implementation::no_ref_cv;
   return cons<no_ref_cv<U>, cons<Car, Cdr>>{std::forward<U>(u), *this};
  }
 };

It's just a simple pair. prepend creates a new cons with the new element as its first element and (a copy of) the current cons as it's second. I remove const and volatile because it's otherwise a bit of a headache (try figuring out why cons<char, cons<char, cons<const char, cons<char, nil>>>> won't convert to cons<char, cons<const char, cons<char, cons<char, nil>>>>)

That said, the implementation of nil::prepend is basically the same:

 template<typename U>
  constexpr auto nil::prepend(U && u) const {
   using implementation::no_ref_cv;
   return cons<no_ref_cv<U>, nil>{std::forward<U>(u), *this};
  }

Also I like free functions to "make" things, so:

 template<typename Car, typename Cdr>
 constexpr auto make_cons(Car && car, Cdr && cdr) {
  using implementation::no_ref_cv;
  return cons<no_ref_cv<Car>, no_ref_cv<Cdr>>{
    std::forward<Car>(car), std::forward<Cdr>(cdr)};
 }

Now, on to your questions:

How can I unpack this structurally? I want to be able to initialize this from a string literal like list<char> s{"hello world"}.

list<char> won't be possible (remember -- you need the length there, too!). But auto s = list::make_list("hello world").

You already have code to get the length of the string literal (parameter type CharT (&array)[N]) and with that N you can build a type with enough nested cons to hold your list:

 namespace implementation {
  template<typename T, std::size_t N>
  struct build_homo_cons_chain {
   using type = cons<T, typename build_homo_cons_chain<T, N - 1u>::type>;
  };

  template<typename T>
  struct build_homo_cons_chain<T, 0u> {
   using type = nil;
  };
 }

N == 0 is just a nil (empty list), everything else is a cons with the element and a list of length N - 1. This allows you to define the correct type for your list, which you could use to default initialize an instance of it and then loop over the car member's to fill it. Something like this:

using list_t = typename implementation::build_homo_cons_chain<char, N>::type;
list_t my_new_list;
// fill my_new_list.car, my_new_list.cdr.car, ... probably with recursion

The issue with this approach is that you require the element type of your list to be both default constructible as well as assignable. Not an issue for char, but these are tough requirements, so we're better of when we copy / move construct the list's elements from the elements supplied in the array (string literal):

 namespace implementation {
  template<std::size_t O, std::size_t C>
  struct offset_homo_builder {
   template<typename T, std::size_t N>
   constexpr auto from( T (&array)[N]) {
    return offset_homo_builder<O - 1u, C - 1u>{}.from(array).prepend(array[N - O]);
   }
  };
  template<std::size_t O>
  struct offset_homo_builder<O, 0u> {
   template<typename T, std::size_t N>
   constexpr auto from( T (&array)[N]) {
    return nil{};
   }
  };
 }

O is an offset relative to the end of the array, C the count of cons we still need to build the list. The from member function template takes an array of length N and prepends the element from the array at N - O to the (shorter) list it builds recursively.

Example: implementation::offset_homo_builder<3,2>::from("ab")

offset_homo_builder<3,2>::from("ab") --> N = 3, O = 3, C = 2
: cons{'b', nil}.prepend('a') => cons{'a', cons{'b', nil}}
  ^
  |--- offset_homo_builder<2, 1>::from("ab") --> N = 3, O = 2, C = 1
       : nil.prepend('b') => cons{'b', nil}
         ^
         |--- offset_homo_builder<1, 0>::from("ab") --> N = 3, O = 1, C = 0 (!specialisation!)
              : nil

The C count is important to leave out the '\0' at the end of the string literal. So now you can make a list with all elements of an array:

 template<typename T, std::size_t N>
 constexpr auto make_homogenous(T (&array)[N]) {
  return implementation::offset_homo_builder<N, N>{}.from(array);
 }

Or build a string where the last element is left out:

 template<std::size_t N, typename CharT, typename = typename std::char_traits<CharT>::char_type>
 constexpr auto make_string(CharT (& array)[N]) {
  static_assert(N > 0, "assuming zero terminated char array!");
  return implementation::offset_homo_builder<N, N - 1>{}.from(array);
 }

Finally, for working with this list you don't need to look at the element's type. Just stop at nil:

 template<typename F, typename Car, typename Cdr>
 constexpr auto fmap(F functor, cons<Car,Cdr> const & cell) {
  return make_cons(functor(cell.car), fmap(functor, cell.cdr));
 }
 template<typename F>
 constexpr auto fmap(F functor, nil const &) {
  return nil{};
 }

foldl, foldr and friends can be implemented similarly. Your operator<< can the be implemented using foldl.

End of the namespace list.

Also, checking that we're still constexpr:

constexpr char inc(char c) {
 return c + 1;
}

static_assert(fmap(inc, list::make_string("ab").prepend('x')).car == 'y', "");

Note the beauty of argument dependent lookup (ADL) ... I can say fmap instead of list::fmap. Good for generic code.