Either monad in C++11

Question

I'm using C++11 with https://github.com/SmingHub/Sming. It has no support of std lib or exceptions. I wanted to use Either monad to return an error or result from my functions. I implemented it using class hierarchy. I'm not a native C++ dev so I would be glad for the code review.

#pragma once

template <class L, class R> 
class Either
{
    virtual bool isLeft();
    virtual bool isRight();

    virtual bool matchLeft(L& x);
    virtual bool matchRight(R& x);
};

template <class L, class R> 
class Left : public Either<L, R> {
public:
    L left;

    Left(L left): left(left) {}
    constexpr bool isLeft() { return true; }
    constexpr bool isRight() { return false; }

    bool matchLeft(L& x)
    {
        x = left;
        return true;
    }
    bool matchRight(R& x) { return false; }
};

template <class L, class R> 
class Right : public Either<L, R> {
public:
    R right;

    Right(R right): right(right) {}
    constexpr bool isLeft() { return false; }
    constexpr bool isRight() { return true; }

    bool matchLeft(L& x) { return false; }

    bool matchRight(R& x) {
        x = right;
        return true;
    }
};

Answer 1

This class is conceptually flawed because the only way to extract the values from it is by (copy) assignment. This makes it less useful than we'd like:

Either<err_type, res_type> *result = some_function(); // notice the pointer; more on this later
if(result->isLeft()) {
    some_type error; // what if there's no obvious and cheap way to create an "empty" object of this type?
                     // why do I have to state the type again?
    result->matchLeft(error); // what if there is no copy assignment operator= on some_type (e.g. it holds some exclusive resource)?
                              // what if the copy assignment is expensive (e.g. it's a container)?
                              // why is this not an expression?
    std::cerr << error << "\n"; // or however you're doing output
} else {
    other_type value;
    result->matchRight(value);
    std::cout << value << "\n";
}
delete result; // argh!

We can take a page out of the standard library's book (std::get_if) and make matchLeft and matchRight into getIfLeft and getIfRight, which return nullable pointers.

template<class L, class R> 
struct Either // note that all of these members are private; you either need to add public: or replace class with struct
{
    // without const, these can't be called on const Eithers
    virtual bool isLeft() const = 0; // can actually be implemented in terms of getIfLeft, so doesn't really need to be virtual at all
    virtual bool isRight() const = 0; // otherwise, I think you need to make these all *pure* virtual, or else you'll get linker errors

    virtual L *getIfLeft() = 0;
    virtual R *getIfRight() = 0;
    // we'd also want const Either -> pointer to const versions, because these functions currently can't be called on const Eithers

    virtual ~Either() = default; // very, VERY severe omission! deleting an Either through a pointer without this is UB!
};

*result->getIfLeft() is now an lvlaue of type L. The caller no longer has to construct a dummy object or restate the type, and the L no longer needs to be copy-assigned, and we need many fewer lines. Note that we've basically just reinvented dynamic_cast.

Either<some_type, other_type> *result = some_function();

// now shorter, more to the point
if(result->isLeft()) std::cerr << *result->getIfLeft() << "\n";
else std::cout << *result->getIfRight() << "\n";
// also acceptable
if(auto error = result->getIfLeft()) std::cerr << *error << "\n";
else if(auto value = result->getIfRight()) std::cout << *value << "\n";

delete result;

