Lambda: Overloading and Recursive

Lambda expression is very handy, but there’re some restrictions – it can’t be overloaded and it can’t call itself. Well, only at language level. Remember we’re talking about c++? It’s fairly easy to overload lambdas and make it recursive-enabled in a library fashion.

Recursive Lambda in C++11

Of course, you can already use lambda recursively in c++11, with the help of std::function.

std::function<int(int)> factorial = [&factorial](int i)
{
    return i == 0? 1 : i * factorial(i - 1);
};

But then you suffer the runtime penalty of std::function.

Recursive Lambda in C++1y

With the introduction of generic lambda in c++1y, we can avoid the overhead:

auto factorial = [](auto self, int i)->int
{
    return i == 0? 1 : i * self(self, i - 1);
};

Note that how the recursive call is written: self(self, i - 1). In the user code, you have to call it in the same way:

factorial(factorial, n);

It’s a bit ugly because the functor itself has to appear twice in one call. To make it more appealing, with the same signature as a normal one, we can make a wrapper:

template<class F>
struct recursive
{
    template<class... Ts>
    decltype(auto) operator()(Ts&&... ts) const
    {
        return f(*this, std::forward<Ts>(ts)...);
    }
    
    F f;
};

auto const make_recursive = [](auto f)
{
    return recursive<decltype(f)>{std::move(f)};
};

Now we can use make_recursive to define the lambda:

auto factorial = make_recursive([](auto& self, int i)->int
{
    return i == 0? 1 : i * self(i - 1);
});

Voila! In the lambda body, we can spell self(i - 1) instead of self(self, i - 1) as in the above example. In the user code, we can call factorial(n) as usual. Perfect, isn’t it?

Let’s move on to the next topic – overloading.

Overload Lambdas

C++ allows us to overload functions, but what a lambda expression gives us is a closure, that is, a function object. You can’t overload the variables:

auto f = [](){...};
auto f = [](int){...};

Yet, we can make a wrapper. The simplest way that comes to mind is:

template<class... Fs>
struct overload : Fs...
{
    overload(Fs&&... fs)
      : Fs(std::move(fs))...
    {}
};

auto const make_overload = [](auto... fs)
{
    return overload<decltype(fs)...>{std::move(fs)...};
};

Make an overloaded functor and call it:

auto f = make_overload
(
    []{ std::cout << "1\n"; }
  , [](int){ std::cout << "2\n"; }
);
 
f();
f(2);

It works fine with clang 3.5, but g++ 4.9.1 doesn’t buy it. Actually, g++ seems to be correct here, see this stackoverflow question.

So, we have to use operator() from the bases explicitly, but it’s illegal to write:

using Fs::operator()...;

Instead, we have to do:

template<class F, class... Fs>
struct overload : F, overload<Fs...>
{
    using F::operator();
    using overload<Fs...>::operator();

    overload(F&& f, Fs&&... fs)
      : F(std::move(f))
      , overload<Fs...>(std::move(fs)...)
    {}
};

template<class F>
struct overload<F> : F
{
    using F::operator();

    overload(F&& f)
      : F(std::move(f))
    {}
};

That’s it.

So far I’ve shown you how to make a recursive lambda and how to overload them, what next? Well, let’s combine the two :)

Recursive and Overloaded Lambda

Recursive template function calls are often not really recursive, actually different functions are called, they just happened to have the same name, at least to the programmer. And usually, we need to deal with the special cases by overloading the function. Combing both tricks makes generic lambda more powerful.

Let’s write a helper function that ties them up:

auto const make_recursive_overload = [](auto&&... fs)
{
    return make_recursive(make_overload(static_cast<decltype(fs)>(fs)...));
};

Now we can play with it. For instance, to implement a recursive for_each for variadic param-pack:

auto const for_each = make_recursive_overload
(
    [](auto& self, auto&& f, auto&& t, auto&&... ts)
    {
        f(static_cast<decltype(t)>(t));
        self(f, static_cast<decltype(ts)>(ts)...);
    }
  , [](auto& self, auto&& f) {}
);

The first overload does the recursive call, and the second one is the termination condition. This is how it is used:

for_each([](auto&& val)
{
    std::cout << val << ',';
}, 1, 2, 3, 4);

If you remember my last post about param-pack, you could have more fun:

auto const each = [](auto&& f)
{
    return [&](auto&&... ts)
    {
        for_each(f, static_cast<decltype(ts)>(ts)...);
    };
};

auto p = pack(1, 2, 3, 4);
p(each([](auto&& val)
{
    std::cout << val << ',';
}));