# Functions of Variants are Covariant

Contents

Today I am happy to present a guest post by Alfredo Correa about covariant visitors for `std::variant`. Alfredo works at Lawrence Livermore National Laboratory where he uses C++ to develop physics simulations tools.

# Introduction

Sum types have a range of values that is the sum of the ranges of its parts. `std::variant` is the model representation of sum types in C++.

For example `std::variant` can hold an integer value (`int` state) or a double value (`double` state). The use of variant types provides support for polymorphism while maintaining value semantics.

There are only a few intrinsic functions that can be applied directly to an `std::variant` instance in C++; basically, only functions that probe or extract their current type state and value. Simple C++ functions over its component states cannot be applied directly to the variant since the type information needs to be probed before calling the corresponding function over the correct type.

Specific C++ functions can be applied through visitors. However, standard visitors are static and non-covariant, stopping polymorphism from propagating through function application.

A basic explanation of variants and their visitors can be found here.

# (Non-covariant) Functions

The free function `std::visit` defines a protocol that can be used to apply a corresponding concrete function from a set of overloads or cases. The concrete functions are grouped as a visitor function. A visitor over a variant type is a callable object that is overloaded or can be applied to all the states of the variant.

## Visitor class

The prototypical visitor class has several overloads of `operator()`.

``````struct print_visitor {
std::ostream& operator()(int a){
return std::cout << "(int)" << a;
}
std::ostream& operator()(double a){
return std::cout << "(double)" << a;
}
};

std::variant<double, int> v = 3.14;
std::visit(print_visitor{}, v); // prints "(double)3.14"
``````

The overload can include template functions which can exploit common syntax within the variant set.

## On-the-fly visitors

If the function is generic enough and can be used on all the possible variant types, the auxiliary function can be replaced by a single lambda and called on-the-fly:

``````std::visit([](auto const& e)->std::ostream&{return std::cout << e;}, v) << '\n';
``````

If a single generic lambda is incapable of handling all the cases, a set of lambdas can be grouped automatically by an overload object. `std::overload` is a proposed addition to the standard library but can be implemented easily:

``````template <class ...Fs>
struct overload : Fs... {
template <class ...Ts>
overload(Ts&& ...ts) : Fs{std::forward<Ts>(ts)}...
{}
using Fs::operator()...;
};
template <class ...Ts>
``````

Visitors can be applied to multiple arguments as well. A basic description of on-the-fly visitors can be found here.

## Scope and Restrictions

The free function `std::visit` and the visitor define a function that can be applied over a variant set.

For a visitor to be valid, it needs to overload all the possible cases of the variant, either by overload resolution, template instantiation or implicit type conversion. Each overload is in principle independent (although it probably makes sense that they all implement a common conceptual operation) but all the overloads have to return a common type. This common return type makes the functions that be applied non-covariant.

For example this is not a valid visitor for `std::variant`, because the return type is not common to all cases (`int` and `double`).

``````// invalid visitor, (what type is d?)
auto d = std::visit([](auto n){ return n + 1; }, std::variant<int, double>(3.14));
``````

# Co-variant functions

A covariant function is one in which the runtime case of the return type varies with the case of the input type(s). Covariant functions are a special case of overloads that return a single variant type based on the concrete return types of the overload functions.

The example above is not a valid visitor and therefore it cannot be applied directly to a variant. However, it can be converted into a valid visitor and therefore also a covariant function by manually predict the possible states of the result and wrap the result into a common variant.

``````auto next = [](auto n)->std::variant<int, double>{ return n + 1; };
auto d = std::visit(next, std::variant<int, double>(3.14));
assert( std::get<double>(d) = 3.14 + 1.0 );
``````

In this case, the possible output types of the overload set are `int` and `double`, therefore the type of `d` is `std::variant`.

The problem with this approach is that it doesn’t scale well for more complicated cases; one has to manually keep track of the possible return types of the overload and enforce the variant return type. If the overload is more complicated, it may become harder to account for all the result types. Besides, it is not clear how to handle the special `void` case. For example:

``````auto next_overload = overload(
[](int a)->std::variant<int, double, void??>{ return a + 1; },
[](double a)->std::variant<int, double, void??>{ return a + 1; },
[](char)->std::variant<int, double, void??>{ return int(0); },
[](std::string)->std::variant<int, double, void??>{}
)
``````

