Functional-style list in C++

Question

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

1. I need to instantiate the list with incomplete types.
2. 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 <cstdlib>
#include <iostream>
#include <memory>

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

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

template<typename T>
std::unique_ptr<List<T>> list()
{
    return std::unique_ptr<List<T>>();
}

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

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

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

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

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

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::unique_ptr<List<T>> &l)
{
    if (l == list<T>())
    {
        return os;
    }
    else
    {
        return os << l->head << ' ' << l->tail;
    }
}

std::unique_ptr<List<int>> randomList(int n)
{
    if (n == 0)
    {
        return list<int>();
    }
    else
    {
        return add(std::rand() % 100, randomList(n - 1));
    }
}

int main()
{
    auto r = randomList(100);
    std::cout << r << '\n' << sort(r) << '\n';
}

Answer 1

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<List<T>>

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

template <typename T>
using FList = std::unique_ptr<List<T>>;

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<typename T>
FList<T> cons(const T& t, FList<T>&& xs)
{
    return {new List<T>{t, std::move(xs)}};
}

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

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

For that, let's loosen the restrictions:

template <typename T,
          typename U,
          typename = std::enable_if_t<std::is_constructible<T, U&&>::value>
          >
FList<T> cons(U&& u, FList<T>&& xs)
{
    return {new List<T>{std::forward<U>(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<typename T>
FList<T> list()
{
    return {}; // shorter
}

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

That will let you write:

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

Checking for empty list

In your functions, you tend to start with:

if (l == list<T>())

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

template<typename T>
FList<T> copy(const FList<T>& 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 <typename T>
T const& car(FList<T> const& xs) { // or T& if you want mutability
    return xs->head;
}

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

So that this becomes:

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

filter()

Could avoid some code duplication here:

template<typename T, typename Filter>
FList<T> filter(const FList<T>& 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 < l->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<typename T>
FList<T> sorted(const FList<T>& 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 <typename T, typename Comp = std::less<T>>
FList<T> sorted(const FList<T>& 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)));
}