Monoid type class in C++

Question

I am trying to come up with a monoid type class in C++. Here I am giving a working example of what I have devised so far.

#include <utility>
#include <vector>
#include <iostream>
#include <string>
#include <type_traits>
#include <iterator>
#include <algorithm>
#include <list>

template<typename T, typename BinaryOp>
struct monoid
{
    //T mempty();
    //T mappend(T,T);
    static constexpr bool is_instance = false;
    using type = T;
};

template<>
struct monoid<int, std::plus<int>>
{
    static int mempty() { return 0 ;}
    static int mappend(int lhs, int rhs) {return lhs + rhs; }
    static constexpr bool is_instance = true;
    using type = int;
};

template<>
struct monoid<double, std::multiplies<double>>
{
    static double mempty() { return 1.0 ;}
    static double mappend(double lhs, double rhs) {return lhs * rhs; }
    static constexpr bool is_instance = true;
    using type = double;
};

template<>
struct monoid<int, std::multiplies<int>>
{
    static int mempty() { return 1 ;}
    static int mappend(int lhs, int rhs) {return lhs * rhs; }
    static constexpr bool is_instance = true;
    using type = int;
};

template <>
struct monoid<std::string, std::plus<std::string>> {
    static std::string mempty(){return std::string{};}
    static std::string mappend(std::string const& lhs,
                               std::string const& rhs){
        return lhs + rhs;
    }
    static constexpr bool is_instance = true;
    using type = std::string;
};

template <typename Container>
struct ContainerAppender{
    Container operator()(Container const& lhs, Container const& rhs)
    {
        Container dst;
        std::merge(std::begin(lhs), std::end(lhs),
                   std::begin(rhs), std::end(rhs),
                   std::back_inserter(dst));

        return dst;
    }
};

template <typename Container>
struct monoid<Container, ContainerAppender<Container>> {
    static Container mempty(){ return Container{}; }
    static Container mappend(Container const& lhs,
                             Container const& rhs){
        return ContainerAppender<Container>{}(lhs, rhs);
    }
    static constexpr bool is_instance = true;
    using type = Container;
};

template <typename T, typename BinaryOp>
constexpr bool is_monoid_v = monoid<T, BinaryOp>::is_instance;

template <typename T, typename BinaryOp>
using is_monoid = std::enable_if_t<is_monoid_v<T, BinaryOp>>;

template<template <typename> typename BinaryOp,
         typename ForwardIt,
         typename = is_monoid<typename ForwardIt::value_type,
                              BinaryOp<typename ForwardIt::value_type>>>
auto mconcat(const ForwardIt begin, const ForwardIt end)
{
    using T = typename ForwardIt::value_type;
    T out{monoid<T, BinaryOp<T>>::mempty()};
    for(ForwardIt it = begin; it != end; it++){
        out = monoid<T, BinaryOp<T>>::mappend(out,*it);
    }
    return out;
}

int main(){
    std::vector<std::string>str_vec{"1","2","3"};
    std::cout << mconcat<std::plus>(str_vec.begin(),
                                    str_vec.end())
              << "\n";

    std::list<double> dbl_li{1.0, 2.3, 4.5};
    double acc = mconcat<std::multiplies>(std::begin(dbl_li),
                                          std::end(dbl_li));
    std::cout << acc << "\n";

    // Reduce vectors as well, nested reduction
    std::vector<std::vector<int>> nested_vec{{1,2,3},{4,5,6},{7,8,9}};
    const auto v= mconcat<ContainerAppender>(std::begin(nested_vec),
                                             std::end(nested_vec));
    int res = mconcat<std::multiplies>(std::begin(v),
                                       std::end(v));
    std::cout << res << "\n";
    return 0;
}

1. What are general code smells you can identify?
2. Are there any problems with my usage of templates and generic programming, how that can be improved?
3. Can you suggest improvements on usability and extendibility of monoid class?

Answer 1

It seems to me that the mappend function should be generated from the BinaryOp. So that makes it the same in all your specializations, and the only thing you need is the matching mempty.

I think you should have a fully generic template that figures out mappend and type from the template arguments, and looks up the proper unit value for that operation using a smaller specialized metafunction.

---

Your monoid::type should be called value_type. And you can get it from declspec(monoid::mempty()) so do you really need a separate entry for that, and if so, shouldn’t you generate it automatically too?

Or, define the functions in terms of the nested value_type rather than peppering the specialization with int and double etc. in all the identical places.

Again, if you factor out mempty, the rest of that just goes away and you don’t need any explicit specializations for monoid.

template<typename T, typename BinaryOp, T unit = UnitFor_v<BinaryOp,T>>
struct monoid
{
    using value_type = T;
    static value_type mempty() { return unit; }
    static value_type mappend (T left,T right) { return BinaryOp()(left, right); }
    using type = T;
};

(deeper thought: I kept the params to mappend by simple value passing, which is probably right for types you’ll use for this, and you always copy on returning anyway. Just make sure it’s move-friendly and optimization-friendly for other types such as large strings)

---

bug

std::begin and end should be unqualified using the two-step.

using std::begin;
auto it1 = begin (container);

so that it picks up ADL for the container and handles built-in types (primitive array) too.

---

Suggest you offer range forms of your algorithms as well (or instead of) two-parameter versions. E.g.

mconcat<std::plus>(str_vec.begin(), str_vec.end())

becomes simply

mconcat<std::plus>(str_vec)

(That also means you can use the range-for in the implementation)

for (auto item : inputrange)
    out = monoid<T, BinaryOp<T>>::mappend(out,item);

---

static std::string mempty(){return std::string{};}

note that now you can write:

static std::string mempty(){return {};}

and the type of thing you are constructing in the return statement is automatically taken from the return type of the function.

Answer 2

@JDługosz has written a great answer, I just want to add that floating point multiplication is not associative. So the instance of Monoid for double is incorrect.

Proof:

int main()
{
    static_assert(
        (31415926535897.9323 *  299792458) * 14142135.6237 !=
         31415926535897.9323 * (299792458  * 14142135.6237)
    );
}

---

I asked about this on the /r/Haskell subreddit, and opinions there seem to be that while Monoid for double is maybe mathematically incorrect it's still useful and reasonable to have.