Exagon Exagon - 2 months ago 14
C++ Question

Monad interface in C++

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

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). Bhecking 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
    = declval(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);
    };
}

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.