CppCon 2016: Ben Deane 'std::accumulate: Exploring an Algorithmic Empire'

—
—
What is the most powerful algorithm in the STL? In the world? There are many cases to be made. But this talk explores what I think is a pretty good candidate, which C++ calls std::accumulate(). Tucked away in ＜numeric＞, perhaps relatively unregarded when compared with workhorses like std::find_if() and std::partition(); nevertheless, std::accumulate() is in some sense the ur-algorithm on sequences.

Let’s explore the result of looking at code through an accumulate-shaped lens, how tweaking the algorithm for better composability can unlock many more uses, and how it can be further genericized with applications to parallelism, tree structures, and heterogeneous sequences.

std::accumulate(): it’s not just for adding things up!
—
Ben Deane
Principal Software Engineer, Blizzard Entertainment
—

*-----*
*-----*

[arisweedler]

42:48 - implementing reverse by accumulating into a set of chained function calls & then invoking them all - this what the IO monad does. You take an impure operation, an impure function (getting input or writing output) and wrap it in a monad.

Wrapping in a monad: instead of letting the side effects happen, you put the side effects as an additional variant to the original output.

Then you do the monoidal composition - chaining together all these monads - and you’re left with an accumulation of how the data will flow through. You’re left with all your yet-to-be-called function calls.

Finally, once you’ve built up this structure, you let it rip. You let all the impure IO happen, reading from users and writing to the screen and all that.

Super cool!

[MatthewChaplain]

Good talk. Accumulate has started turning up in my work more and more recently as well. One particular instance I was proud of was a messaging framework that sent messages received from a client to a number of observers. The observers could respond with vectors of messages to send back. Thanks to Boost.Signals2, the "token combiner" function wrapped accumulate to flatten the returned vectors of messages into one vector of messages.

[YourCRTube]

Nice talk. I would have liked, it was a bit more focused and with more real world examples like the improved API mentioned a few times. Also the main (and only) complete example felt a bit off, because there seems to be missed opportunity to use overloading instead of the 6 funcs passed.

[LordNezghul]

What's the neutral value for min/max?

[MaherBaba]

I always thought type must be the same, is nice

[symq]

TL;DR: C++ programmer discovers the power of functional programming and starts yet another attempt to cram it into C++

[llothar]

Turning trivial stuff into complicated shit so someone can write a PhD about it.
I just can't stand this type of modern programmers anymore. There is no advantage to save 3 lines of very clear code. I had to turn of at the JSON printer. Damit. Thats a stupid API and coding style and i guess 100 times less performant then what i would write.