Functional programming (FP) is a discipline and practice of computer science where Mathematical concepts come to the fore. There are a number of popular FP languages out there, but we can stay with C++ and explore some of the themes of FP by using a subset of familiar syntax. In this article we’ll look at a number of FP concepts, such as purity, immutability and use of higher-order functions, and how they can be concisely and usefully represented in Modern C++.
1. Purity
A function is considered pure if its operation depends only upon its formal input parameters, that is not accessing any external (global) state. Global state in FP is a little like the historical Goto statement, shunned but sometimes necessary, and so is by design abstracted away as much as possible. A C++ lambda is pure if it has an empty capture clause, for example:
void f() {
int x = 42;
auto pure = [](const auto a, const auto b){ return a + b; };
auto impure = [&](const auto a, const auto b){ return a + b + x; };
}
Therefore, when programming in C++ in a functional style, we should use pure lambdas as much as possible. Static variables in functions muddy the water slightly, and C++ classes should be used instead, for example:
#include <iostream>
double random_lcg(unsigned seed = 0) {
static unsigned int x = 1 << 19; // X(n+1) = (aX(n)+c) mod m
if (seed) {
x = seed;
return 0.0;
}
x = (1103515245 * x + 12345) % (1u << 31);
return x * 1.0 / (1u << 31);
}
class RandomLCG {
unsigned int x;
public:
RandomLCG(unsigned int seed = 1 << 19) : x{ seed } {}
double operator()() {
x = (1103515245 * x + 12345) % (1u << 31);
return x * 1.0 / (1u << 31);
}
};
int main() {
random_lcg(42);
std::cout << random_lcg() << ' ' << random_lcg() << ' ' << random_lcg() << '\n';
RandomLCG random(42);
std::cout << random() << ' ' << random() << ' ' << random() << '\n';
}
The output is the same from the C-style random_lcg() function and the C++ RandomLCG class, but the C++ version is preferable as it allows for multiple engines and encapsulates all of its state in the object. (It is also hardly any more code.) If you must use global state, such as std::cout shown above, then keep this in the client code as far as possible.
2. Recursion
In case you didn’t know, FP is big on recursion. In fact, it has to be as loops imply mutable variables (see below). The accidental discovery that compile-time compilation of constant integral values was possible using C++98’s template syntax meant that C++ unwittingly got given one of the tenets of FP. However, TMP (Template Metaprogramming) is compile-time only and not for the faint-hearted. Typically it is necessary to define a base case of a function as well as the general case, such as:
template<int N>
constexpr int factorial() {
return N * factorial<N-1>();
}
template<>
constexpr int factorial<0>() {
return 1;
}
static_assert(factorial<0>() == 1);
static_assert(factorial<5>() == 120);
This code does nothing at run-time, but does compute the values of 0! and 5! at compile-time. However in C++ we get the best of both worlds with generalized constexpr functions, so the result can be used for compile-time constants such as std::array sizes, and called at run-time with any other valid value, such as:
constexpr unsigned long long factorial(unsigned long long n) {
return (n < 2) ? 1 : n * factorial(n - 1);
}
To obtain the benefit of recursion in an FP style, together with TMP-style magic, declare as many (small, pure) functions as possible constexpr.
3. Immutability
Immutable values can be assigned to once, possibly at run-time or at compile-time. Once assigned, it is illegal to try to change them. This brings a number of advantages, such as thread safety, and disadvantages, such as a lack of loop counter variables as mentioned above. The program below prints out two standard containers, with separators, without using any loops. Instead it recursively calls itself with a std::span with the first element removed, stopping the recursion when the size of the std::span is one:
#include <span>
#include <iostream>
#include <vector>
template<typename T>
void printContainer(const std::span<T> s, std::ostream& os = std::cout) {
os << s.front();
if (s.size() > 1) {
os << ", ";
printContainer(s.subspan(1), os);
}
}
int main() {
std::vector vi{ 1, 2, 3, 4, 5 };
printContainer(std::span(vi)); // '1, 2, 3, 4, 5'
std::cout << '\n';
std::vector vf{ 1.1, 2.2, 3.3, 4.4 };
printContainer(std::span(vf)); // '1.1, 2.2, 3.3, 4.4'
std::cout << '\n';
}
Notice that the second (defaulted) parameter to printContainer() is an std::ostream, so the same function could be used to output to a file or std::ostringstream. The above code solves the problem of a trailing separator, and by using std::span avoids copying the whole container when removing the first element, so is reasonably efficient in space and time.
4. Referential Transparency
Related to considerations of purity, referential transparency is the concept where calling the same function with the same parameters is guaranteed to return the same result. This can be useful where the call is expensive but the result is cheap to store for future use. Keeping the result(s) for later calls is called memoization. Below is a demonstration of this technique using the mathematically elegant but highly inefficient Fibonacci Number generator:
#include <iostream>
#include <functional>
#include <unordered_map>
#include <string>
template<typename R, typename P>
class Memoizer {
constexpr R f(const P& n) {
if (n < 2) {
return n;
}
else {
return call(n - 2) + call(n - 1);
}
}
std::unordered_map<P,R> m;
public:
R call(const P& param) {
if (auto iter = m.find(param); iter != m.end()) {
return iter->second;
}
else {
auto r = f(param);
m.insert({ param, r });
return r;
}
}
};
int main(const int argc, const char **argv) {
Memoizer<long long,long long> m;
if (argc == 2) {
auto n = std::stoll(argv[1]);
std::cout << "Fibonacci(" << n << "): " << m.call(n) << '\n';
}
else {
for (long long n = 0; n != 50; ++n) {
std::cout << "Fibonacci(" << n << "): " << m.call(n) << '\n';
}
}
}
The member function f() is declared private, and so client code must use function call(). The parameter and result are stored in an std::unordered_map ready to by used in preference in future. The call() function is general, and could be used without changes for any function taking a single parameter. Note that to gain the full benefit of memoization, f() must also use call() in its recursive return statement.
5. Higher-Order Functions
The final FP concept we’ll look at is that of functions which accept other functions as parameters. This may sound arcane and complex, but you’ve probably already used higher-order functions in your own code when calling the Standard Library algorithms. Below are two ways to print a std::vector<int> to the standard output stream:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector v{ 0, 1, 2, 3, 4, 5 };
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n'; // '0 1 2 3 4 5 '
std::for_each(v.begin(), v.end(), [&v](const auto& value){
std::cout << value;
std::cout << ((&value == &v.back()) ? "\n" : ", ");
}); // '0, 1, 2, 3, 4, 5'
}
Use of std::copy() to produce output may seem strange at first, but use of the Standard Library in this way will gain you the respect of your Line Manager and the adulation of your work colleagues. In fact it’s a bit limited in practice as it writes a trailing separator, so the std::for_each() version can be used where this is an issue (this needs to use a capturing lambda). Note that the addresses of value and v.back() are compared to determine whether it its the final element to be printed.
That’s all for this article, hopefully this introduction to FP concepts in C++ has inspired and equipped you to begin your Functional journey. Full source code for the examples presented in this article is available on GitHub.
Learn Modern C++ 