(Optional) C++ - Lambda Expressions

Introduction

Why Use Lambdas?

Lambdas allow us to write simple and anonymous functions in place. This allows us to write smaller functions while keeping code local and organized. In addition, lambdas can capture their surrounding variables, which is often convenient when writing helper functions.

In addition, the C++ standard library has good support for lambdas, with functions like std::sort and std::lower_bound allowing you to pass custom functions to act as a comparator of objects.

General Form

Lambdas have the following form:

[capture_list](parameters) -> trailing_return_type {
	// function body
}

The parameters, return type, and function body are all pretty straightforward. In competitive programming contexts, we typically use the following capture types:

[]: Does not capture anything in the local scope.

[&]: Captures everything in the local scope by reference.

[=]: Captures everything in the local scope by copy.

The lambda's local scope is the scope where it is defined, not the scope where it is used.

You can also specify what variables to capture, but this typically is not necessary.

For an example of a lambda, say we want to write a function returns the square of a given number. We can write the following lambda expression:

Copy
auto square = [](int x) -> long long { return (long long)x * x; };

Then, you can call the lambda like a normal function.

Copy
cout << square(10) << '\n';  // prints out 100

Recursive Lambdas

Let's say we want to write a recursive GCD function. With a lambda, the most straightfoward way to write it would be like this:

Copy
auto gcd = [](int a, int b) -> int { return b == 0 ? a : gcd(b, a % b); };

Unfortunately, this does not work, because a lambda cannot directly reference itself in its definition. However, there are workarounds to this issue.

With y_combinator

If we add the following from the link above in C++14:

Copy
namespace std {

template <class Fun> class y_combinator_result {
	Fun fun_;

  public:
	template <class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template <class... Args> decltype(auto) operator()(Args &&...args) {

Then we can have code like the following:

Copy
int main() {
	cout << y_combinator([](auto gcd, int a, int b) -> int {
		return b == 0 ? a : gcd(b, a % b);
	})(20, 30)
	     << "\n";  // outputs 10
}

With std::function

Instead of auto, use function<return_type(param)>.

Copy
int main() {
	function<int(int, int)> gcd = [&](int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	};
	cout << gcd(20, 30) << '\n';  // outputs 10
}

With auto as a parameter:

The main issue with recursive lambdas is that a lambda typically cannot access itself. To fix this, we pass the lambda into itself.

Copy
int main() {
	auto gcd = [&](int a, int b, auto &&gcd) -> int {
		return b == 0 ? a : gcd(b, a % b, gcd);
	};
	cout << gcd(20, 30, gcd) << '\n';  // outputs 10
}