title: Is it possible to construct an Either in Java that allows flatMap to return a different Left value?
body: <p>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 <code>Left</code> value during <code>flatMap</code>. I can't work out how it is possible within the type system. </p>
  
  <p>Minimal Either example code: </p>
  
  <pre><code>public class Either&lt;A,B&gt; {
      public final A left;
      public final B right;
  
      private Either(A a, B b) {
          left = a;
          right = b;
      }
  
      public static &lt;A, B&gt; Either&lt;A, B&gt; left(A a) {
          return new Either&lt;&gt;(a, null);
      }
  
  
      public static &lt;A, B&gt; Either&lt;A, B&gt; right(B b) {
          return new Either&lt;&gt;(null, b);
      }
  
  
      public &lt;C&gt; Either&lt;A, C&gt; flatMap(Function&lt;B, Either&lt;A,C&gt;&gt; f) {
          if (this.isRight()) return f.apply(this.right);
          else return Either.left(this.left);
      }
  
      // map and other useful functions....
  </code></pre>
  
  <p>I originally thought I'd be able to map to different Left values, which would allow returning the relevant error at each point. </p>
  
  <p>So, for instance, given these functions: </p>
  
  <pre><code>public static Either&lt;Foo, String&gt; doThing() {
          return Either.right("foo");
  }
  
  public static Either&lt;Bar, String&gt; doThing2(String text) {
      return (text.equals("foo")) 
          ? Either.right("Yay!") 
          : Either.left(new Bar("Grr..."));
  }
  
  public static Either&lt;Baz, String&gt; doThing3() {
      return (text.equals("Yay!")) 
          ? Either.right("Hooray!") 
          : Either.left(new Baz("Oh no!!"));
  }
  </code></pre>
  
  <p>I thought I'd be able to do </p>
  
  <pre><code>doThing().flatMap(x -&gt; doThing2()).flatMap(y -&gt; doThing3())
  </code></pre>
  
  <p>However, the compiler flags this as impossible. </p>
  
  <p>After some studying of the code, I realized that it's due to my <code>&lt;A,B&gt;</code> generic parameters. </p>
  
  <p>flatMap has two different cases: </p>
  
  <ol>
  <li>the case where we map the right side</li>
  <li>the case where we pass through the left value </li>
  </ol>
  
  <p>So, if my goal is to enable sometimes returning different Left values from flatMap, then my two generic variables <code>&lt;A,B&gt;</code> don't work, because if case 1 executes and my function changes <code>A</code>, then case 2 is invalid, because <code>A</code> != <code>A'</code>. The act of applying a function to the right side may have changed the Left side to a different type. </p>
  
  <p>All this leads me to these questions: </p>
  
  <ol>
  <li>Is my expectation for the behavior of the Either type incorrect? </li>
  <li>Is it possible to return different <code>Left</code> types during a flatMap operation? </li>
  <li>if so, how do you get the types to work out? </li>
  </ol>