Monad interface in C++

Question

I am currently learning a little bit haskell and started to figure out how monads work. Since I normaly code C++ and I think the monad pattern would be (as fas as I understand it right now) be realy awesome to use in C++, too, for example for futures etc,

I wonder if there is a way to implement an interface, or a base class, to enforce a correct overload of the functions bind and return (of cause with another name than return for C++) for derived types?

To make more clear what I am thinking of:

consider we have the following non member function:

auto foo(const int x) const -> std::string;

And a member function bar which has different overloads in for different classes:

auto bar() const -> const *Monad<int>;

If we now want to do something like this: foo(someMember.bar()), this simply doesnt work. So if have to know what bar returns, and for example if it returns a future<int>, we have to call bar().get(), which blocks, even if we dont need to block here.

In haskell we could do something like bar >>= foo

So I am asking myself if we could achieve such a behaviour in C++, because when calling foo(x) we dont care if x is a object which boxes an int, and in what kind of class the int is boxed, we just want to apply function foo on the boxed type.

I am sorry I have some problem formulating my thoughts in english, since I am not a native speaker.

Answer 1

First note that being a monad is not a property of a type, but of a type constructor.

E.g. in Haskell you'd have List a as a type and List as the type constructor. In C++ we have the same functionality with templates: std::list is a type constructor that can construct the type std::list<int>. Here List is a monad, but List Bool is not.

In order for a type constructor M to be monadic it needs to supply two special functions:

