Is it possible to construct an Either in Java that allows flatMap to return a different Left value?

Question

I'm trying to understand how Either is implemented. I've gotten stuck at chaining together multiple functions in a way that allows returning a different Left value during flatMap. I can't work out how it is possible within the type system.

Minimal Either example code:

public class Either<A,B> {
    public final A left;
    public final B right;

    private Either(A a, B b) {
        left = a;
        right = b;
    }

    public static <A, B> Either<A, B> left(A a) {
        return new Either<>(a, null);
    }


    public static <A, B> Either<A, B> right(B b) {
        return new Either<>(null, b);
    }


    public <C> Either<A, C> flatMap(Function<B, Either<A,C>> f) {
        if (this.isRight()) return f.apply(this.right);
        else return Either.left(this.left);
    }

    // map and other useful functions....

I originally thought I'd be able to map to different Left values, which would allow returning the relevant error at each point.

So, for instance, given these functions:

public static Either<Foo, String> doThing() {
        return Either.right("foo");
}

public static Either<Bar, String> doThing2(String text) {
    return (text.equals("foo")) 
        ? Either.right("Yay!") 
        : Either.left(new Bar("Grr..."));
}

public static Either<Baz, String> doThing3() {
    return (text.equals("Yay!")) 
        ? Either.right("Hooray!") 
        : Either.left(new Baz("Oh no!!"));
}

I thought I'd be able to do

doThing().flatMap(x -> doThing2()).flatMap(y -> doThing3())

However, the compiler flags this as impossible.

After some studying of the code, I realized that it's due to my <A,B> generic parameters.

flatMap has two different cases:

1. the case where we map the right side
2. the case where we pass through the left value

So, if my goal is to enable sometimes returning different Left values from flatMap, then my two generic variables <A,B> don't work, because if case 1 executes and my function changes A, then case 2 is invalid, because A != A'. The act of applying a function to the right side may have changed the Left side to a different type.

All this leads me to these questions:

1. Is my expectation for the behavior of the Either type incorrect?
2. Is it possible to return different Left types during a flatMap operation?
3. if so, how do you get the types to work out?

Answer 1

Regarding your usage of Either (doThing(...)) it seems your flat mapping isn't sufficient. I assume you want your flat mapping work like for Optional<T>.

The mapper ofOptional.flatMap takes a value of kind of T and returns an Optional<U> where U is a generic type parameter of this method. But Optional has one generic type parameter T whereas Either has two: A and B. So if you want to flat map an Either<A,B> either it isn't sufficient to use one mapping.

One mapping what should it map? "The value which isn't null" you would say - wouldn't you? Ok but you know that first at runtime. Your flatMap method is defined at compile time. Therefore you have to provide a mapping for each case.

You choose <C> Either<A, C> flatMap(Function<B, Either<A, C>> f). This mapping uses a value of type B as input. That means if the mapped Either either is !either.isRight() all following mappings would return an Either.left(a) where a is the value of the very first Either.left(a). So actually only an Either either where either.isRight() could be mapped to another value. And it has to be either.isRight() from the beginning. This means also that once an Either<A,B> either is created all flat mappings will result in a kind of Either<A,?>. So the current flatMap restricts an Either either to keep its left generic type. Is this what you supposed to do?

If you want to flat map an Either either without restrictions you need mappings for both cases: either.isRight() and !either.isRight(). This will allow you to continue the flat mapping in both directions.

I did it this way:

public class Either<A, B> {
    public final A left;
    public final B right;

    private Either(A a, B b) {
        left = a;
        right = b;
    }

    public boolean isRight() {
        return right != null;
    }

    @Override
    public String toString() {
        return isRight() ?
                right.toString() :
                left.toString();
    }

    public static <A, B> Either<A, B> left(A a) {
        return new Either<>(a, null);
    }

    public static <A, B> Either<A, B> right(B b) {
        return new Either<>(null, b);
    }

    public <C, D> Either<C, D> flatMap(Function<A, Either<C, D>> toLeft, Function<B, Either<C, D>> toRight) {
        if (this.isRight()) {
            return toRight.apply(this.right);
        } else {
            return toLeft.apply(this.left);
        }
    }

    public static void main(String[] args) {
        Either<String, String> left = Either.left(new Foo("left"))
                .flatMap(l -> Either.right(new Bar(l.toString() + ".right")), r -> Either.left(new Baz(r.toString() + ".left")))
                .flatMap(l -> Either.left(l.toString() + ".left"), r -> Either.right(r.toString() + ".right"));
        System.out.println(left); // left.right.right

        Either<String, String> right = Either.right(new Foo("right"))
                .flatMap(l -> Either.right(new Bar(l.toString() + ".right")), r -> Either.left(new Baz(r.toString() + ".left")))
                .flatMap(l -> Either.left(l.toString() + ".left"), r -> Either.right(r.toString() + ".right"))
                .flatMap(l -> Either.right(l.toString() + ".right"), r -> Either.left(r.toString() + ".left"));
        System.out.println(right); // right.left.left.right
    }

    private static class Foo {
        private String s;

        public Foo(String s) {
            this.s = s;
        }

        @Override
        public String toString() {
            return s;
        }
    }

    private static class Bar {
        private String s;

        public Bar(String s) {
            this.s = s;
        }

        @Override
        public String toString() {
            return s;
        }
    }

    private static class Baz {
        private String s;

        public Baz(String s) {
            this.s = s;
        }

        @Override
        public String toString() {
            return s;
        }
    }
}

Answering your question: Yes it is possible to construct an Either returning a different left value. But I think your intent was to know how to get a proper working Either.

Answer 2

You can, but your old Left has to be a subtype of or equal to the new Left, so it can be cast up. I'm not very familiar with Java's syntax, but the Scala implementation looks like:

def flatMap[A1 >: A, B1](f: B => Either[A1, B1]): Either[A1, B1] = this match {
  case Right(b) => f(b)
  case _        => this.asInstanceOf[Either[A1, B1]]
}

Here the A1 >: A designates A as a subtype of A1. I know Java has an <A extends A1> syntax, but I'm not sure it can be used to describe the constraint on A1, as we need in this case.

Answer 3

There isn't a sensible flatMap() function like you want, due to parametricity. Consider:

Either<Foo, String> e1 = Either.left(new Foo());
Either<Bar, String> e2 = foo.flatMap(x -> doThing2());
Bar bar = e2.left; // Where did this come from???

flatMap() itself would have had to invent a Bar instance somehow. If you start writing a flatMap() that can change both types, you'll see the issue more clearly:

public <C, D> Either<C, D> flatMap(Function<B, Either<C, D>> f) {
    if (this.isRight()) {
        return f.apply(this.right);
    } else {
        // Error: can't convert A to C
        return Either.left(this.left);
    }
}