Templated requires-expression

Question

I want a Functor concept in C++20.

A functor is a higher-kinded type that can be mapped over. A simple example is std::optional; with a function from type A to type B and a std::optional<A>, you can easily create a std::optional<B> by applying the function to the value if it exists and returning an empty optional otherwise. This operation is called fmap in Haskell.

template<typename A, typename B>
std::optional<B> fmap(std::function<B(A)> f, std::optional<A> fa) {
    if (!fa) {
        return std::optional<B>{};
    }
    return std::optional<B>(f(*fa));
}

A concept for all functors is simple enough to write. I've come up with this (using GCC—you'll have to remove bool to get this working in Clang, I think):

template<template<typename> typename F, typename A, typename B>
concept bool Functor = requires(std::function<B(A)> f, F<A> fa) {
    { fmap(f, fa) } -> F<B>;
};

And a simple additional function to make sure this works:

template<typename A, typename B>
std::function<B(A)> constant(B b) {
    return [b](A _) { return b; };
}

template<template<typename> typename F, typename A, typename B>
F<B> replace(B b, F<A> fa) requires Functor<F,A,B> {
    return fmap(constant<A,B>(b), fa);
}

It works. But it's not pretty. What I want is for the signature of replace to read like so:

template<Functor F, typename A, typename B>
F<B> replace(B b, F<A> fa);

No need for a requires-clause here. Much nicer, don't you agree? To get this to work, however, I'd have to reduce the template on my concept to a single argument. Something like this:

template<template<typename> typename F>
concept bool Functor = requires(function<B(A)> f, F<A> fa) {    // Uh-oh
    { fmap(f, fa) } -> F<B>;
};

Problem is, I've not declared types A and B. As far as I can tell, there's nowhere I can declare them before I have to use them. Can what I want be done, and can it be done simply and elegantly?

One possible solution that comes to my mind is to make the requires-expression in the concept a template (or at least a template-like thing). I'd then have something like this:

template<template<typename> typename F>
concept bool Functor = requires<typename A, typename B>(function<B(A)> f, F<A> fa) {
    { fmap(f, fa) } -> F<B>;
};

Unfortunately, this is not valid by the C++20 standard and will not compile with g++-8. Could something like this be viable? Could it make it into the standard?

Answer 1

C++ doesn't have parametric polymorphism like this - you can't do things like "for any type" in the way you want to, and in the way you can in Haskell. I think that's fundamentally impossible in a world where overloading exists.

What you have is the following (I went ahead and removed the erroneous bool, which isn't part of C++20 concepts, and fixed -> Type, which was also removed):

template<template<typename> class F, typename A, typename B>
concept Functor = requires(std::function<B(A)> f, F<A> fa) {
    { fmap(f, fa) } -> std::same_as<F<B>>;
};

What you want to say is for any types a and b, given an a -> b, you can call this function. We can't do that. But we can just pick arbitrary types ourselves. One way of doing that is to pick secret types that the functor implementation just wouldn't know about:

namespace secret {
    struct A { };
    struct B { };

    template <typename From, typename To>
    struct F {
        auto operator()(From) const -> To;
    };
}

template <template <typename> class F>
concept Functor = requires(secret::F<secret::A, secret::B> f, F<secret::A> fa) {
    { fmap(f, fa) } -> std::same_as<F<secret::B>>;
};

That's probably your best bet. You could even add multiple a/b pairs to make this more likely to be correct.

Regardless, this:

template<Functor F, typename A, typename B>
F<B> replace(B b, F<A> fa);

Isn't going to happen anyway, since we don't have that kind of terse syntax for constrained template template parameters. You'd have to write it this way:

template <template <typename> class F, typename A, typename B>
    requires Functor<F>
F<B> replace(B b, F<A> fa);

---

As a side note, this is a bad implementation of fmap for optional:

template<typename A, typename B>
std::optional<B> fmap(std::function<B(A)> f, std::optional<A> fa);

Taking a std::function<Sig> means this will only work if you pass in specifically a std::function. Not for lambdas or function pointers or other function objects (like the secret::F I used earlier). And even if it did work, you wouldn't want to do this anyway, since it's needless overhead.

You want:

template <typename F, typename A, typename B = std::invoke_result_t<F&, A const&>>
std::optional<B> fmap(F f, std::optional<A> fa);

I have a whole post about this exact problem, Declarations Using Concepts.

Answer 2

Your "Functor" concept represents a complex relationship between three different types: F (a one-parameter template that is the template being projected over), A (the starting object type), and B (the resulting object type). Your concept represents a relationship between 3 parameters, so your concept is going to have to take 3 parameters.

Terse template syntax is for simple cases: constraints relating to a single (type) parameter. Your case is not simple, so you're going to have to spell it out with a requires clause. Anytime you have a concept with multiple parameters like this, you'll have to spell it out.

As for whether it is "pretty" or not, that's a value judgement. But given the complex relationship on display here, seeing it spelled out makes it clear what the relationship between all of these parameters is. And clarity has a beauty all its own.