diff options
Diffstat (limited to 'src/monoid.hpp')
-rw-r--r-- | src/monoid.hpp | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/src/monoid.hpp b/src/monoid.hpp new file mode 100644 index 00000000..465e58af --- /dev/null +++ b/src/monoid.hpp @@ -0,0 +1,37 @@ +#pragma once + +#include <numeric> +#include <vector> + +/** + * A monoid is an algebraic structure with a single associative + * binary operation ('append') and an identity element ('empty'). + * + * See https://en.wikipedia.org/wiki/Monoid + * + * Shamelessly adapted from: + * + * https://gist.github.com/evincarofautumn/2b5f004ca81e33c62ff0 + */ +template<typename T, T append_(T const&, T const&), const T &empty_> +struct monoid { + /* Access the type the monoid operates on */ + typedef T type; + + /* Append two T's */ + static T append(T const& a, T const& b) { + return append_(a, b); + } + + /* The value of an empty T */ + static constexpr T empty = empty_; +}; + +/** + * mconcat :: (Monoid m mappend) -> [m] -> m + * mconcat = fold mappend mempty + */ +template<typename M> +typename M::type mconcat(const std::vector<typename M::type>& xs) { + return std::accumulate(std::begin(xs), std::end(xs), M::empty, M::append); +} |