Functor

In this example we want to illustrate a capability of the C++ language using concepts, namely to implement the category theory concept called functor. The closest example of implementing functors in functional programming is the one in Haskell where a functor is a data type that implements a $fmap$ function.

The definition in Haskell is:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

This definition is very elegant, but in object-oriented languages that support genericity, explaining this concept correctly is very difficult or impossible. In C++20 instead we can define the functor as a concept even if it is more difficult, it is not impossible.

namespace sayten
{
    template<typename FunctionT>
    concept FmapParameter = Callable<FunctionT> &&
    HasArgCount<FunctionT, 1> && !HasVoidReturn<FunctionT>;

    template<typename InputT, typename FunctionT>
    concept FmapRequirement = FmapParameter<FunctionT> &&
            HasArgNoCVRefType<FunctionT, InputT, 0>;

    template<template<typename> typename FunctorT>
    concept HasFmap =
    requires (FunctorT<placeholder<1>> functor)
    {
        { functor.fmap(placeholder_function<0, 1>) } -> std::convertible_to<FunctorT<placeholder<0>>>;
        { functor.fmap(placeholder_callable<0, 1>{}) } -> std::convertible_to<FunctorT<placeholder<0>>>;
    };
    
    template<template<typename> typename FunctorT>
    concept Functor = HasFmap<FunctorT>;
}

In the presented code, several concepts are defined for defining the functor concept, they further use concepts defined in our code on gitlab to have certain static reflection capabilities in code. For those who are interested, they can inspect our code for more details.

The first time we defined the concept of FmapParameter, which checks if a type is a function or an object with the call operator through the Callable concept. Then a value of that type must be able to be called with a single parameter ensuring through the HasArgCount concept and not be a poll resulting void through the HasVoidReturn concept.

namespace sayten
{
    template<typename FunctionT>
    concept FmapParameter = Callable<FunctionT> &&
    HasArgCount<FunctionT, 1> && !HasVoidReturn<FunctionT>;
}

note

Any object that has the call operator can be called as a function by default which is nothing more than a non-static method. This operator can be implemented by any structure or class in C++ and is used behind the scenes by the compiler to implement lambada functions which are nothing but objects with the anonymous type and with this operator implemented. Also, std::function classes have this operator. It should be remembered that when creating a lambda function, an object is actually created that can also have a constructor. For example, a lambda [&x](int a) -> int { return a + x; } will have a constructor with a parameter of type from capture (capture). Like any non-static method, the call operator will have the first hidden parameter to represents the reference to this.

Next we define the concept of FmapRequirement where we test if for a given input type a function type can be called with it with HasArgNoCVRefType and of course first testing that the type can be a callable type. This concept will be used for functor implementations, not for the definition of the functor concept.

namespace sayten
{
    template<typename InputT, typename FunctionT>
    concept FmapRequirement = FmapParameter<FunctionT> &&
            HasArgNoCVRefType<FunctionT, InputT, 0>;
}

namespace sayten
{
    template<template<typename> typename FunctorT>
    concept HasFmap =
    requires (FunctorT<placeholder<1>> functor)
    {
        { functor.fmap(placeholder_function<0, 1>) } -> std::convertible_to<FunctorT<placeholder<0>>>;
        { functor.fmap(placeholder_callable<0, 1>{}) } -> std::convertible_to<FunctorT<placeholder<0>>>;
    };
}

The Functor concept is defined, not on a type, but on a template. The reason is that the function must, on the one hand, map the data types to the template instances, something that happens automatically, but on the other hand, map all the functions between them.

Thus the Functor concept is synonymous with HasFmap in which it is tested on placeholder types if the fmap method respects without additional assumptions the same signature as in Haskell, which ensures that the fmap method will act for all its courts. Basically, we are trying to have an equivalent for the forall keyword in Haskell.

For the present case, we set the condition that for a call of the fmap method, either on a function or on an object that can be called, an instance of the given function should be produced for us, or at least convertible to it. The reason why I left code with std::convertible_to and not with std::same_as is that there are situations in which anonymous types are returned, such as lambada functions that can be converted to std:: function.

namespace sayten
{
    template<template<typename> typename FunctorT>
    concept HasFmap =
    requires (FunctorT<placeholder<1>> functor)
    {
        { functor.fmap(placeholder_function<0, 1>) } -> std::convertible_to<FunctorT<placeholder<0>>>;
        { functor.fmap(placeholder_callable<0, 1>{}) } -> std::convertible_to<FunctorT<placeholder<0>>>;
    };
    
    template<template<typename> typename FunctorT>
    concept Functor = HasFmap<FunctorT>;
}

To elucidate what our placeholder types look like, these are just some structures without content that we only use to test the requirements from the concepts.

namespace sayten
{
    template<size_t>
    struct placeholder
    {
        std::strong_ordering operator<=>(const placeholder&) const
        {
            return std::strong_ordering::equal;
        }

        bool operator==(const placeholder&) const
        {
            return true;
        }
    };

    template<size_t result, size_t ...args>
    struct placeholder_callable
    {
        std::strong_ordering operator<=>(const placeholder_callable&) const
        {
            return std::strong_ordering::equal;
        }

        bool operator==(const placeholder_callable&) const
        {
            return true;
        }

        placeholder<result> operator()(const placeholder<args>&...) const
        {
            return placeholder<result>{};
        }
    };

    template<size_t result, size_t ...args>
    placeholder<result> placeholder_function(const placeholder<args>&...)
    {
        return placeholder<result>{};
    }
}

Because we have defined the Functor concept, we can test it on a classic functor, the identity functor described here:

namespace sayten
{
    template<typename ValueT>
    class identity
    {
    private:
        ValueT value;

    public:
        template<typename OtherValueT>
        friend class identity;

        identity() = delete;
        constexpr identity(const ValueT &value) : value(value) {}
        constexpr identity &operator=(const identity &) = default;

        constexpr identity(const identity &other) : value(other.value) {}

        template<typename MapFunctionT>
        requires FmapRequirement<ValueT, MapFunctionT>
        constexpr identity<typename unwrap_function<MapFunctionT>::result_type> fmap(const MapFunctionT &map_function) const
        {
            return identity<typename unwrap_function<MapFunctionT>::result_type>(map_function(value));
        }
    };
}

I didn't define anything more than the basic requirements for fmap, I didn't even use inheritance or implement an interface like in other languages to get an approximation of a functor. At the most, I used static relection to put the corresponding signature for fmap.

Thus, if we test the concept at compile time:

int main()
{
    if constexpr (Functor<identity>)
    {
        std:cout << "Template identity is a functor\r\n";
    }
    else
    {
        std:cout << "Template identity is not a functor\r\n";
    }
 
    return 0;
}

We will get after the equivalent code:

int main()
{
    std:cout << "Template identity is a functor\r\n";
 
    return 0;
}