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?

@Konrad: [fold](http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29) = reduce = accumulate. — kennytm, Oct 11 '10 at 13:52
@Konrad - process a data structure in some order and build a return value. http://www.haskell.org/haskellwiki/Fold — DumbCoder, Oct 11 '10 at 13:52

score 43 · Accepted Answer · edited Oct 11 '10 at 14:14

43

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++.

edited Oct 11 '10 at 14:14

James McNellis

348,265
75
913
977

answered Oct 11 '10 at 13:49

kennytm

510,854
105
1,084
1,005

Note that `accumulate` uses the `value_type` of the iterator arguments for the internal accumulator variable, despite accepting and returning a distinct type, and allowing other types still in the functor argument. – Potatoswatter Oct 12 '10 at 00:04
@Potatoswatter: I don't see this from accumulate definition:TYPE accumulate( input_iterator start, input_iterator end, TYPE val, BinaryFunction f ); – Andrey Oct 12 '10 at 15:39
@Andrey: Never mind. I was thinking of Defect Report 539 (http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#539). `accumulate` uses the proper internal type. – Potatoswatter Oct 12 '10 at 15:50
By the way, `accumulate` is a left fold; think (1 + 2) + 3 rather than 1 + (2 + 3); like `foldl` in Haskell. – user2023370 May 11 '11 at 19:12
2

@user: Use the reverse iterator for `foldr`. – kennytm May 11 '11 at 19:16
@KennyTM Yes, replace `x.begin()` and `x.end()` with `x.rbegin()` and `x.rend()`. – user2023370 May 11 '11 at 19:57

wheaties · Answer 2 · 2010-10-11T17:48:31.513

5

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

edited Oct 11 '10 at 17:48

answered Oct 11 '10 at 13:49

wheaties

35,646
15
94
131

It's `std::accumulate`. It's in the `std` namespace, but in the `` header. :) – jalf Oct 11 '10 at 17:11
@jalf keep 'em coming. Only way I stay in line. :P – wheaties Oct 11 '10 at 17:48

score 1 · Answer 3 · answered Jan 07 '15 at 18:28

1

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 :)

answered Jan 07 '15 at 18:28

Panic Fred

44
2

Using `begin(col)` and `end(col)` would be more generic but still this function is quite redundant beause `accumulate` is simple to call directly as well. – sim642 Feb 15 '15 at 07:32

score 0 · Answer 4 · edited May 23 '17 at 11:46

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_ );

@Loom This answer suggests stateful functors are fine for `std::for_each`: http://stackoverflow.com/a/6113053/2348315, is it incorrect? — PeterSW, Mar 20 '15 at 14:14

score -1 · Answer 5 · answered Mar 20 '15 at 13:53

-1

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);      
}

answered Mar 20 '15 at 13:53

error

519
4
5

2

Because that only works with `b_t`, `a_t`, and function pointers. Also it is less trustworthy than the much more widely used and tested alternative that can be found in the standard library implementations. – PeterSW Mar 20 '15 at 14:06

How to fold STL container?

5 Answers5

Linked