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