Thread: Implementing right fold in terms of std::accumulate

I'm trying to implement left- and right-fold in C++ using std::accumulate. The left-fold is trivial since it is identical to std::accumulate, but the right-fold is less obvious.

I figured it was simply a matter of traversing the input sequence in reverse, which is correct according to the Wikipedia article on the subject.

Originally Posted by Wikipedia

Left-fold:

Code:

std::accumulate(begin, end, initval, func)

Right-fold:

Code:

std::accumulate(rbegin, rend, initval, func)

However, the results i'm getting does not seem to imply that this is a correct implementation. If my initial element is simply the value 5, and the input sequence is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], my custom fold-right returns -50, which is identical to the left fold with the same input.

If i ask my Haskell interpreter the same question:

Code:

foldr (-) 5 [1..10]

...i'm told the answer is 0. This is corroborated by my ML interpreter.

If my understanding of a right fold is correct, this is the expression that is being evaluated:

Code:

(1 - (2 - (3 - (4 - (5 - (6 - (7 - (8 - (9 - (10 - 5))))))))))

Which does indeed equal 0.

I tried flipping the arguments of the binop for std::accumulate with a lambda, and this did indeed make my foldr behave as those of Haskell and ML, but this only works if the arguments to the binop are of the same type, which isn't always the case.

So i'm out of ideas, am i gonna have to roll my own if i want foldr in C++?

I think accumulate makes the most sense when you work with numbers. In that case, it is not likely you will have problems understanding what a binary operation will really do.
Accumulate will always do initval - a - b - c ... - z.
You may have to flip the operands if this order is not correct.

For weird reductions you have to get a bit creative. For example, rfolding a list of chars into a string:

Code:

#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

int main()
   {
   char stuff[] = {'a','b','x','d','c','k','f'};
   string folded (reverse_iterator<char*> (stuff+7), reverse_iterator<char*> (stuff));
   cout << folded << endl;
   }

In general I feel like reverse_iterator solves your problem in the general case, as long as you have a binary operator that comes up with the proper result. (In this case, "" + *rbegin() is just "f", so it works.) If you don't have one, overload it.

Of course, with those things in hand, accumulate can be made to work, but it is up to you if accumulate is clearer than a loop or something else.

Originally Posted by whiteflags

In general I feel like reverse_iterator solves your problem in the general case, as long as you have a binary operator that comes up with the proper result. (In this case, "" + *rbegin() is just "f", so it works.) If you don't have one, overload it.

This foldr is for a library, so the arguments could be anything, and of (almost) any type, and i need to be able to handle it all. I guess i'll have to roll my own, it's just a real shame having to get my hands dirty with the right-fold, when foldl can be done so succinctly.

Thanks for the reply.

What issue is the order and type of the arguments giving you?

Code:

#include <numeric>
#include <vector>
#include <cassert>
#include <functional>

int main()
{
	using namespace std;
	vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	auto thisWorks = [](double curr, int item) { return item - curr; };

	auto notThis = [](int item, double curr) { return item - curr; };

	using namespace std::placeholders;
	auto butThisWorks = bind(notThis, _2, _1);

	double result1 = accumulate(v.rbegin(), v.rend(), 5.0, thisWorks);
	double result2 = accumulate(v.rbegin(), v.rend(), 5.0, notThis);
	double result3 = accumulate(v.rbegin(), v.rend(), 5.0, butThisWorks);

	assert(result1 == 0);
	assert(result2 == -50.0);
	assert(result3 == 0);
}

O_o

There are many cases where you may need to reverse the order of parameters for a "binary predicate"/"binary accumulator" so make a tool for that operation.

With such a tool, `foldl' and `foldr' are one line functions if the predicate/accumulator is generalized.

Soma

Code:

int main()
{
    int s[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    cout << accumulate(rbegin(s), rend(s), 5, r_(minus())) << '\n'; // -> 0
    return(0);
}

Originally Posted by CodeMonkey

What issue is the order and type of the arguments giving you?

Well, in your example the types can be implicity converted. Using types where this is not the case, your example won't compile. Accumulate expects the binop to accept these types in a certain order, if i flip the order the compiler complains.