I'm trying to write a generic fold function using the new anonymous functions available in C++11, here is what I have:
template<typename T>
T foldl(std::function<T(T,T)> f, T initial, std::vector<T> items) {
T accum = initial;
for(typename std::vector<T>::iterator it = items.begin(); it != items.end(); ++it) {
accum = f(accum, (*it));
}
return accum;
}
The following attempt to use it:
std::vector<int> arr;
arr.assign(8, 2);
foldl([] (int x, int y) -> int { return x * y; }, 1, arr);
causes an error:
main.cpp:44:61: error: no matching function for call to 'foldl(main(int, char**)::<lambda(int, int)>, int, std::vector<int>&)'
main.cpp:44:61: note: candidate is:
main.cpp:20:3: note: template<class T> T foldl(std::function<T(T, T)>, T, std::vector<T>)
main.cpp:20:3: note: template argument deduction/substitution failed:
main.cpp:44:61: note: 'main(int, char**)::<lambda(int, int)>' is not derived from 'std::function<T(T, T)>'
It seems to me that using std::function
is not the right way to go about defining the type of f
. How can I correct this?
Although C is not the language that supports many FP concepts out of the box, higher-order functions can be implemented using function pointers and also with compiler support.
map function, found in many functional programming languages, is one example of a higher-order function. It takes as arguments a function f and a collection of elements, and as the result, returns a new collection with f applied to each element from the collection.
A higher order function is a function that takes a function as an argument, or returns a function . Higher order function is in contrast to first order functions, which don't take a function as an argument or return a function as output. Earlier we saw examples of . map() and . filter() .
Introduced in ES5, this higher-order function returns a new array with the results of callback applied to every element from the original array, in the same order. The callback receives three arguments: The current element value. The current element index.
Your code is not very generic. There is no need to require a function
, vector
, or anything of the kind. And generally, in C++, functions would go at the end of the argument list (especially important for lambdas, as they can be big).
So it would be better (ie: more standard) to write this as this:
template<typename Range, typename Accum>
typename Range::value_type foldl(const Range &items, const typename Range::value_type &initial, Accum f)
{
typename Range::value_type accum = initial;
for(const auto &val : items) {
accum = f(accum, val);
}
return accum;
}
Or you could just use std::accumulate
which does the exact same thing.
I'm not certain why this template is failing, but switching over to using a template parameter for the function instead of std::function<>
seems to work wonderfully.
template<typename T, typename F>
T foldl(F f, T initial, std::vector<T> items) {
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With