Note that the possible number of return types of the overload is equal to or smaller than the original variant states. If the function takes more than one (variant) argument the number of possible output state multiplies.

Additionally, since `void` is not a regular type, a variant containing a `void` type is invalid. Therefore, overloads that return `void` should be handled separately. A possible design choice is to map the `void` return to a special `monostate`, which effectively behaves like a regular `void`.

## Automatic covariant return type deduction

Given an overload set (or callable function) `Overload` and a list of input types `ListInput`, in principle, it is possible to deduce the set of all the possible return types `ResultSet` from all the possible inputs and later construct a variant `Out` for it.

This is, of course, something that can be computed at the time of compilation, for example with a (meta)function `result_set_of`:

``````using Result = results_of_set_t<Overload, ListInput>;
``````

where `ListInput` is extracted from a variant type:

``````using ListInput = variant_types_list_t<std::variant<...>>;
``````

From the set of results a new variant type can be made:

``````using new_variant = variant_of_set_t<Result>;
``````

## Implementation

This type deduction requires a certain degree of metaprogramming. Different techniques can be used to implement the type deduction above.

Here we use the Boost Metaprogramming Library, Boost.MPL. The code is not particularly obvious but is simple from the perspective of functional programming:

``````namespace bmp = boost::mpl;

template<class, class> struct variant_push_back;
template<class... Vs, class T>
struct variant_push_back<std::variant<Vs...>, T> {
using type = std::variant<
std::conditional_t<
std::is_same<T, void>::value
, std::monostate
, T
>,
Vs...
>;
};

template<class Set>
using variant_of_set_t =
typename bmp::fold<
Set,
std::variant<>,
variant_push_back<bmp::_1, bmp::_2>
>::type;
;
``````
``````template<class F, class T>
struct apply {
using type = decltype(std::declval<F>()(std::declval<T>()));
};
template<class O, class Seq>
using results_of_set_t =
typename bmp::fold<
typename bmp::transform_view<
Seq,
apply<O, bmp::_1>
>::type,
bmp::set<>,
bmp::insert<bmp::_1, bmp::_2>
>::type
;
``````
``````template<class T> struct variant_types_list
template<class... Ts>
struct variant_types_list<std::variant<Ts...>> {
using type = bmp::list<Ts...>;
};
template<class T> using variant_types_list_t = typename variant_types_list<T>::type;
``````

Once we are past this metaprogramming interlude, it is relatively straightforward to define a `covariant` wrapper class that generalizes the concept of an overload in order to produce a covariant function. Note that the main complication is to handle the `void` return case.

``````template<class... Fs>
struct covariant : overload<Fs...> {
covariant(Fs... fs) : overload<Fs...>(fs...) {}
template<class... Ts, typename = decltype(overload<Fs...>::operator()(std::declval<Ts>()...))>
decltype(auto) call(Ts&&... ts) const{
if constexpr(std::is_same<decltype(overload<Fs...>::operator()(std::forward<Ts>(ts)...)), void>::value) {
return std::monostate{};
} else {
}
}
template<class... Ts, class Ret = variant_of_set_t<detail::results_of_set_t<overload<Fs...> const&, variant_types_list_t<std::variant<Ts...>>>>>
Ret operator()(std::variant<Ts...> const& v) {
return std::visit([&](auto&& e)->Ret{ return call(e); }, v);
}
};

template<class... Fs> covariant(Fs... f) -> covariant<Fs...>;
``````

# Result and Conclusion

In the same way that visitors can be applied to variant types and return a single type, a covariant functions can return a new variant type.

This example function gives the next element within the current state of the variant (e.g. `double` or `int`), for a non-numeric input (`std::string`) it returns nothing (`void`) which is turned into an `std::monostate`.

``````std::variant<int, double, std::string> v = 1.2;
auto d = covariant(
[](int i){ return i + 1; },
[](double d){ return d + 1; },
[](auto const&){} // return void otherwise
)(v);
// d is of type std::variant<int, double, std::monostate>
assert( std::get<double>(d) == 1.2 + 1 );
``````

For simplicity, the covariance defined here works only with respect to a single argument.
The power of this technique is that it scales to multiple variant arguments at the cost of a slightly more elaborate metaprogramming code. The concept of a covariant function simplifies the propagation of polymorphic values through the use of functions.

The reference implementation can be found in https://gitlab.com/correaa/boost-covariant.