Is there a standard abstraction for semirings or monoids in C++?

Question

Does boost, or any other common C++ library, provide semiring or monoid abstractions (such as a template class)?

I have some algorithms that I would like to express in terms of these abstract structures, but so far I haven't come across anything. I can write my own, but ideally these would be in a library I'm already using such as boost.

Thanks!

Answer 1

SGI STL has MonoidOperation concept. For instance power function is implemented for MonoidOperation.

Boost.Graph library also defines Monoid concept.

In addition to already suggested Elements of Programming you may look to Notes on Programming by Alexander Stepanov (one of authors of EoP). Notes are freely available, and have some overlap with EoP book.

There are style difference between EoP and Notes - EoP is very terse like math textbook, but Notes are more "informal" - there some small stories, etc.

By the way, both have some discussion of referenced above power function implementation.

P.S. there are great talks by Alexander Stepanov:

• Elements of Programming
• STL and Its Design Principles
• A9 lectures
• Greatest Common Measure

P.P.S. Collected Papers of Alexander A. Stepanov

Answer 2

To the best of my knowledge the C++ standard library doesn't have any abstractions around these structures. However, Alex Stepanov, inventor of the STL, wrote a book entitled Elements of Programming in which he writes a variety of useful functions that operate on monoids, groups, binary operators, unary functions, etc. It's not necessarily a standard, but it might be a good starting point for further exploration.

Hope this helps!