1. A function that lifts arbitrary values of some type T to the monad, i.e. a function of type T -> M<T>. This function is called return in Haskell.
2. A function (in Haskell called bind) of the type M<T> ->(T -> M<T'>) -> M<T'>, i.e. a function that takes an object of type M<T> and a function of type T -> M<T'> and applies the argument function to the T objects wrapped inside the argument M<T>.

There are also some properties that these two functions have to fulfill, but since semantic properties cannot be checked at compile time (neither in Haskell nor in C++), we don't really need to care about them here.

What we can check however is the existence and types of these two functions once we decided on a syntax/names for them. For the first one, the obvious choice is a constructor that takes exactly one element of any given type T. For the second one I decided to go with operator>>= since I wanted it to be an operator in order to avoid nested function calls and it is similar to the Haskell notation (but unfortunately it is right-associative - oh well).

Checking the monadic interface

So how does one check properties of a template? Luckily there are template-template arguments and SFINAE in C++.

First, we need a way to figure out if there actually is a constructor that takes an arbitrary type. We can approximate that by checking that for a given type constructor M the type M<DummyType> is well formed for a dummy type struct DummyType{}; we define. This way we can make sure that there cannot be a specialization for the type we're checking against.

For bind we do the same thing: Check that there is an operator>>=(M<DummyType> const&, M<DummyType2>(*)(DummyType)) and that the returned type is actually M<DummyType2>.

Checking that a function exists can be done using C++17s std::void_t (I highly recommend Walter Browns talk at CppCon 2014 where he introduces the technique). Checking that the types are correct can be done with std::is_same.

All together this can look something like this:

// declare the two dummy types we need for detecting constructor and bind
struct DummyType{};
struct DummyType2{};

// returns the return type of the constructor call with a single 
// object of type T if such a constructor exists and nothing 
// otherwise. Here `Monad` is a fixed type constructor.
template <template<typename, typename...> class Monad, typename T>
using constructor_return_t
    = decltype(Monad<T>{std::declval<T>()});

// returns the return type of operator>>=(const Monad<T>&, Monad<T'>(*)(T))
// if such an operator is defined and nothing otherwise. Here Monad 
// is a fixed type constructor and T and funcType are arbitrary types.
template <template <typename, typename...> class Monad, typename T, typename T'>
using monadic_bind_t
    = decltype(std::declval<Monad<T> const&>() >>= std::declval<Monad<T'>(*)(T)>());

// logical 'and' for std::true_type and it's children
template <typename, typename, typename = void>
struct type_and : std::false_type{};
template<typename T, typename T2>
struct type_and<T, T2, std::enable_if_t<std::is_base_of<std::true_type, T>::value && std::is_base_of<std::true_type, T2>::value>> 
    : std::true_type{};


// the actual check that our type constructor indeed satisfies our concept
template <template <typename, typename...> class, typename = void>
struct is_monad : std::false_type {};

template <template <typename, typename...> class Monad>
struct is_monad<Monad, 
                void_t<constructor_return_t<Monad, DummyType>,
                       monadic_bind_t<Monad, DummyType, DummyType2>>>
    : type_and<std::is_same<monadic_bind_t<Monad, DummyType, DummyType2>,
                            Monad<DummyType2>>,
               std::is_same<constructor_return_t<Monad, DummyType>,
                            Monad<DummyType>>> {};

Note that even though we generally expect the type constructor to take a single type T as an argument, I've used a variadic template template parameter to account for default allocators typically used in STL containers. Without that you couldn't make std::vector a monad in the sense of the concept defined above.

Using the type trait to implement generic functions based on the monadic interface

The great advantage of monads is that there are quite a lot of things one can do with only the monadic interface. For example we know that every monad is also an applicative, so we can write Haskell's ap function and use it to implement liftM that allows to apply any ordinary function to a monadic value.

// ap
template <template <typename, typename...> class Monad, typename T, typename funcType>
auto ap(const Monad<funcType>& wrappedFn, const Monad<T>& x) {
    static_assert(is_monad<Monad>{}(), "");
    return wrappedFn >>= [x] (auto&& x1) { return x >>= [x1 = std::forward<decltype(x1)>(x1)] (auto&& x2) {
        return Monad<decltype(std::declval<funcType>()(std::declval<T>()))> { x1 (std::forward<decltype(x2)>(x2)) }; }; };
}

// convenience function to lift arbitrary values into the monad, i.e.
// just a wrapper for the constructor that takes a single argument.
template <template <typename, typename...> class Monad, typename T>
Monad<std::remove_const_t<std::remove_reference_t<T>>> pure(T&& val) {
    static_assert(is_monad<Monad>{}(), "");
    return Monad<std::remove_const_t<std::remove_reference_t<T>>> { std::forward<decltype(val)>(val) };
}

// liftM
template <template <typename, typename...> class Monad, typename funcType>
auto liftM(funcType&& f) {
    static_assert(is_monad<Monad>{}(), "");
    return [_f = std::forward<decltype(f)>(f)] (auto x) {
        return ap(pure<Monad>(_f), x);
    };
}

// fmap
template <template <typename, typename...> class Monad, typename T, typename funcType>
auto fmap(funcType&& f, Monad<T> const& x) {
    static_assert(is_monad<Monad>{}(), "");
    return x >>= ( [_f = std::forward<funcType>(f)] (const T& val) {
        return Monad<decltype(_f(std::declval<T>()))> {_f(val)}; });
}

Let's see how we can use it, assuming that you already implemented operator>>= for std::vector and optional.

// functor similar to std::plus<>, etc.
template <typename T = void>
struct square {
    auto operator()(T&& x) {
        return x * std::forward<decltype(x)>(x);
    }   
};

template <>
struct square<void> {
    template <typename T>
    auto operator()(T&& x) const {
        return x * std::forward<decltype(x)>(x);
    }
};

int main(int, char**) {
    auto vector_empty = std::vector<double>{};
    auto vector_with_values = std::vector<int>{2, 3, 31};
    auto optional_with_value = optional<double>{42.0};
    auto optional_empty = optional<int>{};

    auto v1 = liftM<std::vector>(square<>{})(vector_empty); // still an empty vector
    auto v2 = liftM<std::vector>(square<>{})(vector_with_values); // == vector<int>{4, 9, 961};
    auto o1 = liftM<optional>(square<>{})(optional_empty); // still an empty optional
    auto o2 = liftM<optional>(square<>{})(optional_with_value); // == optional<int>{1764.0};

    std::cout << std::boolalpha << is_monad<std::vector>::value << std::endl; // prints true
    std::cout << std::boolalpha << is_monad<std::list>::value << std::endl; // prints false

}

Limitations

While this allows for a generic way to define the concept of a monad and makes for straightforward implementations of monadic type constructors, there are some drawbacks.

First and foremost, I'm not aware that there is a way to have the compiler deduce which type constructor was used to create a templated type, i.e. there is no way that I know of to have to compiler figure out that the std::vector template has been used to create the type std::vector<int>. Therefore you have to manually add the name of the type constructor in the call to an implementation of e.g. fmap.

Secondly, it is quite ugly to write functions that work on generic monads, as you can see with ap and liftM. On the other hand, these have to be written only once. On top of that the whole approach will become alot easier to write and to use once we get concepts (hopefully in C++2x).

Last but not least, in the form I've written it down here, most of the advantages of Haskell's monads are not usable, since they rely heavily on currying. E.g. in this implementation you can only map functions over monads that take exactly one argument. On my github you can find a version that also has currying support, but the syntax is even worse.

And for the interested, here is a coliru.

EDIT: I just noticed that I was wrong regarding the fact that the compiler can not deduce Monad = std::vector and T = int when supplied an argument of type std::vector<int>. This means that you really can have a unified syntax for mapping a function over an arbitrary container with fmap, i.e.

auto v3 = fmap(square<>{}, v2);
auto o3 = fmap(square<>{}, o2);

compiles and does the right thing.

I added the example to the coliru.

EDIT: Using concepts

Since C++20's concepts are right around the corner, and the syntax is pretty much final, it makes sense to update this reply with equivalent code that uses concepts.

The simplest thing you can do to make this work with concepts is to write a concept that wraps the is_monad type trait.

template<template<typename, typename...> typename T>
concept monad = is_monad<T>::value;

Though, it could also be written as a concept by itself, which makes it a bit clearer.

template<template<typename, typename...> typename Monad>
concept monad = requires {
    std::is_same_v<monadic_bind_t<Monad, DummyType, DummyType2>, Monad<DummyType2>>;
    std::is_same_v<constructor_return_t<Monad, DummyType>, Monad<DummyType>>;
};

Another neat thing this allows us to do is cleaning up the signature of the generic monad functions above, like so:

// fmap
template <monad Monad, typename T, typename funcType>
auto fmap(funcType&& f, Monad<T> const& x) {
    return x >>= ( [_f = std::forward<funcType>(f)] (const T& val) {
        return Monad<decltype(_f(std::declval<T>()))> {_f(val)}; });
}

Answer 2

I fear that Haskell-style polymorphism and C++ templates are too far to pragmatically define monads in C++, in a way that it is actually usable.

Technically, you might define a monad M to be a template class of the following form (I'll be passing everything by value to keep it simple)

template <typename A>
struct M {
   // ...

   // this provides return :: a -> M a
   M(A a) { .... }

   // this provides (>>=) :: M a -> (a -> M b) -> M b
   template <typename B>
   M<B> bind(std::function< M<B> (A) > f) { ... }

   // this provides flip fmap :: M a -> (a -> b) -> M b
   template <typename B>
   M<B> map(std::function< B (A) > f) { ... }
};

This might work (I'm no C++ expert), but I'm unsure about whether it is usable in C++. Surely it would lead to non idiomatic code.

Then, your question is about how to require that a class has such interface. You could use something like

template <typename A>
struct M : public Monad<M, A> {
...
};

where

template <template <typename T> M, typename A>
class Monad {
   // this provides return :: a -> M a
   Monad(A a) = 0;

   // this provides (>>=) :: M a -> (a -> M b) -> M b
   template <typename B>
   M<B> bind(std::function< M<B> (A) > f) = 0;

   // this provides flip fmap :: M a -> (a -> b) -> M b
   template <typename B>
   M<B> map(std::function< B (A) > f) = 0;

};

But, alas,

monads.cpp:31:44: error: templates may not be ‘virtual’
   M<B> bind(std::function< M<B> (A) > f) = 0;

Templates look similar to polymorphic functions, but they are a different thing.

---

New approach, which seems to work, but it does not:

template <template <typename T> typename M, typename A>
class Monad {
  // this provides return :: a -> M a
  Monad(A a) = 0;

  // this provides (>>=) :: M a -> (a -> M b) -> M b
  template <typename B>
  M<B> bind(std::function< M<B> (A) > f);

  // this provides flip fmap :: M a -> (a -> b) -> M b
  template <typename B>
  M<B> map(std::function< B (A) > f);

};

// The identity monad, as a basic case
template <typename A>
struct M : public Monad<M, A> {
  A x;
  // ...

  // this provides return :: a -> M a
  M(A a) : x(a) { }

  // this provides (>>=) :: M a -> (a -> M b) -> M b
  template <typename B>
  M<B> bind(std::function< M<B> (A) > f) {
    return f(x);
  }

  // this provides flip fmap :: M a -> (a -> b) -> M b
  template <typename B>
  M<B> map(std::function< B (A) > f) {
      return M(f(x));
  }
};

However, removing, say map, from the M type does not trigger a type error. Indeed, errors will only be generated at instantiation time. Templates are not foralls, again.