Skip to content

Instantly share code, notes, and snippets.

@deciduously
Last active October 3, 2019 16:15
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save deciduously/fdb8ee23b4f3d73e4340ef85359edce6 to your computer and use it in GitHub Desktop.
The BenFolds Five
#include <iostream>
#include <vector>
class BenFolds {
public:
// fold - Fold a binary operation over a vector
template <typename T, typename R, typename BinOp>
static R fold(std::vector<T> elems, R acc, BinOp func)
{
int length = elems.size();
if (length == 0)
{
// base case - empty list
// Sub-problem is trivial - we're already done. The passed accumulator holds the result
return acc;
}
else
{
// Calculation is not complete - sub-problem is also trivial
// Call function on accumulator using first element in vector as operand
R newAcc = func(acc, elems[0]);
// Create a new input from the second element onward of the current input
std::vector<T> newInput(elems.begin() + 1, elems.end());
// Recur with rest of list and new accumulator
return fold(newInput, newAcc, func);
}
}
// Or - True if any element is true, else False
static bool foldOr(std::vector<bool> bools)
{
return fold<bool>(bools, false, [](bool acc, bool curr) { return acc || curr; });
}
// Any - True if any element satisfies predicate, else false
template <typename T, typename Predicate>
static bool foldAny(std::vector<T> elems, Predicate p)
{
return fold(elems, false, [p](bool acc, T curr) { return acc || p(curr); });
}
// Elem - True if element found in elements, else false
template <typename T>
static bool foldElem(std::vector<T> elems, T elem)
{
return foldAny(elems, [elem](T curr) { return elem == curr; });
}
// Map - Result of performing func() on each elem in elems
template <typename T, typename Op>
static std::vector<T> foldMap(std::vector<T> elems, Op func)
{
return fold(elems, std::vector<T>(), [func](std::vector<T> acc, T curr) {
acc.push_back(func(curr));
return acc;
});
}
}; // class BenFolds
// Pretty-print a vector
template <typename T>
std::ostream &operator<<(std::ostream &stream, const std::vector<T> vec)
{
stream << "[";
for (int i = 0; i < vec.size(); i++)
{
stream << vec[i];
if (i < vec.size() - 1)
{
stream << ", ";
}
}
stream << "]";
return stream;
}
int main()
{
using std::cin;
using std::cout;
using std::vector;
// Folds object
BenFolds bf;
vector<int> nums;
for (int i = 0; i < 5; i++)
{
nums.push_back(i);
}
cout << "Set: " << nums << "\n";
int acc = 0;
// Test basic fold
int result = bf.fold(nums, acc, [](int acc, int curr) { return acc + curr; });
cout << "Testing fold...\nSum: " << result << "\n";
// Throwaway to ensure foldOr works
vector<bool> bools = {false, false, false, true, false};
cout << "Testing foldOr...\nThis should be true: " << bf.foldOr(bools) << "\n";
// Check for any even elements - should be true
cout << "Testing foldAny...\nAre there even elements in the set: " << bf.foldAny(nums, [](int n) { return n % 2 == 0; }) << "\n";
cout << "Are there elements greater than 10: " << bf.foldAny(nums, [](int n) { return n > 10; }) << "\n";
// Check if the number '2' is in the set - should be true
cout << "Testing foldElem...\nIs the number 2 present in the set: " << bf.foldElem(nums, 2) << "\n";
cout << "Is the number 8 present in the set: " << bf.foldElem(nums, 8) << "\n";
// Double each number in the set
cout << "Testing foldMap...\nHere's each element doubled: " << bf.foldMap(nums, [](int elem) { return elem * 2; }) << "\n";
return 0;
}
@deciduously
Copy link
Author

g++ --std=c++11 -o benfolds benfolds.cpp

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment