How to fold STL container?

Question

I need an analog of Haskell's foldl function to fold any STL containers. Expected signature is like following:

template Iterator, FoldingFunction, Result
Result foldl(
  Iterator begin, 
  Iterator end, 
  FoldingFunction f, 
  Result initValue);

Standard STL has no such function. Does Boost have any?

I know it's pretty simple to implement, but I'd like to know whether there's any ready standardized implementation.

And one more question: how do you usually fold data lists in C++/STL?

Answer 1

STL does have such a function: std::accumulate. However, it is in the header <numeric>, not <algorithm>.

Actually the Wikipedia page on "Fold" already listed the foldl/foldr functions on most programming languages, including C++.

Answer 2

Have you looked at std::accumulate in the <numeric> header?

Answer 3

here's my implementation using std::accumulate

template<typename collection, typename operation>
typename collection::value_type reduce(collection col, operation op)
{
    return accumulate(col.begin(),  col.end(), typename collection::value_type(), op);
}

the reduce means fold in Haskell. And this function template may make the program more functional :)

Answer 4

Although std:: accumulate seems to be the best candidate, I think that the requirement can be achieved by using good old for_each too.

I took the examples from the link in the answer of KennyTM, and translated all of them to for_each. The full code is posted at codepad, following is some excerpt:

struct result_functor {
    result_functor( int initial, int multiplier ) :
        result_( initial ), multiplier_( multiplier ) {
    }
    int operator()( int x ) {
        result_ += multiplier_ * x;
        return result_;
    }
    int result_;
    int multiplier_;
};

const int init = 100;
const int numbers[] = { 10, 20, 30 };

const int accum_sum = std::accumulate( numbers, numbers + 3, init );
const result_functor for_sum = for_each( 
    numbers, numbers + 3, result_functor( init, +1 ) );
assert( accum_sum == for_sum.result_ );

Answer 5

why not just;

b_t foldl(b_t (*f)(b_t,a_t),b_t base_case,a_t * in_list){
 int l = sizeof(inList)/sizeof(a_t);
 b_t carry = base_case;
 for(int i = 0;i<l;i++){
   carry = f(carry,in_list[i]);
  }
 return carry;
}

or recursively; // maybe you could help me with the correct syntax...

b_t foldl(b_t (*f)(b_t,a_t),b_t base_case,a_t * in_list){
 return foldl(f,f(base_case,in_list[0]),in_list + 1);      
}