Overly Functional C++: The BenFolds Five
What a plot twist! I made almost no effort to avoid the pun and I’m only a little sorry.
Despite being a trilogy now, this post stands alone if you’re familiar with the concept of the fold or reduce higher-order function.
In part 2 of yesterday’s minddump, I documented my first stab at a specific fold in C++. I had gotten stuck, though, in trying to make it generic.
I’ve said it before and I’ll say it again: ask DEV stuff, they know things. Thanks to @curtisfenner and @markboer I was able to write the intended generic fold function I had set out to write initially with almost no modification. This newly-generic fold function is a building block, and if you give a nerd a fold…
BenFolds is a class with five static member functions. It defines BenFolds::fold() as a generic version of the code from part 2, and then defines or, any, elem, and map in terms of this fold. I’ll walk through each, or you can grab the gist. This gist compiled and executed successfully for me using g++ -std=c++11 -o benfolds benfolds.cpp on g++ 9.2.0.
This is the only definition with any substance, the rest will all specify parameters to run through this fold:
This implementation is identical to the solution from part 2 apart from the parameterized types. The other four “backup” functions are just specific cases of this fold.
As @curtisfenner pointed out, this naive implementation is needlessly expensive. The recursion is in tail position, which the compiler does optimize for, but each call is allocating a brand new vector to swap into the stack frame. If you needed to optimize this further, you could consider instead passing ever-smaller subslice references to the same vector, or even mutating the original vector in place instead.
The simplest application just takes a list of booleans and tells you if any of them are true. The T in BenFolds::fold() is bool:
The initial accumulator is false. We call || on this accumulator against each element of the passed collection. At the end, if any element was true, the accumulator flipped to true and stuck. Otherwise, nothing was found it’s still false.
To test, I added a quick throwaway to main():
The any function is just a generalization of or:
It’s really almost the same thing. We’re still calling || on the accumulator and this element, but we’re passing the element through some other predicate p before checking for truth.
For example, see if the inputs has any even numbers (it should) or anything greater than 10 (it shouldn’t):
The elem function checks if an element exists in a collection, which is a specialization of any so we can reuse that definition:
It calls foldAny defining the predicate as equality against a specific element. We can test by checking for a specific number, no need to pass a lambda:
We can also define a map function from this fold that builds the target vector in the accumulator:
I tested this one by doubling each element in the input:
Running through all the tests as defined yields this output:
Photo by Oscar Keys on Unsplash