## Linq to C++ (or something much better)

A really long time ago (26th Jan 2009 to be exact), I got excited about lambdas in C++0x, and the idea of bringing a Linq-like lazily-evaluated sequence filtering system to C++. I wrote a blog post about this idea partly as a pedagogical exercise in explaining the parallels/divergences in how an iteratable sequence is represented in C++ and C#.

Whenever I’m asked if this would make sense as a real library, I’ve replied that in the real world it would make much more sense to build on the stuff in Boost, especially the range library.

And guess what? At that very moment someone was already working on it (only with a far more elegant, extensible interface), and the following month a set of extensions to range were put up for review, and were accepted… then a long time passed (they’re very careful) until summer of 2010, when finally the new features were released in Boost 1.43.

I only discovered this just now. People still seem to be finding that old blog post, so it only seems proper to get up-to-date. My first stab looked like this:

#include <boost/range/algorithm/for_each.hpp> #include <boost/range/adaptor/filtered.hpp> #include <boost/range/adaptor/transformed.hpp> #include <boost/lexical_cast.hpp> #include <vector> #include <iostream> #include <string> int main() { using namespace boost::adaptors; std::vector<int> numbers; numbers.push_back(0); numbers.push_back(-1); numbers.push_back(4); numbers.push_back(-3); numbers.push_back(5); numbers.push_back(8); numbers.push_back(-2); auto quoted_positives = numbers | filtered([] (int n) { return n >= 0; }) | transformed([] (int x) { return "\"" + boost::lexical_cast<std::string>(x) + "\""; }); boost::for_each(quoted_positives, [] (std::string n) { std::cout << n << std::endl; }); return 0; }

As you can see, the key is the use of `operator|`

