C++ Algorithms, Boost and function currying

[spivey]

http://blog.objectmentor.com/articles/2010/06/12/c-algorithms-boost-and-function-currying

[dkersten]

The author went from this:

    int Dice::total() const {
      int total = 0;
      for(const_iterator current = dice.begin();
          current != dice.end();
          ++current)
        total += (*current)->faceValue();
      return total;
    }

to this:

    int Dice::total() const {
      return std::accumulate(
          dice.begin(),
          dice.end(),
          0,
          bind(std::plus<int>(), _1, bind(&Die::faceValue, _2))
      );
    }

and shows his intermediate steps. I took his last variant and converted it to the following, using Intel Threading Building Blocks to perform a parallel reduce:

    class Sum {
        const std::vector<Face*>& v;
    public:
        int sum;
        void operator()( const tbb::blocked_range<size_t>& r ) {
            const std::vector<Face*>& a = v;
            for( size_t i = r.begin(); i != r.end(); ++i )
                sum += a[i]->faceValue();
        }
        Sum( Sum& x, tbb::split ) : v(x.v), sum(0) {}
        void join( const Sum& y ) {sum += y.sum;}
        Sum(const std::vector<Face*>& a ) : v(a), sum(0) {}
    };

    int Dice::parallel_total () const {
        Sum s(dice);
        tbb::parallel_reduce(tbb::blocked_range<size_t>(0, dice.size()),
                             s,
                             tbb::auto_partitioner());
        return s.sum;
    }

I had to guess what his Dice implementation contained and if I wrote in from scratch, I may have done it differently (eg, I'd handle that vector in Sum differently). Also, it doesn't really seem worth it performance-wise ;-) but still interesting to see it in action.

[Chris_Newton]

A more declarative programming style has many potential benefits. The trouble is, the version in that style is supposed to look something like this:

    total dice = sum (map faceValue dice)

C++ is showing its age now, as ideas from other programming styles are entering the mainstream. Modern programming languages, designed with the benefit of hindsight, support those idioms natively and much more effectively than a bolted-on library, the cleverness of the Boost implementers notwithstanding.

In this context, I think one of the commenters on the original article probably had it right: given that C++ is essentially an imperative language, using the new range-based for loops is a more natural way to write this algorithm.

[ANH]

Okay, I admit this is the first time I've seen the word 'currying'. I've heard it spoken and thought it was a neologism derived from "courier", but it's apparently named after a man called Haskell: http://en.m.wikipedia.org/wiki/Currying?wasRedirected=true

[steveklabnik]

This is also currently on HN as part of zedshaw's post on Shedding Bikes: http://sheddingbikes.com/posts/1276445247.html http://news.ycombinator.com/item?id=1427599

[d0m]

why use bind and not a "c++ lambda" if you are using boost?

The expression:

bind(std::plus<int>(), _1, bind(&Die::faceValue, _2))

makes the code harder to read instead of easier, which isn't an improvement.

[tman]

Where functional programming in C++ falls apart is this step:

  bind(std::plus<int>(), _1, bind(&Die::faceValue, _2))

When I first learned the STL, I worked pretty hard to figure out bind, etc., and get rid of all my for loops. The problem is that it doesn't actually buy you that much. The for loop is uglier, but simpler to maintain, read, and debug.

Luckily the lambda syntax from the new standard already appears to be available in experimental gcc. This is going to be a game-changer.

[rubashov → tman]

The lambda stuff is in g++ 4.5, which is a stable release, right? It's not really experimental.

[DCoder → rubashov]

Lambdas are also supported in MSVC++ 2010.

[tman → rubashov]

http://gcc.gnu.org/gcc-4.5/cxx0x_status.html : "Status of Experimental C++0x Support in GCC 4.5"

Last month's release of 4.5.0 is stable, but the C++0x support is experimental.