Express general monadic interface (like Monad class) in C++

Question

Is it even possible to express a sort of monad" C++ ? I started to write something like this, but stuck:

#include <iostream>

template <typename  a, typename b> struct M;

template <typename a, typename b> struct M {
    virtual M<b>& operator>>( M<b>& (*fn)(M<a> &m, const a &x) ) = 0;
};

template <typename a, typename b> 
struct MSome : public M<a> {
    virtual M<b>& operator>>( M<a>& (*fn)(M<a> &m, const a &x) ) {
        return fn(*this, x);
    }

private:
    a x;
};

M<int, int>& wtf(M<int> &m, const int &v) {
    std::cout << v << std::endl;
    return m;
}

int main() {
//    MSome<int> v;
//    v >> wtf >> wtf;
    return 0;
}

but faced the lack of polymorphism. Actually it may be my uncurrent C++ 'cause I used it last time 8 years ago. May be it possible to express general monadic interface using some new C++ features, like type inference. It's just for fun and for explaining monads to non-haskellers and non-mathematicians.

Answer 1

C++' type system is not powerful enough to abstract over higher-kinded types, but since templates are duck-typed you may ignore this and just implement various Monads seperately and then express the monadic operations as SFINAE templates. Ugly, but the best it gets.

This comment is bang on the money. Time and time again I see people trying to make template specializations 'covariant' and/or abuse inheritance. For better or for worse, concept-oriented generic programming is in my opinion* saner. Here's a quick demo that will use C++11 features for brevity and clarity, although it should be possible to implement the same functionality in C++03:

(*: for a competing opinion, refer to "Ugly, but the best it gets" in my quote!)

#include <utility>
#include <type_traits>

// SFINAE utility
template<typename...> struct void_ { using type = void; };
template<typename... T> using Void = typename void_<T...>::type;

/*
 * In an ideal world std::result_of would just work instead of all that.
 * Consider this as a write-once (until std::result_of is fixed), use-many
 * situation.
 */    
template<typename Sig, typename Sfinae = void> struct result_of {};
template<typename F, typename... Args>
struct result_of<
    F(Args...)
    , Void<decltype(std::declval<F>()(std::declval<Args>()...))>
> {
    using type = decltype(std::declval<F>()(std::declval<Args>()...));
};
template<typename Sig> using ResultOf = typename result_of<Sig>::type;

/*
 * Note how both template parameters have kind *, MonadicValue would be
 * m a, not m. We don't whether MonadicValue is a specialization of some M<T>
 * or not (or derived from a specialization of some M<T>). Note that it is
 * possible to retrieve the a in m a via typename MonadicValue::value_type
 * if MonadicValue is indeed a model of the proper concept.
 *
 * Defer actual implementation to the operator() of MonadicValue,
 * which will do the monad-specific operation
 */
template<
    typename MonadicValue
    , typename F
    /* It is possible to put a self-documenting assertion here
       that will *not* SFINAE out but truly result in a hard error
       unless some conditions are not satisfied -- I leave this out
       for brevity
    , Requires<
        MonadicValueConcept<MonadicValue>
        // The two following constraints ensure that
        // F has signature a -> m b
        , Callable<F, ValueType<MonadicValue>>
        , MonadicValueConcept<ResultOf<F(ValueType<MonadicValue>)>>
    >...
    */
>
ResultOf<MonadicValue(F)>
bind(MonadicValue&& value, F&& f)
{ return std::forward<MonadicValue>(value)(std::forward<F>(f)); }

// Picking Maybe as an example monad because it's easy
template<typename T>
struct just_type {
    using value_type = T;

    // Encapsulation omitted for brevity
    value_type value;

    template<typename F>
    // The use of ResultOf means that we have a soft contraint
    // here, but the commented Requires clause in bind happens
    // before we would end up here
    ResultOf<F(value_type)>
    operator()(F&& f)
    { return std::forward<F>(f)(value); }
};

template<typename T>
just_type<T> just(T&& t)
{ return { std::forward<T>(t) }; }

template<typename T>
just_type<typename std::decay<T>::type> make_just(T&& t)
{ return { std::forward<T>(t) }; }

struct nothing_type {
    // Note that because nothing_type and just_type<T>
    // are part of the same concept we *must* put in
    // a value_type member type -- whether you need
    // a value member or not however is a design
    // consideration with trade-offs
    struct universal { template<typename T> operator T(); };
    using value_type = universal;

    template<typename F>
    nothing_type operator()(F const&) const
    { return {}; }
};
constexpr nothing_type nothing;

It is then possible to write something like bind(bind(make_just(6), [](int i) { return i - 2; }), [](int i) { return just("Hello, World!"[i]); }). Be aware that the code in this post is incomplete in that the wrapped values aren't forwarded properly, there should be errors as soon as const-qualified and move-only types are involved. You can see the code in action (with GCC 4.7) here, although that might be a misnomer as all it does is not trigger assertions. (Same code on ideone for future readers.)

The core of the solution is that none of just_type<T>, nothing_type or MonadicValue (inside bind) are monads, but are types for some monadic values of an overarching monad -- just_type<int> and nothing_type together are a monad (sort of -- I'm putting aside the matter of kind right now, but keep in mind that it's possible to e.g. rebind template specializations after the fact, like for std::allocator<T>!). As such bind has to be somewhat lenient in what it accepts, but notice how that doesn't mean it must accept everything.

It is of course perfectly possible to have a class template M such that M<T> is a model of MonadicValue and bind(m, f) only ever has type M<U> where m has type M<T>. This would in a sense make M the monad (with kind * -> *), and the code would still work. (And speaking of Maybe, perhaps adapting boost::optional<T> to have a monadic interface would be a good exercise.)

The astute reader would have noticed that I don't have an equivalent of return here, everything is done with the just and make_just factories which are the counterparts to the Just constructor. This is to keep the answer short -- a possible solution would be to write a pure that does the job of return, and that returns a value that is implicitly convertible to any type that models MonadicValue (by deferring for instance to some MonadicValue::pure).

There are design considerations though in that the limited type deduction of C++ means that bind(pure(4), [](int) { return pure(5); }) would not work out of the box. It is not, however, an insurmountable problem. (Some outlines of a solution are to overload bind, but that's inconvenient if we add to the interface of our MonadicValue concept since any new operation must also be able to deal with pure values explicitly; or to make a pure value a model of MonadicValue as well.)