Functional-style list in C++

I've implemented a functional-style list structure in C++. It seems okay so far, and doing custom allocation for list nodes improves performance greatly. I omitted that part here for simplicity.

The mutability of the list is intentional, as the application I'm thinking of requires a lot of state updates. I wrote this code instead of using std::forward_list because

• I need to instantiate the list with incomplete types.

• The algorithm is recursive (some kind of tree search), so the code will look better with a functional data structure.

Any advice is welcome.

```
#include
#include
#include

template
struct List
{
T head;
std::unique_ptr> tail;
};

template
std::unique_ptr> add(const T &t, std::unique_ptr> &&l)
{
return std::unique_ptr>(new List{t, std::move(l)});
}

template
std::unique_ptr> list()
{
return std::unique_ptr>();
}

template
std::unique_ptr> list(const T &t, const Ts &...ts)
{
return add(t, list(ts...));
}

template
std::unique_ptr> copy(const std::unique_ptr> &l)
{
if (l == list())
{
return list();
}
else
{
return add(l->head, copy(l->tail));
}
}

template
std::unique_ptr> merge(const std::unique_ptr> &a, const std::unique_ptr> &b)
{
if (a == list())
{
return copy(b);
}
else
{
return add(a->head, merge(a->tail, b));
}
}

template
std::unique_ptr> filter(const std::unique_ptr> &l, Filter f)
{
if (l == list())
{
return list();
}
else if (f(l->head))
{
return add(l->head, filter(l->tail, f));
}
else
{
return filter(l->tail, f);
}
}

template
std::unique_ptr> sort(const std::unique_ptr> &l)
{
if (l == list())
{
return list();
}
else
{
return merge(sort(filter(l->tail, &{return t head;})), add(l->head, sort(filter(l->tail, &{return t >= l->head;}))));
}
}

template
std::ostream &operator> &l)
{
if (l == list())
{

This looks pretty solid. I don't have any major comments. Just lots of minor ones.

Unique or Shared

Why unique_ptr as a design choice over shared_ptr? The latter would let you be able to take shallow copies to your lists without having to have references everywhere. I'm not saying that shared_ptr is strictly better, more than it's something worth considering if you have not already. Either way, both are strictly better than raw pointers, so you're already on the right track.

std::unique_ptr>

That is a huge mouthful to type every time. And it is the only type that matters. So let's just alias it:

template 
using FList = std::unique_ptr>;

Alternatively, rename List<> to Cons or Node so that the alias can be named List. To avoid confusion, I will use FList throughout the rest of this review.

cons()

The standard name for a list structure that is a value and a list is a "cons" cell. As in construct. Just for consistency, you should rename your add() to cons():

template
FList cons(const T& t, FList&& xs)
{
    return {new List{t, std::move(xs)}};
}

Now, this is less usable than it could be, simply because you can't do something like:

FList x = ...;
cons(4, std::move(x)); // error

For that, let's loosen the restrictions:

template ::value>
          >
FList cons(U&& u, FList&& xs)
{
    return {new List{std::forward(u), std::move(xs)}};
}

You'll note that I changed your variable from l to xs. 1 is a terrible variable name as it's very easy to mistake for l. So easy to mistake that you probably didn't notice that I wrote one the first time and el the second time.

list()

Going on the theme of loosening restrictions, let's do that here too:

template
FList list()
{
    return {}; // shorter
}

template
FList list(U&& u, Us&&... us)
{
    return cons(std::forward(u), 
                list(std::forward(us)...)
                );
}

That will let you write:

auto nums = list(1, '4', 5ull);

Checking for empty list

In your functions, you tend to start with:

if (l == list())

But std::unique_ptr is usable in a boolean context as-is. So all of those checks you can write much simpler:

template
FList copy(const FList& xs)
{
    if (!xs)
    {
        return {};
    }
    else
    {
        return cons(xs->head, copy(xs->tail));
    }
}

Note that in the interest of being functional, we also probably want:

template 
T const& car(FList const& xs) { // or T& if you want mutability
    return xs->head;
}

template 
FList const& cdr(FList const& xs) { 
    return xs->tail;
}

So that this becomes:

return cons(car(xs), copy(cdr(xs)));

filter()

Could avoid some code duplication here:

template
FList filter(const FList& xs, Filter f)
{
    if (!xs) {
        return {};
    }

    auto tail = filter(cdr(xs), f);
    return f(car(xs)) 
           ? cons(car(xs), std::move(tail)) 
           : tail;
}

sort()

This function deserves a comment solely for:

return merge(sort(filter(l->tail, [&](const T &t){return t head;})), add(l->head, sort(filter(l->tail, [&](const T &t){return t >= l->head;}))));

It's like you never want anybody to read your code. So you're basically trying to do a sort of quicksort based on partitioning the head. Let's just write that in more than one line of code (and rename it to sorted to mimic python and make it sound less like you're sorting in place):

template
FList sorted(const FList& xs)
{
    if (!xs) return {};

    auto left = filter(cdr(xs), [&](const T& val){ return val < car(xs); });
    auto right = filter(cdr(xs), [&](const T& val){ return !(val < car(xs)); });

    return merge(sorted(left), 
                 cons(car(xs), sorted(right)));
}

I find that a ton easier to read. The reason I wrote the second filter with ! is that it naturally lends itself to adding a custom comparator:

template >
FList sorted(const FList& xs, Cmp cmp = {})
{
    if (!xs) return {};

    auto left = filter(cdr(xs), [&](const T& val){ return cmp(val, car(xs)); });
    auto right = filter(cdr(xs), [&](const T& val){ return !cmp(val, car(xs)); });

    return merge(sorted(left, cmp), 
                 cons(car(xs), sorted(right, cmp)));
}

StackExchange Code Review Q#106180, answer score: 6