# Persistent List with constexpr and pointers

I am trying to implement a linked list in C++, functional and persistent. Before looking into sample implementations, I tried to come up with my own as an exercise.

I came up with two versions:

1. One is using pointers as is customary in C++. I am trying to set up an interface that respects structural sharing.
2. The other one is using full-constexpr. It is basically a compile-time list, if you do not use operator<<.

To begin, the complete code is so long so I am going to start with a link to Compiler Explorer that contains all of the code. Here is the code. There, "C++ Source 1" contains the code for pointer based implementation. "C++ Source 2" contains more functional implementation. You can find respective compiler outputs on the right pane.

First one is the pointer-based version:

#include <iostream>
#include <type_traits>

static size_t total_allocated = 0;

namespace chops {
template <typename T>
public:
using ValueType = T;

template <typename ValueType>
struct list_node{
ValueType val;
list_node *next;

const ValueType head() const {
return val;
}
const list_node *tail() const {
return next;
}

list_node *Clone(const list_node* other){
if(other == nullptr)
return nullptr;

list_node* result = new list_node;
total_allocated += sizeof(list_node<ValueType>);
result->val = other->val;
result->next = Clone(other->next);
return result;
}

friend std::ostream& operator<<(std::ostream& str,
const list_node<ValueType> *ci){
if(ci == nullptr){
str << "\n";
return str;
}
str << ci->head() << " " << ci->tail();
return str;
}
};

using ConstListIterator = const list_node<ValueType>*;
using ListIterator = list_node<ValueType>*;
static const size_t node_size = sizeof(list_node<ValueType>);

};

}

a_new_copy = true;
std::cout << "copy is happening\n";
}

{
if(_head != nullptr && !a_new_copy){
std::cout << "Calling the destructor\n";
}else
{
ListIterator current = _head;
while(current != nullptr){
std::cout << "Calling the destructor\n";
ListIterator next = current->next;
current->next = nullptr;
delete current;
current = next;
}
}
}

auto prepend(T val) const{
ListIterator new_node = new list_node<ValueType>;
total_allocated += sizeof(list_node<ValueType>);
new_node->val = val;
}

auto head() const {
}

ConstListIterator tail() const {
}

bool is_empty() const {
return _head == nullptr;
}

private:
{};

bool a_new_copy;
};

template <typename T>
std::ostream& operator<<(std::ostream& str, const linked_list<T>& l){
if(l.is_empty()){
str << "\n";
return str;
}
str << l.head() << " " << l.tail();
return str;
}

}

int main()
{
if(ll.is_empty())
std::cout << "Empty list!\n";

const auto ll2 = ll.prepend(6);
const auto ll3 = ll2.prepend(5);
const auto ll4 = ll3.prepend(4);
const auto ll5 = ll4.prepend(3);
const auto ll6 = ll5.prepend(2);
const auto ll7 = ll6.prepend(1);

std::cout << ll7;
std::cout << ll6.tail();
std::cout << lcopy;

if(std::is_same_v<decltype(ll), decltype(ll7)>)
std::cout << "Total allocated memory is " << total_allocated << " bytes\n";

std::cout << "Size of int is: " << sizeof(int) << " \n";
std::cout << "Size of list_node<int> is: "
<< " \n";

}


And, here is the constexpr version:

#include <iostream>
#include <type_traits>

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

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

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

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.empty)
return str;
str << p.car() << " " << p.cdr();
return str;
}

const E1 _car;
const E2 _cdr;
bool empty;
};

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());
}

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

constexpr list():p{}, empty{true}
{}

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

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

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

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

bool is_empty() const {
return empty;
}

friend std::ostream& operator<<(std::ostream& str,
str << l.p;
str << "\n";
return str;
}

private:
bool empty;
};

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

}

int main()
{
constexpr auto l2 = l1.prepend(6);
constexpr auto l3 = l2.prepend(5);
constexpr auto l4 = l3.prepend(4);
constexpr auto l5 = l4.prepend(3);
constexpr auto l6 = l5.prepend(2);
constexpr auto l7 = l6.prepend(1);

constexpr auto lcopy = l7.tail();
std::cout << l5;
std::cout << l4.tail();
std::cout << lcopy;
}


I think these are working somewhat correctly but I need to ask couple of questions.

1. Are there any errors that I am missing? How would you improve this code, in general terms?

2. Why is the pointer-based implementation generating so much longer assembly, assuming this indicates a slower code. They are doing pretty-much the same thing but compile-time version is much faster. Look at the next question for further points.

3. Is my second implementation truly constexpr? I can see a compile-time version can be faster, since computation happens at compile-time. But in the sample, I am not putting constexpr in my declarations. I can construct those lists in main as constexpr as well. For example, I can do this, adding constexpr:

constexpr chops::linked_list<int> l1;
constexpr auto l2 = l1.prepend(6);
constexpr auto l3 = l2.prepend(5);
constexpr auto l4 = l3.prepend(4);
constexpr auto l5 = l4.prepend(3);
constexpr auto l6 = l5.prepend(2);
constexpr auto l7 = l6.prepend(1);

constexpr auto lcopy = l7.tail();
std::cout << l5;
std::cout << l4.tail();
std::cout << lcopy;


and if I comment out the I/O part, this generates nearly no-code at all which is expected right, assuming all the computation happens at compile-time?

4. My compile-time version is more like lisp const-lists. They are made out of pairs which also lives in chops namespace. So tail of a list is just another nested-pair. This complicates things a-little bit. I had to invent an empty pair. If you think as a mathematical abstraction, an empty pair might not be a good idea. But pointer-based version can just use nullptr to indicate empty list. The other problem with compile-time version is that, I wrapped list into a linked_list through a variable template. But in reality, every list has a different type. After you prepend, you get a new list and it's type is not the same as input list. Types in the compile-time version contains all the structure of the list. For example type of (1 2 3) is list<int, pair<int, int>>. Would this pose a disadvantage in terms of generic usage? Is it better if all had the type List<T>?

5. What should be the copy-semantics for a purely functional list? Right now, I am treating every copy as if a new world of lists created, separate from the previous list worlds. Is there any mistakes here? My destructor is just deleting the prepended node, unless it is the beginning of a new copy. You can check this out in the code, in the pointer-based version. Compile-time version has no destructor or copy constructor. It is all value-semantics. Which would you prefer?

6. How would you implement multithreading and fmap-like facility in the compile-time version?

7. Would move-semantics help the performance of the pointer-based version?

8. What are the code-smells you can point out?

9. Is the heavy use of recursion problematic here?

• Welcome to Code Review! Unfortunately your question is off-topic as of now, as the code to be reviewed must be present in the question. Please add the code you want reviewed in your question. Thanks! – Vogel612 Apr 9 '18 at 9:56
• I'm a bit embarrassed because you ask a review of two very different pieces of code. They aren't two different implementations of the same concept. I believe you should ask about one or the other, but not both. About the second kind of list, there is no difference between a pair and a list, so it isn't really useful to write two different classes. Lists in functional or functional-friendly languages are algebraic types (in this instance either nil or a cons) we don't really have in C++, hence the weird empty pair. – papagaga Apr 9 '18 at 13:57
• Is this supposed to be a comparative-review (as in "which of these should I use?")? If not, it might be better as two questions. – Toby Speight Apr 9 '18 at 15:25
• @papagaga I probably did something wrong there, I thought about it. But, performance questions and C++ type system related questions made me believe that it is better if i gave a sample implementation of both. – meguli Apr 9 '18 at 17:18