2 Getting started with functional programming
This chapter demystifies functional programming in C++ by showing that its power comes from simple ideas with big consequences. Central is the notion that functions are first-class values and that higher-order functions—those that take or return functions—enable concise, declarative solutions. Common patterns like filtering and transforming (map/transform) are presented as reusable abstractions that let you express intent at a higher level, improving readability, correctness, and opportunities for reuse and optimization.
Through the Standard Template Library, the chapter demonstrates practical higher-order tools: accumulate and reduce for aggregation (e.g., averages), folding as a generalization that can compute sums, products, counts, or even build new collections; find_if for tasks like string trimming; and (stable_)partition for reorganizing elements by a predicate. It also highlights real-world caveats: while STL algorithms encourage a functional style, their iterator-and-output-iterator interfaces can hinder composition, often forcing intermediate containers or extra copying. The text notes when handwritten loops remain simpler or more efficient and points to execution policies for parallel variants where appropriate.
Finally, it shows how to write your own higher-order functions by templating over callable types, and compares several implementation strategies: direct loops for clarity and efficiency, recursion for conceptual purity (with warnings about stack usage), tail recursion and the possibility of tail-call optimization, and folding as a clean, reusable way to express iterative accumulation. Performance nuances are addressed (e.g., accumulator copying with accumulate and the value of move-aware variants), and the chapter foreshadows ranges as a more composable approach that preserves efficiency. The overall message is that higher-order functions and folds let you build small, composable pieces that scale to robust, efficient C++ solutions.
Filtering a collection of people based on the is_female predicate. It should return a new collection containing only females.
You have a collection of people. The transform algorithm should call the transformation function for each of them and collect the results. In this case, you’re passing it a function that returns the name of a person. The transform algorithm collects the name of every person into a new collection.
If you have one function that filters a collection of people to contain only females, and a second function that extracts the name of every person in a specified collection, you can compose the two functions into a function that gets the names of all females in a group of people.
Calculating the average score for a movie from a list of individual user ratings. You first sum all the individual ratings and then divide the sum by the number of users.
Folding calculates the sum of all movie scores in a collection by adding the first score to the initial value used for summation (zero), adding the second score to the previously calculated sum, and so on.
In general, folding takes the first element in a collection and applies the specified binary function f to it and the initial value for folding (r0); then it takes the second element from the collection and calls f on it and the previously calculated result. This is repeated until you get to the last item in the collection.
You can count the number of newline characters in a given string by folding a string with a simple function that increments the count each time it encounters a newline.
Folding on a left-associative operator is the same as writing all the items in the collection one after another, and putting the operator between them.
The main difference between left and right folding is that a left fold starts from the first element and moves toward the end of the collection, whereas a right fold starts at the end and moves toward the beginning.
Partitioning a group of people based on a predicate that checks whether a person is female. As the result, all females are moved to the start of the collection.
Moving selected items to a specified position with the help of std::stable_partition. Selected items that are above the destination location should move down, and selected items that come after the destination location should move up.
Getting the names of all females in a group
Summary
- By passing specific predicate functions to algorithms such as
transformandfilter, you change their behavior and make a general algorithm work for a specific problem you have. - The
std::accumulatealgorithm lives in the<numeric>header, but it’s applicable to many more areas than just performing simple calculations. std::accumulateimplements a concept called folding that isn’t limited to addition and multiplication and can be used to implement many standard algorithms.- If you don’t want to change the order of selected elements in a list while dragging them, it’s better to use the
std::stable_partitionalgorithm instead ofstd::partition. Similarly, in a UI,std::stable_sortis often preferable tostd::sort. - Although STL algorithms are meant to be composed, they aren’t meant to be composed the same way as algorithms in other functional programming languages. This will be easily remedied when you start using ranges.
- The fact that most standard algorithms are implemented as loops isn’t a reason to use handwritten loops instead. In the same way,
while,if, and others are implemented usinggotos (jumps)—but you don’t usegotostatements, because you know better.
FAQ
What are higher-order functions, and why do they matter in C++?
Higher-order functions are functions that take other functions as arguments or return functions as results. They matter because they let you express intent at a higher level (what to do, not how), enabling reusable patterns like filtering, transforming, folding, and composing behaviors across collections.How do filtering and transformation (map) differ conceptually?
- Filter keeps items that satisfy a predicate and discards the rest; input and output item types are the same.- Transform (map) applies a function to each item and collects the results; output type can differ from input type.
Which STL algorithms embody higher-order functions?
Core examples include std::accumulate (fold), std::reduce (parallel-friendly fold), std::transform (map), std::copy_if (filter-like copy), std::find_if (search by predicate), std::partition and std::stable_partition (reorder by predicate). Each accepts callable arguments to customize behavior.What is folding (reduction), and how does std::accumulate implement it?
Folding iteratively combines a running result with each element using a binary function and a starting value. std::accumulate performs a left fold: it starts with the initial value, combines it with the first element, then with the next, and so on, returning the final accumulated result.When should I use std::reduce instead of std::accumulate?
Use std::reduce when you want potential parallel execution (with execution policies) and you don’t rely on strict left-to-right accumulation. std::accumulate guarantees sequential left-to-right order, which can be important for non-associative operations but prevents parallelization.How can I customize accumulation (sum, product, or something else)?
Pass a custom binary operation to the algorithm. For example, you can use multiplication instead of addition, or supply any callable that combines the running result and the current item. Choose an appropriate initial value (e.g., 0 for sums, 1 for products).What is the erase–remove idiom, and why is it needed?
std::remove_if reorders a range so that “kept” elements come first and returns an iterator to the new logical end; it doesn’t actually shrink the container. You must call container.erase(returned_iterator, container.end()) to physically remove the trailing “removed” elements.How do I trim leading and trailing whitespace using STL algorithms?
Use std::find_if to locate the first non-space from the front and erase the prefix; use reverse iterators with std::find_if to locate the last non-space from the back and erase the suffix. Passing the string by value is convenient when you return a modified copy.Why are STL algorithms sometimes hard to compose directly?
They typically take input as iterator pairs and require an output iterator, returning an iterator rather than a new container. This design enables flexibility (operate on subranges, choose output container) but hinders “function composition” style. Workarounds include intermediate containers, custom views/iterators, or adopting ranges (C++20/Range-v3) for fluent composition.How should I write my own higher-order function, and what about loops, recursion, and folds?
- Accept callables via templates (auto or typename F) to support functions, lambdas, and function objects without overhead.- Prefer clear loops when STL composition would force extra allocations or copies.
- Use recursion cautiously; tail recursion may be optimized into loops (TCO), but it’s not guaranteed.
- Favor folds (accumulate/reduce) to express tail-recursive patterns succinctly; watch for performance pitfalls like unnecessary copies and use moves where appropriate.
Functional Programming in C++ ebook for free
