Can the 'type' of a lambda expression be expressed?

Thinking of lambda expressions as 'syntactic sugar' for callable objects, can the unnamed underlying type be expressed?

An example:

struct gt {
    bool operator() (int l, int r) {
        return l > r;
    }
} ;

Now, [](int l, int r) { return l > r; } is an elegant replacement for the above code (plus the necessary creation of callable objects of gt), but is there a way to express gt (the type) itself?

A simple usage:

std::set<int, gt> s1;  // A reversed-order std::set
// Is there a way to do the same using a lambda?
std::set<int, some-magic-here-maybe([](int l, int r) { return l > r; }) > s2;

No, you cannot put it into decltype because

> A lambda-expression shall not appear in an unevaluated operand

You can do the following though

auto n = [](int l, int r) { return l > r; };
std::set<int, decltype(n)> s(n);

But that is really ugly. Note that each lambda expression creates a new unique type. If afterwards you do the following somewhere else, t has a different type than s

auto n = [](int l, int r) { return l > r; };
std::set<int, decltype(n)> t(n);

You can use std::function here, but note that this will incur a tiny bit of runtime cost because it needs an indirect call to the lambda function object call operator. It's probably negligible here, but may be significant if you want to pass function objects this way to std::sort for example.

std::set<int, function<bool(int, int)>> s([](int l, int r) { return l > r; });

As always, first code then profile :)

Direct answer to your question: No.

You'll need to use something that is assignable from any type resembling a functor that has a well defined type. One example is std::function as shown in sbi's answer. That isn't, however, the type of the lambda expression.

You could use a small class lambda_wrapper<>, to wrap a lambda at low costs. Its much more faster than std::function because there are no virtual function call and a dynamic memory alloc. Wrapper works by deducing the lambda arguments list and return type.

#include <iostream>
#include <functional>
#include <set>

template <typename T, typename ... Args>
struct lambda_wrapper : public lambda_wrapper<decltype(&T::operator())(Args...)> {};

template <typename L>
struct lambda_wrapper<L> {
private:
    L lambda;
    
public:
    lambda_wrapper(const L & obj) : lambda(obj) {}
    
    template<typename... Args>
    typename std::result_of<L(Args...)>::type operator()(Args... a) {
        return this->lambda.operator()(std::forward<Args>(a)...);
    }
    
    template<typename... Args> typename
    std::result_of<const L(Args...)>::type operator()(Args... a) const {
        return this->lambda.operator()(std::forward<Args>(a)...);
    }
};
template <typename T>
auto make_lambda_wrapper(T&&t) {
    return lambda_wrapper<T>(std::forward<T>(t));
}
int main(int argc, char ** argv) 
{
    auto func = make_lambda_wrapper([](int y, int x) -> bool { return x>y; });
    std::set<int, decltype(func)> ss(func);
    std::cout << func(2, 4) << std::endl;
}

In Microsoft Visual Studio at least (I haven't tried this with other compilers), and if you don't capture anything, the type seems to be a regular function pointer:

std::string (*myFunctionPointer)(int x) = [] (int x) {
  char buffer[10];
  return std::string("Test ") + itoa(x, buffer, 10);
};
std::string testOutput = myFunctionPointer(123);