Lambda Expressions in Algorithms
A lambda expression is a notation that generates a function object, exactly like Less_than<int>{x}.
Try it: Functions as Values: Lambda
That a lambda (like def) evaluates to a function object that a name can refer to and that can be passed to other functions — apply(f, x), twice(f, x), map(f, xs), sorted(xs, key=f) — and that each call is traced by binding the argument, substituting it into the single expression and evaluating in operator order.
How it works
- lambda x: expression evaluates to a function object (named <lambda>); nothing inside it is computed yet. f = ... gives it a name, exactly as def f(x): return expression would.
- Writing f without parentheses passes the function object itself; inside apply or twice the parameter func refers to the same object.
- A call binds the argument to the parameter x, substitutes it into the expression, and evaluates by operator precedence (* and % before + and -, parentheses first).
- The value of the expression is the call's return value; there is no other body.
- map(f, xs) calls f once per item and keeps the results in order; sorted(xs, key=f) calls f once per item to get keys, orders by the keys (ties keep their order) and returns the items.
Default run (9 steps): The program is ready: a lambda written inline, then f(x). … print shows 7.
Simplified: Four one-parameter lambdas with editable integer constants, small int arguments (at most 6 items). Each substituted expression the lab shows was evaluated by CPython 3.12 and has the same value as the real call; printed results and ZeroDivisionError messages match CPython.
Loading the simulation…
A Prediction Before Reading the Mechanism
This article works from one real function, f. It takes a vector of ints, a list of strings, an int x, and a string s, and it prints two counts: how many values are less than x, and how many strings are less than s. Both counts are computed by passing a lambda expression to a counting routine called count. Each call to count receives a lambda as its second argument. The first lambda uses the local name x, and the second uses the local name s. Keep these two lambdas in mind, because the rest of the article asks you to reason about exactly what each one can see.
What do you think happens?
Suppose vec holds the values 3, 8, and 12, and x is 10. Without running anything, how many values does the first lambda count, and why?
Reveal answer
Two values are counted: 3 and 8. Each is less than 10, and 12 is not.
The first lambda's job is to decide whether a value qualifies by comparing it with x. Because x is 10 in f, the comparison is against 10. Write down your own answer and reason before reading on, because the rest of the article explains how the lambda reaches that x and decides which values qualify.
What a Lambda Expression Generates
A lambda expression is a notation that generates a function object. A function object is a value of a type that can be called like a function and that holds data. Writing a lambda is a compact way to produce such an object without naming a separate type or writing out a class.
The source uses Less_than<int>{x} as the reference point. Less_than<int>{x} is an ordinary function object: it is a value of a type that can be called like a function and that holds x. A lambda expression is a shorter way of writing down an object of this kind. Instead of naming the type and constructing it with x, you write the behavior in place, at the point where it is needed, and the notation produces the function object for you. The key idea is that the lambda's behavior and the value it depends on travel together in one object that the algorithm can call.
Because the lambda is written in place, it lives inside the function that uses it. That is why it can refer to names that exist in that function, such as x in f. The source describes this as capturing the local names used within the lambda expression. The rest of this article explains how that capture works.
Reading the Three Parts of a Lambda
The lambda in the first line of f has three visible parts, read left to right. The first is the capture list, written in square brackets. The second is the parameter list, written in parentheses. The third is the body, written in braces. Each part has a separate responsibility, and the diagram labels the piece that controls each one.
Notice that the parameter a is declared inside the lambda, while x is not declared there at all. The capture list is what tells the reader that x comes from the enclosing function. The parameter list describes what the generated object accepts when it is called, and the body describes what it computes. Keeping these roles separate makes a lambda much easier to read: the brackets answer where outside names come from, the parentheses answer what arrives on each call, and the braces answer what happens.
How the Capture List Controls Access
The capture list is the part that specifies how local names used inside the lambda are accessed. The source gives two ways to capture a single name individually and three forms that apply to every local name the lambda uses. The two groups are covered below.
Copy Versus Reference for a Local Name
The central question for a captured name is whether the lambda holds its own copy of x or a reference to the enclosing function's x. With reference capture, the lambda reaches the same x that f owns, so a change made through the lambda is visible outside it. With value capture, the lambda works with its own value for x, so a change made to that value does not reach the x in f. The diagram shows the two situations side by side for the same local name.
Worked Example: Counting Values Below x
The source does not print the full listing of f in this pack, so the lambda below is a reconstruction that matches the source's description: it takes one argument named a, compares it with x, and captures x. The example traces it with the values from the opening prediction.
- [&] captures the local name x by reference
- const int& a is the argument the counting routine passes on each call
- The body returns true when the element is less than x
Counting the values in vec
vec holds 3, 8, and 12, and x is 10. The first lambda is passed to count. How many values are counted?
- 1Identify the captured name
The capture list [&] captures x by reference, so the lambda compares against the x that f owns, which is 10.
- 2Call on the first element
count calls the lambda with a equal to 3. The test 3 < 10 is true, so this value counts.
- 3Call on the second element
count calls the lambda with a equal to 8. The test 8 < 10 is true, so this value counts.
- 4Call on the third element
count calls the lambda with a equal to 12. The test 12 < 10 is false, so this value does not count.
Two values are counted, 3 and 8. This matches the prediction made at the start of the article.
Tracing the Lambda Through the Counting Routine
The lambda is not called once for the whole vector. The counting routine calls it once per element, and each call reads the same captured x. The diagram follows the calls made while count processes vec, showing the value passed in each time and the result of the comparison.
Every call reads the same x, which is 10 throughout. Only the argument changes from call to call. The count is the number of calls that returned true. Because the value of x is fixed across the calls, the captured name does not change the result here; what matters is which x the lambda reads, and that determines the comparison each time it runs.
Mistakes Beginners Make With Captures
Common mistake Writing [ ] and expecting the lambda to see an outside local name
What it looks like[ ](const int& a) { return a < x; } with x declared in fWhy it fails[ ] captures nothing, so the lambda has no access to the local x of the enclosing function.
Do this insteadUse a capture form that includes x, such as [&x] or [&], depending on the intended access.
Common mistake Assuming [=x] lets the lambda change the enclosing x
What it looks likeA lambda with [=x] that assigns to x, expecting f's x to change
Why it fails[=x] captures x by value, so the lambda works with its own value rather than the x in f.
Do this insteadIf the change must be visible outside the lambda, capture x by reference with [&x].
Common mistake Assuming a name is captured because it appears in the body
What it looks likeA body that uses s while the capture list only names x
Why it failsThe capture list determines access. A name the capture list does not include is not made available just because the body mentions it.
Do this insteadRead the capture list and the body together and check that every outside name the body uses is covered.
Common mistake Treating the parameter list as a place to bring in outside names
When a lambda gives an unexpected result, the cause is usually a capture decision: a name captured differently than assumed, or a name assumed to be captured that the capture list did not include. The fastest way to find it is to locate the first step where your reasoning and the actual execution diverge.
Choosing a Capture List
Given a local name and how the lambda uses it, the table gives the capture form that matches. Read the use first, then pick the form. The table uses only the forms the source describes.
| Situation inside the lambda | Capture form | What the lambda holds |
|---|---|---|
| No outside local name is used | [ ] | Nothing is captured |
| One local name x, reached by reference | [&x] | A reference to the enclosing x |
| One local name x, taken by value | [=x] | A value of x |
| Several local names, all by reference | [&] | References to every local name used |
| Several local names, all by value | [=] | Values of every local name used |
Capture forms and what each one gives the lambda
Practice: Changing a Capture
The second lambda in f has the capture list [&] and the parameter const string& a, and it compares a string from lst against s. Rewrite its capture list so that it captures s by value instead of by reference, and explain what the lambda can and cannot do with s afterward. Then say whether the value of s used in the comparison could ever differ from the s in f.
Hints
- Start from the table: the choice is between [&s] and [=s] for one named local name.
- Ask what a value-captured name holds, and whether it is the same object as the s in f.
- Consider which form matches a value that is fixed when the lambda is written.
Key Takeaways
- A lambda expression is a notation that generates a function object, the same kind of thing as Less_than<int>{x}: a callable value that holds the data it needs.
- A lambda has three parts: the capture list in square brackets decides how outside local names are reached, the parameter list in parentheses receives the arguments, and the body in braces is the code that runs.
- [&x] captures x by reference, [=x] captures x by value, [&] and [=] apply those modes to all local names used, and [ ] captures nothing.
- When tracing a lambda through a counting routine, the algorithm calls it once per element, and the captured name determines which x each call compares against; when a result is unexpected, look for the first step where the capture decision diverges from your model.