Monoids in C++

monoid.cpp

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

// In Haskell, the Monoid typeclass is parameterised by only a type. Such a
// definition requires “newtype hacks” to produce different monoids on the same
// type. This definition is parameterised by both the type and the function, and
// as such can be used to define different monoids on the same type without any
// interference.
template<typename T, T append_(T const&, T const&)>
struct Monoid {
	typedef T type;
	static T append(T const& a, T const& b) {
		return append_(a, b);
	}
	static const T empty;
};

////////////////////////////////////////

template<typename T>
T add(T const& a, T const& b) { return a + b; }

template<typename T>
T multiply(T const& a, T const& b) { return a * b; }

////////////////////////////////////////

// “(Int, (+)) forms a monoid with 0 as the identity.”
// instance Monoid Int (+) where mempty = 0
template<> const int Monoid<int, add<int>>::empty(0);

// “(Int, (*)) forms a monoid with 1 as the identity.”
// instance Monoid Int (*) where mempty = 1
template<> const int Monoid<int, multiply<int>>::empty(1);

// mconcat :: (Monoid m mappend) -> [m] -> m
// mconcat = fold mappend mempty
template<typename M>
typename M::type mconcat(const vector<typename M::type>& xs) {
	return accumulate(begin(xs), end(xs), M::empty, M::append);
}

////////////////////////////////////////

template<typename T>
using SumMonoid = Monoid<T, add<T>>;

template<typename T>
T sum(const vector<T>& xs) { return mconcat<SumMonoid<T>>(xs); }

template<typename T>
using ProductMonoid = Monoid<T, multiply<T>>;

template<typename T>
T product(const vector<T>& xs) { return mconcat<ProductMonoid<T>>(xs); }

////////////////////////////////////////

int main() {
	vector<int> xs = { 1, 1, 2, 3, 5, 8 };
	cout
		<< "Sum: " << sum(xs) << '\n'
		<< "Product: " << product(xs) << '\n';
	vector<double> ys = { 1.1, 2.2, 3.3 };
	// “undefined reference to ‘Monoid<double, …add…>::empty’” means
	// “no identity was specified for the monoid (double, (+)).”
	cout
		<< "Sum: " << sum(ys) << '\n';
}