Composing Algorithms with Lambdas — Evil Genius Society

Lesson 5 of 5

Lambdas are most useful not one at a time but combined: a lambda that returns a lambda, a predicate built from two others, a comparator parameterised by a key.

This lesson is the practical payoff of Modules 13 and 14 together.

Factories: a lambda that returns a lambda

#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

struct Sale {
    std::string region;
    std::string product;
    int units;
    double price;
};

int main() {
    std::vector<Sale> sales = {
        {"north", "widget", 10, 2.50},
        {"south", "gadget",  5, 10.00},
        {"north", "gadget",  8, 10.00},
        {"east",  "widget", 20, 2.50},
        {"south", "widget",  3, 2.50},
        {"north", "widget", 15, 2.50},
    };

    // A predicate factory: build a filter from a value.
    auto in_region = [](const std::string& r) {
        return [r](const Sale& s) { return s.region == r; };
    };

    // Compose two predicates into one.
    auto both = [](auto p, auto q) {
        return [p, q](const auto& x) { return p(x) && q(x); };
    };

    auto is_widget = [](const Sale& s) { return s.product == "widget"; };

    std::cout << "north sales:        "
              << std::count_if(sales.begin(), sales.end(), in_region("north")) << "\n";
    std::cout << "north widget sales: "
              << std::count_if(sales.begin(), sales.end(), both(in_region("north"), is_widget))
              << "\n";

    // A projection factory used as an accumulate step.
    auto revenue_of = [](const Sale& s) { return s.units * s.price; };
    double total = std::accumulate(sales.begin(), sales.end(), 0.0,
                                   [&](double acc, const Sale& s) { return acc + revenue_of(s); });
    std::cout << "total revenue: " << total << "\n";

    double north = std::accumulate(sales.begin(), sales.end(), 0.0,
        [&](double acc, const Sale& s) {
            return in_region("north")(s) ? acc + revenue_of(s) : acc;
        });
    std::cout << "north revenue: " << north << "\n";

    // Sort by a chosen key, descending, using a factory.
    auto by_desc = [](auto key) {
        return [key](const auto& a, const auto& b) { return key(a) > key(b); };
    };
    std::sort(sales.begin(), sales.end(), by_desc(revenue_of));
    std::cout << "top seller: " << sales[0].region << "/" << sales[0].product
              << " = " << revenue_of(sales[0]) << "\n";
    return 0;
}

north sales:        3
north widget sales: 2
total revenue: 250
north revenue: 142.5
top seller: north/gadget = 80

Four patterns there, and all four are worth stealing.

A predicate factory. in_region("north") returns a lambda that tests one region. One definition, any number of regions — this is how you avoid writing is_north, is_south, is_east.

A combinator. both(p, q) takes two predicates and returns their conjunction. It is generic (auto parameters), so it composes anything. Writing either, negate, and all_of_them is the same three lines.

A projection. revenue_of names a computed field once, and it is then usable as an accumulate step, a sort key, and a filter input. Naming it separately is what lets the later by_desc line be one word long.

A comparator factory. by_desc(revenue_of) builds a descending comparator from any key function. Compare that with writing the comparator inline every time.

Note the capture in in_region: [r] copies the string into the returned closure. Capturing [&r] would dangle the moment the factory returned — lesson 14.2's bug, and factories are exactly where it happens.

Three ways to express a pipeline

#include <algorithm>
#include <iostream>
#include <ranges>
#include <string>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Three ways to express the same pipeline.

    // 1. Nested calls: reads inside-out, needs intermediate storage.
    std::vector<int> step1;
    std::copy_if(v.begin(), v.end(), std::back_inserter(step1),
                 [](int x) { return x % 2 == 0; });
    std::vector<int> step2(step1.size());
    std::transform(step1.begin(), step1.end(), step2.begin(), [](int x) { return x * x; });
    int sum1 = 0;
    for (int x : step2) sum1 += x;

    // 2. One accumulate with the logic fused into the lambda.
    int sum2 = 0;
    std::for_each(v.begin(), v.end(), [&](int x) { if (x % 2 == 0) sum2 += x * x; });

    // 3. A range pipeline: reads left to right, no intermediates.
    auto pipeline = v
        | std::views::filter([](int x) { return x % 2 == 0; })
        | std::views::transform([](int x) { return x * x; });
    int sum3 = 0;
    for (int x : pipeline) sum3 += x;

    std::cout << "nested algorithms: " << sum1 << " (2 intermediate vectors)\n";
    std::cout << "fused for_each:    " << sum2 << " (0 intermediates, logic tangled)\n";
    std::cout << "range pipeline:    " << sum3 << " (0 intermediates, steps separate)\n";
    return 0;
}

nested algorithms: 220 (2 intermediate vectors)
fused for_each:    220 (0 intermediates, logic tangled)
range pipeline:    220 (0 intermediates, steps separate)

Same answer, three different trade-offs.

Nested algorithms name each step, which reads well — but each one materialises a whole vector, and the steps run in the opposite order from how they are written.

A fused for_each allocates nothing and makes one pass, and it is what you write in a hot loop. The cost is that filtering, transforming, and accumulating are tangled in one lambda body: change the order of operations and you rewrite it.

A range pipeline (lesson 13.9) has the fused version's efficiency and the nested version's readability. Since C++20 this is the default choice for anything more than one step.

The honest exception is a single simple operation. std::count_if(v.begin(), v.end(), pred) needs no pipeline, and a plain range-for still beats all three for clarity when there is only one thing to do.

The composition worth knowing

Three small combinators cover most needs:

// auto negate = [](auto p) { return [p](const auto& x) { return !p(x); }; };
// auto both   = [](auto p, auto q) { return [p, q](const auto& x) { return p(x) && q(x); }; };
// auto either = [](auto p, auto q) { return [p, q](const auto& x) { return p(x) || q(x); }; };
//
// std::count_if(v.begin(), v.end(), both(is_active, negate(is_expired)));

Note they capture p and q by value. A combinator returns a closure that outlives the call that made it, so by-reference capture is the dangling bug again.

std::not_fn in <functional> is the standard's version of negate:

// std::count_if(v.begin(), v.end(), std::not_fn(is_expired));

Where composition stops paying

Three honest limits.

Depth. Two or three composed lambdas read well. Five nested factories do not, and no reader will thank you. When it gets deep, name the intermediate steps as ordinary functions.

Debugging. Stepping into both(in_region("north"), is_widget) in GDB (lesson 11.2) lands you in a chain of operator() calls with no source names. A named function has a name in the backtrace.

Compile time. Every distinct composition is a distinct closure type, so a heavily composed codebase compiles slowly — the same cost ranges have (lesson 13.9).

The rule of thumb: compose when it removes repetition, stop when it removes clarity.

Try it

Given a list of employees, build a query system from composable lambdas: filter by department, filter by salary range, sort by any field, and take the top N. Compose them to answer "the three highest-paid engineers under 40", and count how many records each stage touches.

Checkpoint