irresistibly bad - don't say i didn't warn you

After reading yet another discussion about the superiority of some language based on its builtin list comprehensions, I figured I should try adding the same to C++. I searched the web, but other than some references to using Boost, wasn't able to find anything concrete.

First, let's start with something basic. We want builtin syntax for working with the head and tail elements of a list. And we want to access the rest of the list. Like so:

    list<int> startlist, rest;
    int head, tail;

    (head, rest) = startlist;
    (rest, tail) = rest;

    assert(head == startlist.front() &&
        tail == startlist.back());

Given a a single element and target list, as in (head, rest), we need something that can interact with a list via assignment. We'll create a new class whose constructor takes a reference to an item and a list.

template<typename T>
class list_slice_head {
private:
    T &head;
    list<T> &tail;
public:
    list_slice_head(T &h, list<T> &t) : head(h), tail(t) { }

    list_slice_head<T> &operator=(const list<T> &o) {
        tail = o;
        head = tail.front();
        tail.pop_front();
        return *this;
    }
};

Pretty straightforward. When assigned a list, this class pulls it apart into a head element and tail list. In order to construct instances of this class on the fly and support our desired syntax, we can use the comma operator.

template<typename T>
list_slice_head<T>
operator,(T &h, list<T> &t) {
    return list_slice_head<T>(h, t);
}

So now, we can just type (head, rest) = list and have the compiler create a list_slice_head class for us. We also want to support tail slicing; the code for that is very similar.

template<typename T>
class list_slice_tail {
private:
    list<T> &head;
    T &tail;
public:
    list_slice_tail(list<T> &h, T &t) : head(h), tail(t) { }

    list_slice_tail<T> &operator=(const list<T> &o) {
        head = o;
        tail = head.back();
        head.pop_back();
        return *this;
    }
};
template<typename T>
list_slice_tail<T>
operator,(list<T> &h, T &t) {
    return list_slice_tail<T>(h, t);
}

This isn't quite list comprehension, but we're making some progress, and we've got some sweet syntactic sugar.

List comprehension doesn't quite fit into C++ using the set builder notation, but we can come up with something close by rearranging the order of some things. Basically, our goal is to be able to filter a list without explicit filter calls. Same for map. Let's say we want the numbers less than 10, given a list of all numbers. (ok, not quite all. We don't have infinite lists here.)

    little = numbers < 10;

Pretty clear what our intention is. Here's the code to implement this, using bind2nd to call less<T> with our fixed argument.

template<typename T>
list<T>
operator<(const list<T> &l, const T &x) {
    return l | bind2nd(less<T>(), x);
}

Some of the code anyway. We still need operator |. This is the more complicated half. I've really implemented more of a map function operator, but it can do double duty for filtering as well. Before jumping to the code, we realize we would like to both modify a value (map) and select it (filter). The best way to do both is with a function that takes a reference and returns a bool. But we don't want to alter the initial list.

template<typename T, typename F>
list<T>
operator|(const list<T> &l, F fn) {
    list<T> r;
    foreach (i, l) {
        T x(*i);
        if (fn(x))
            r.push_back(x);
    }
    return r;
}

We iterate over the input, collecting values (possibly modified), and then return a new list. foreach is a macro, defined in the full code below, or you can simply write out the relevant code. Note that the function doesn't have to take a reference, pass by value can also work since fn is of independent template type F.

Here's some sample code to demonstrate some simple things we can do. Of course, the code here only works with STL lists. If you roll your own list like structure, you'll have to redo it, but that's a good thing. You aren't confined to one container type.

You can also download the source.

bool even(int x) { return x % 2 == 0; }
bool x2(int &x) { x *= 2; return true; }

int
main()
{
    list<int> l;
    int x, y;
    list<int> t;

    for (int i = 0; i < 10; i++)
        l.push_back(i);

    (x, t) = l | x2;
    (t, y) = t;

    cout << x << " " << t.front() << "-" << t.back() << " " << y << endl;
    cout << l.front() << "-" << l.back() << endl;

    t = l < 9;

    foreach (i, t)
        cout << *i << " ";
    cout << endl;

    t = t < 7 | even | x2;
    foreach (i, t)
        cout << *i << " ";
    cout << endl;
}

Bonus round. We add one more comparison filter operator and a + operator for concatenation (elided, see source), and now we're ready to implement quicksort.

template<typename T>
list<T>
qsortlist(const list<T> &l)
{
    if (l.empty())
        return l;
    T pivot;
    list<T> tail;

    (pivot, tail) = l;
    return qsortlist(tail < pivot) + pivot + qsortlist(tail >= pivot);
}

Not the most efficient implementation, but now it looks remarkably like the version on the Haskell wiki, and that's what counts, right? We don't even have to mess around with the explicit call to filter.

And finally, a little sample code and the output I get. Combine with the above.

    for (int i = 0; i < 12; i++)
        l.push_back(rand() % 100);
    foreach(i, l)
        cout << *i << " ";
    cout << endl;
    l = qsortlist(l);
    foreach(i, l)
        cout << *i << " ";
    cout << endl;

90 75 84 81 74 99 52 85 86 47 8 21

8 21 47 52 74 75 81 84 85 86 90 99

eof