C++ Concepts: Can I define a concept that is itself a template?

Question

Sorry if the question isn't too clear. I'm not sure the best way to phrase it (feel free to edit!). I think an example would be the most clear:

I am attempting to define a Monad concept based off of the Haskell definition. The bind operator (>>=) requires that a Monad of type A can be bound to a function that takes an A and returns a Monad of type B. I can define A in terms of a value_type typedef but how do I define type B in my concept?

template <typename M>
concept bool Monad()
{
  return requires(M m, Function<_1, ValueType<M>> f) {
    // (>>=) :: m a -> (a -> m b) -> m b
    { m >>= f } -> M
  }
}

In the above example, what do I put in place of the _1 in the Function<> concept?

Also does this sufficiently constrain the result of invoking f to be a Monad of any type?

Answer 1

I think the closest you may be able to do is to provide a specific function that is A --> Monad<B> and verify that it does the right thing. In an effort to prevent infinite recursion, we can just verify that A --> M works:

template <class M>
concept bool Monad()
{
    return requires(M m) {
        { m >>= std::function<M(ValueType<M>)>{} } -> M;
    };
}

This is only one specific case, but I don't believe it is possible to verify the general case that A --> Monad<X> works, since the concepts checks still involve specific expressions and you can only create specific expressions with specific types.

Of course, we can provide multiple such requirements. With a rebind metafunction:

template <class M, class X>
struct rebind;

template <class M, class X>
using rebind_t = typename rebind<M, X>::type;

template <template <class...> class Z, class R, class X>
struct rebind<Z<R>, X> {
    using type = Z<X>;
};

We can then add requirements for functions returning various types, say that it also works for ints:

template <class M>
concept bool Monad()
{
    return requires(M m)
    {
        { m >>= std::function<M(ValueType<M>)>{} } -> M;
        { m >>= std::function<rebind_t<M,int>(ValueType<M>)>{} } -> rebind_t<M,int>;
    };
}

which might get easier by refactoring that into its own sub-concept:

template <class M, class R>
concept bool MonadBind()
{
    return requires(M m) {
        { m >>= std::function<rebind_t<M,R>(ValueType<M>)>{} } -> rebind_t<M,R>;
    };
}

template <class M>
concept bool Monad()
{
    return requires(M m) {
        requires MonadBind<M, ValueType<M>>();
        requires MonadBind<M, int>();
    };
}