to make a piping syntax, so that we can naturally read from left to right (you may have seen the same approach used in F#). So I start with a vector of plain integers called `numbers`

, I then pipe that through the `filtered`

adaptor so as to get just the positives (corresponding to `Where`

in Linq), and finally through the `transformed`

adaptor to turn each positive into a quoted string (corresponding to `map`

in most functional frameworks and to `Select`

in Linq).

**Except… it doesn’t work.**

The problem is that `boost`

is not yet entirely C++11 lambda-friendly. It’s unfortunate that the boost documentation (and other online information) is peppered with the word lambda signifying something else, so I may just be missing something. But the gist of the problem appears to be that `transformed`

wants a functor with a member type called `result_type`

. So you are supposed to write something like this:

struct quote { typedef std::string result_type; std::string operator()(int x) const { return "\"" + boost::lexical_cast<std::string>(x) + "\""; } };

C++11 lambdas don’t have that `result_type`

inside them, so they don’t directly fit. It goes without saying that we don’t like this, because the whole point of lambdas is to avoid writing a separate class somewhere else.

It is surely possible to extend boost’s `function_traits`

so that they can reflect on lambdas. In the past they have not been written to work on general functors because a functor can have multiple overloads of `operator()`

, so you are required to manually pick one of those members before you ask questions. But this position is no longer sensible (if indeed it ever was). The majority of functors will now be lambdas, with a single overload of `operator()`

, and it is (as we can see from this example) perfectly reasonable to want to know the return type of that single overload. A lambda is an alternative to a plain function, and whatever is useful for a function will be useful for a lambda.

But in the meantime, it is interesting to see how many hoops we have to jump through to make the above sample code work as expected.

If you read my last update on this sordid subject you’ll know that I don’t want to have to state the type of something that can be inferred, so I’m not going to be satisfied by a wrapper template that just adds a *manually specified* `result_type`

member to my lambda. Ugh! It *must* be inferred automatically.

Fortunately this is just a matter of using a few simple steps in metaprogramming. Firstly, a template designed to match a member function:

template <class T> struct mem_fun_traits { };

Of course in this general form it will match anything. But we’ll only bother to specialise it for one case: a pointer to a const member function that accepts one argument:

template <class R, class C, class A> struct mem_fun_traits<R (C::*)(A) const> { typedef R result_type; typedef A argument_type; };

So if you pass `mem_fun_traits`

the type of a pointer to the `operator()`

within a lambda, you know what it accepts and returns. But how do you get that type argument? With `decltype`

that’s easy-peasy:

template<typename T> struct functor_member { typedef decltype(&T::operator()) type; };

Armed with these tools, we can write a traits class for our simple one-argument, single-overload functors (and hence, by an extraordinary coincidence, also for C++11 lambdas):

template <class F> struct functor_traits { typedef typename functor_member<F>::type member_t; typedef mem_fun_traits<member_t> traits; typedef typename traits::result_type result_type; typedef typename traits::argument_type argument_type; };

This is the thing that should be integrated into boost’s `function_traits`

, to make lambdas work as true replacements for functions. I’m sure someone’s working on it.

In the event that this doesn’t happen, we can shoehorn it together anyway by making a function template that adds type metadata to any single-argument functor:

template <class F> class functor_with_traits_t { F f; public: functor_with_traits_t(F f_) : f(f_) {} typedef typename functor_traits<F>::result_type result_type; typedef typename functor_traits<F>::argument_type argument_type; result_type operator()(argument_type a) const { return f(a); } }; template <class F> inline functor_with_traits_t<F> functor_with_traits(F f) { return functor_with_traits_t<F>(f); }

So if you have a plain old lambda like this:

auto l = [] (int x) { return "\"" + boost::lexical_cast<std::string>(x) + "\""; };

You can “fix” it to have type metadata like so:

auto l2 = functor_with_traits(l);

This makes it compatible with boost’s `transformed`

! Although manually putting in that wrapper each time is pretty tedious. We can work around that by defining our own adapter (let’s call it `selected`

in slavish imitation of Linq) that just plugs together `functor_with_traits`

and `transformed`

. Sounds simple, though as always the difficulty is in figuring out the types:

template <class F> inline um... selected(F f) { return boost::adaptors::transformed(functor_with_traits(f)); }

The `um...`

is “whatever type we’re returning”. Wouldn’t it be nice if we could put `auto`

there? Well, we almost can: `decltype`

to the rescue as usual:

decltype( boost::adaptors::transformed( functor_with_traits(make_ref<F>()) ) )

That is: give me the type that would be returned if I called `transformed`

, passing it the result of a call to `functor_with_traits`

, passing it an `F`

. Of course we can’t assume that `F`

can be default constructed, hence the use of that funny `make_ref`

function that always comes in handy with `decltype`

.

So our completed adaptor is:

template <class F> decltype( boost::adaptors::transformed( functor_with_traits(make_ref<F>()) ) ) selected(F f) { return boost::adaptors::transformed(functor_with_traits(f)); }

We can use `selected`

in place of `transformed`

and everything is hunky dory. Full example:

#include <boost/range/algorithm/for_each.hpp> #include <boost/range/adaptor/filtered.hpp> #include <boost/range/adaptor/transformed.hpp> #include <boost/lexical_cast.hpp> #include <vector> #include <iostream> #include <string> template <class T> T *make_ptr() { return (T *)0; } template <class T> const T &make_ref() { return *(make_ptr<T>()); } template <class T> struct mem_fun_traits { }; template <class R, class C, class A> struct mem_fun_traits<R (C::*)(A) const> { typedef R result_type; typedef A argument_type; }; template<typename T> struct functor_member { typedef decltype(&T::operator()) type; }; template <class F> struct functor_traits { typedef typename functor_member<F>::type member_t; typedef mem_fun_traits<member_t> traits; typedef typename traits::result_type result_type; typedef typename traits::argument_type argument_type; }; template <class F> class functor_with_traits_t { F f; public: functor_with_traits_t(F f_) : f(f_) {} typedef typename functor_traits<F>::result_type result_type; typedef typename functor_traits<F>::argument_type argument_type; result_type operator()(argument_type a) const { return f(a); } }; template <class F> functor_with_traits_t<F> functor_with_traits(F f) { return functor_with_traits_t<F>(f); } template <class F> decltype(boost::adaptors::transformed(functor_with_traits(make_ref<F>()))) selected(F f) { return boost::adaptors::transformed(functor_with_traits(f)); } int main() { using namespace boost::adaptors; std::vector<int> numbers; numbers.push_back(0); numbers.push_back(-1); numbers.push_back(4); numbers.push_back(-3); numbers.push_back(5); numbers.push_back(8); numbers.push_back(-2); auto quoted_positives = numbers | filtered([] (int n) { return n >= 0; }) | selected([] (int x) { return "\"" + boost::lexical_cast<std::string>(x) + "\""; }); boost::for_each(quoted_positives, [] (std::string n) { std::cout << n << std::endl; }); return 0; }

(Tested on MSVC++ 16.00.40219.01 and GNU G++ 4.5.3.)