Overly Functional C++: The Fold
This is part two of a three-part post, but don’t worry - each part stands alone. You don’t need to read any of the first post before reading this.
This code implements a the higher-order “fold” function for a std::vector<int>, which is a variable-size one-dimensional collection of integers available in the standard library. The actual int-type is system and compiler dependent, but for this toy demo that’s not a concern of mine. For trivia, mine are 32-bit longs.
I did this to see how hard it would be. The answer turned out to be “not”.
The code that appears here compiles as shown using a command like g++ --std=c++11 -o foldtest foldtest.cpp, and should work without modification on other compilers that support C++11.
In functional programming, the fold function is a commonly-used building block. It abstracts away the recursive part of the function definition for a very common use case - producing an accumulated result by processing each element in a collection - into a flexible, safe API.
When implemented correctly, we should expect the following output from our test code:
The main() function to generate that output looks like this:
We define a hardcoded vector [1,2,3,4,5], display it to the user, and then pass it to our fold function with an accumulator and the lambda to use, displaying that result.
Before implementing the fold itself, I defined a quick template to pretty-print a vector like shown in the expected output, for debugging purposes:
All that’s missing is the actual fold:
The body is simple. The base case simply returns, and the recursive case builds the new adjusted inputs and passes them back to the function. The one part I had to look up was std::function, used for the type of the lambda parameter. I had written essentially what I ended up with in pseudocode, not knowing how I’d actually need to implement the working version, only to find the exact construct I wanted actually existed. Thanks, C++.
To verify that this code performs reasonably, I replaced the hardcoded input with a loop to populate a vector with numbers from 0 through n:
On my computer, this code sums this vector in just over two seconds:
However, any higher value dumps core.
One of those hashtags is not like the others… I also have a question about extending this code. This is an extremely limited fold function, with the type of the collection to fold over fully specified as std::vector<int>. This sounds like a job for a template to me, but from what I understand C++11 doesn’t fully support templated lambdas yet. Is that more or less accurate?
Photo by Kelly Sikkema on Unsplash