The other issue is using virtual inheritance for this in the first place. That means the only way to use this class is through pointers, probably with dynamic allocation, which is easy to get wrong (I forgot to write the deletes in this answer at first; you forgot to make the destructor virtual; some_function above probably has to to contain a new, so we probably should delete it, but maybe some_function returns a pointer to some preallocated memory that it reuses, or maybe it does something else, so it's hard to automatically know how to handle the memory...). A more direct way to do this is the classic (old as C) "tagged union".

std::variant is a general purpose tagged union, but it doesn't exist in C++11 and you say you don't even have the STL available. Implementing a pared down version involves a union, which is interesting to handle properly, but the point is that the end result acts like "just a value" and doesn't require the user code to know how to manage memory.

// you say you don't have the std namespace available
// if you really don't have std::move or std::forward, just write them yourself
enum class either_side { left, right };
struct left_tag_t {}; struct right_tag_t {};
template<class L, class R>
class either {
    // self explanatory
    either_side tag;
    union {
        L left;
        R right;
    };

    public:
    // "in-place" constructors: according to the tag, initialize with whatever arguments
    template<class... U>
    either(left_tag_t, U&&... args) : tag(either_side::left), left(std::forward<U>(args)...) { }
    template<class... U>
    either(right_tag_t, U&&... args) : tag(either_side::right), right(std::forward<U>(args)...) { }
    // may want std::initializer_list "forwarding" constructors, too

    // initialize by type
    either(L x) : either(left_tag_t(), std::move(x)) { }
    either(R x) : either(right_tag_t(), std::move(x)) { }

    // sometimes we don't know which variant member to initialize immediately
    // so we leave the union uninitialized and then placement-new into it
    either(either const &other) : tag(other.tag) {
       if(tag == either_side::left) new(&left) L(other.left);
       else new(&right) R(other.right);
    }
    either(either &&other) : tag(other.tag) {
       if(tag == either_side::left) new(&left) L(std::move(other.left));
       else new(&right) R(std::move(other.right));
    }
    // and when we need to destroy the object, we must explicitly call the destructor
    either &operator=(either const &other) {
       if(tag == either_side::left && other.tag == either_side::left) left = other.left;
       else if(tag == either_side::right && other.tag == either_side::right) right = other.right;
       else if(tag == either_side::left && other.tag == either_side::right) {
           left.~L();
           // NOT exception safe! if this constructor were to throw and ~either to be called during the unwinding
           // then ~either would see the tag set but neither object constructed
           // and would try to destroy it a second time
           // ...but you say we don't have exceptions, so I suppose we can be sloppy (the standard library's solution is to add a third tag meaning "empty because of exception" to std::variant)
           new(&right) R(other.right);
       } else {
           right.~R();
           new(&left) L(other.left);
       }
       tag = other.tag;
    }
    either &operator=(either &&other) {
       if(tag == either_side::left && other.tag == either_side::left) left = std::move(other.left);
       else if(tag == either_side::right && other.tag == either_side::right) right = std::move(other.right);
       else if(tag == either_side::left && other.tag == either_side::right) {
           left.~L();
           new(&right) R(std::move(other.right));
       } else {
           right.~R();
           new(&left) L(std::move(other.left));
       }
       tag = other.tag;
    }
    ~either() {
        if(tag == either_side::left) left.~L();
        else right.~R();
    }

    L *get_if_left() { return tag == either_side::left ? &left : nullptr; }
    L const *get_if_left() const { return tag == either_side::left ? &left : nullptr; }
    R *get_if_right() { return tag == either_side::right ? &right : nullptr; }
    R const *get_if_right() const { return tag == either_side::right ? &right : nullptr; }
    bool is_left() const { return bool(get_if_left()); }
    bool is_right() const { return bool(get_if_right()); }
};
// hopefully, all that's correct (emphasis on the hopefully)

Ta-da!

// all uses of std:: definitions are for demonstrative purposes
struct user_session {
    std::string user_name;
    long user_id;
    long session_id;
    std::fstream data_file; // or whatever you're using
    user_session(std::string user_name, long user_id, long session_id, std::fstream data_file)
    : user_name(std::move(user_name)), user_id(user_id), session_id(session_id), data_file(std::move(data_file))
    { }
};

either<std::string, user_session> acquire_session(long user_id) {
    std::stringstream builder;
    builder << "User" << user_id;
    std::string name = builder.str();
    if(std::rand() & 1) return {left_tag_t(), "Computer says no"};
    try {
        std::fstream data(name);
        return {right_tag_t(), std::move(name), user_id, std::rand(), std::move(data)};
    } catch(...) {
        return {left_tag_t(), "IO error"};
    }
    // no wacky allocations for either
}
int main() {
    auto result = acquire_session(std::rand());
    if(auto *error = result.get_if_left()) {
        std::cerr << *error << "\n";
        return EXIT_FAILURE;
    }
    std::cout << result.get_if_right()->user_name << "\n";
    // either is correctly destroyed automatically
}

Answer 2

Your Either-monad suffers from a fatal flaw:

It is impossible to return an Either which might be either possibility.

You can only return a Left or a Right, an Either must per force be a pointer or reference to one of those.

Without help from the compiler in automatically deducing a return-type of Either<T, U> if it finds returns of a combination of Either<T, U>, Left<T> and Right<U> sufficient to deduce T and U, or at least adding pattern-matching, Left and Right are pretty much useless.

In the end, that just leaves Either, which is now only a poor-mans substitute for full-fledged std::variant of two.