Sum types in C++

user_390636 0
Viewed 2437

At work, I ran into a situation where the best type to describe the result returned from a function would be std::variant<uint64_t, uint64_t> - of course, this isn't valid C++, because you can't have two variants of the same type. I could represent this as a std::pair<bool, uint64_t>, or where the first element of the pair is an enum, but this is a special case; a std::variant<uint64_t, uint64_t, bool> isn't so neatly representable, and my functional programming background really made me want Either - so I went to try to implement it, using the Visitor pattern as I have been able to do in other languages without native support for sum types:

template <typename A, typename B, typename C>
class EitherVisitor {
    virtual C onLeft(const A& left) = 0;
    virtual C onRight(const B& right) = 0;
};

template <typename A, typename B>
class Either {
    template <typename C>
    virtual C Accept(EitherVisitor<A, B, C> visitor) = 0;
};

template <typename A, typename B>
class Left: Either<A, B> {
private:
    A value;
public:
    Left(const A& valueIn): value(valueIn) {}

    template <typename C>
    virtual C Accept(EitherVisitor<A, B, C> visitor) {
        return visitor.onLeft(value);
    }
};

template <typename A, typename B>
class Right: Either<A, B> {
private:
    B value;
public:
    Right(const B& valueIn): value(valueIn) {}
    
    template <typename C>
    virtual C Accept(EitherVisitor<A, B, C> visitor) {
        return visitor.onRight(value);
    }
};

C++ rejects this, because the template method Accept cannot be virtual. Is there a workaround to this limitation, that would allow me to correctly represent the fundamental sum type in terms of its f-algebra and catamorphism?

strong-typedef variant virtual-functions templates c++
2 Answers

Perhaps the simplest solution is a lightweight wrapper around T for Right and Left? Basically a strong type alias (could also use Boost's strong typedef)

template<class T>
struct Left
{
    T val;
};

template<class T>
struct Right
{
    T val;
};

And then we can distinguish between them for visitation:

template<class T, class U>
using Either = std::variant<Left<T>, Right<U>>;

Either<int, int> TrySomething()
{
    if (rand() % 2 == 0) // get off my case about rand(), I know it's bad
        return Left<int>{0};
    else
        return Right<int>{0};
}

struct visitor
{
    template<class T>
    void operator()(const Left<T>& val_wrapper)
    {
        std::cout << "Success! Value is: " << val_wrapper.val << std::endl;
    }
    
    template<class T>
    void operator()(const Right<T>& val_wrapper)
    {
        std::cout << "Failure! Value is: " << val_wrapper.val << std::endl;
    }
};

int main()
{
    visitor v;
    for (size_t i = 0; i < 10; ++i)
    {
        auto res = TrySomething();
        std::visit(v, res);
    }
}

Demo

user_276780

std::variant<X,X> is valid C++.

It is a bit awkward to use, because std::visit doesn't give you the index, and std::get<X> won't work either.

The way you can work around this is to create a variant-of-indexes, which is like a strong enum.

template<std::size_t i>
using index_t = std::integral_constant<std::size_t, i>;

template<std::size_t i>
constexpr index_t<i> index = {};

template<std::size_t...Is>
using number = std::variant< index_t<Is>... >;

namespace helpers {
  template<class X>
  struct number_helper;
  template<std::size_t...Is>
  struct number_helper<std::index_sequence<Is...>> {
    using type=number<Is...>;
  };
}
template<std::size_t N>
using alternative = typename helpers::number_helper<std::make_index_sequence<N>>::type;

we can then extract the alternative from a variant:

namespace helpers {
  template<class...Ts, std::size_t...Is, class R=alternative<sizeof...(Ts)>>
  constexpr R get_alternative( std::variant<Ts...> const& v, std::index_sequence<Is...> ) {
    constexpr R retvals[] = {
      R(index<Is>)...
    };
    return retvals[v.index()];
  }
}
template<class...Ts>
constexpr alternative<sizeof...(Ts)> get_alternative( std::variant<Ts...> const& v )
{
  return helpers::get_alternative(v, std::make_index_sequence<sizeof...(Ts)>{});
}

so now you have a std::variant<int, int>, you can

auto which = get_alternative( var );

and which is a variant, represented at runtime by an integer which is the index of the active type in var. You can:

std::variant<int, int> var( std::in_place_index_t<1>{}, 7 );

auto which = get_alternative( var );

std::visit( [&var](auto I) {
  std::cout << std::get<I>(var) << "\n";
}, get_alternative(var) );

and get access to which of the alternative possibilities in var is active with a compile time constant.

The get_alternative(variant), I find, makes variant<X,X,X> much more usable, and fills in the hole I think you might be running into.

Live example.

Now if you don't need a compile-time index of which one is active, you can just call var.index(), and visit via visit( lambda, var ).

When you construct the variant, you do need the compile time index to do a variant<int, int> var( std::in_place_index_t<0>{}, 7 ). The wording is a bit awkward, because while C++ supports variants of multiples of the same type, it considers them a bit less likely than a "standard" disjoint variant outside of generic code.

But I've used this alternative and get_alternative like code to support functional programming like data glue code before.

user_17746670
Related