Java tagged union / sum types

Make Either an abstract class with no fields and only one constructor (private, no-args, empty) and nest your "data constructors" (left and right static factory methods) inside the class so that they can see the private constructor but nothing else can, effectively sealing the type.

Use an abstract method either to simulate exhaustive pattern matching, overriding appropriately in the concrete types returned by the static factory methods. Implement convenience methods (like fromLeft, fromRight, bimap, first, second) in terms of either.

import java.util.Optional;
import java.util.function.Function;

public abstract class Either<A, B> {
    private Either() {}

    public abstract <C> C either(Function<? super A, ? extends C> left,
                                 Function<? super B, ? extends C> right);

    public static <A, B> Either<A, B> left(A value) {
        return new Either<A, B>() {
            @Override
            public <C> C either(Function<? super A, ? extends C> left,
                                Function<? super B, ? extends C> right) {
                return left.apply(value);
            }
        };
    }

    public static <A, B> Either<A, B> right(B value) {
        return new Either<A, B>() {
            @Override
            public <C> C either(Function<? super A, ? extends C> left,
                                Function<? super B, ? extends C> right) {
                return right.apply(value);
            }
        };
    }

    public Optional<A> fromLeft() {
        return this.either(Optional::of, value -> Optional.empty());
    }
}

Pleasant and safe! No way to screw it up. Because the type is effectively sealed, you can rest assured that there will only ever be two cases, and every operation ultimately must be defined in terms of the either method, which forces the caller to handle both of those cases.

Regarding the problem you had trying to do class Left<L> extends Either<L,?>, consider the signature <A, B> Either<A, B> left(A value). The type parameter B doesn't appear in the parameter list. So, given a value of some type A, you can get an Either<A, B> for any type B.

A standard way of encoding sum types is Boehm–Berarducci encoding (often referred to by the name of its cousin, Church encoding) which represents an algebraic data type as its eliminator, i.e., a function that does pattern-matching. In Haskell:

left :: a -> (a -> r) -> (b -> r) -> r
left x l _ = l x

right :: b -> (a -> r) -> (b -> r) -> r
right x _ r = r x

match :: (a -> r) -> (b -> r) -> ((a -> r) -> (b -> r) -> r) -> r
match l r k = k l r

-- Or, with a type synonym for convenience:

type Either a b r = (a -> r) -> (b -> r) -> r

left :: a -> Either a b r
right :: b -> Either a b r
match :: (a -> r) -> (b -> r) -> Either a b r -> r

In Java this would look like a visitor:

public interface Either<A, B> {
    <R> R match(Function<A, R> left, Function<B, R> right);
}

public final class Left<A, B> implements Either<A, B> {

    private final A value;

    public Left(A value) {
        this.value = value;
    }

    public <R> R match(Function<A, R> left, Function<B, R> right) {
        return left.apply(value);
    }

}

public final class Right<A, B> implements Either<A, B> {

    private final B value;

    public Right(B value) {
        this.value = value;
    }

    public <R> R match(Function<A, R> left, Function<B, R> right) {
        return right.apply(value);
    }

}

Example usage:

Either<Integer, String> result = new Left<Integer, String>(42);
String message = result.match(
  errorCode -> "Error: " + errorCode.toString(),
  successMessage -> successMessage);

For convenience, you can make a factory for creating Left and Right values without having to mention the type parameters each time; you can also add a version of match that accepts Consumer<A> left, Consumer<B> right instead of Function<A, R> left, Function<B, R> right if you want the option of pattern-matching without producing a result.

Alright, so the inheritance solution is definitely the most promising. The thing we would like to do is class Left<L> extends Either<L, ?>, which we unfortunately cannot do because of Java's generic rules. However, if we make the concessions that the type of Left or Right must encode the "alternate" possibility, we can do this.

public class Left<L, R> extends Either<L, R>`

Now, we would like to be able to convert Left<Integer, A> to Left<Integer, B>, since it doesn't actually use that second type parameter. We can define a method to do this conversion internally, thus encoding that freedom into the type system.

public <R1> Left<L, R1> phantom() {
  return new Left<L, R1>(contents);
}

Complete example:

public class EitherTest {

  public abstract static class Either<L, R> {}

  public static class Left<L, R> extends Either<L, R> {

    private L contents;

    public Left(L x) {
      contents = x;
    }

    public <R1> Left<L, R1> phantom() {
      return new Left<L, R1>(contents);
    }

  }

  public static class Right<L, R> extends Either<L, R> {

    private R contents;

    public Right(R x) {
      contents = x;
    }

    public <L1> Right<L1, R> phantom() {
      return new Right<L1, R>(contents);
    }

  }

}

Of course, you'll want to add some functions for actually accessing the contents, and for checking whether a value is Left or Right so you don't have to sprinkle instanceof and explicit casts everywhere, but this should be enough to get started, at the very least.