Exagon - 1 year ago 113

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`

`return`

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`

`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>`

`bar().get()`

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)`

`int`

`int`

`foo`

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

Answer Source

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:

- 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. - 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).

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.

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
}
```

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.