Technically you only need swap (eg:

  swap :: Either e2 (Either e1 a) -> Either e1 (Either e2 a)
  swap (Left z) = (Right (Left z))
  swap (Right (Left y)) = (Left y)
  swap (Right (Right x)) = (Right (Right x))

) to implement join (at the functor `Either e1 . Either e2`) and then a general monad-compose. You could also use:

  join :: f1 (f2 (f1 (f2 a))) -> f1 (f2 a)
  -- join = fmap join . join . fmap swap -- if you have swap

directly, which doesn't even require f1 and f2 to be monads in the first place (though they do need to be applicative for return/pure/unit). (See http://web.cecs.pdx.edu/~mpj/pubs/RR-1004.pdf for technical details.)

swap is generally trivial (see above) for any sane error-reporting monad, although might be a bit more difficult if you're shoving error-handling logic into them.

IMO the solution is to either:

* Use return values and let people deal with the boilerplate ala Optional in java. We use Optionals to replace null values and IMO the boilerplate is 100% worth it. I've also used return values that can encode possible errors in Java.

* Use unchecked exceptions and expect people to understand the methods they call and the exceptions those methods can throw, which should be documented in javadoc instead of a throws clause. This needs to happen regardless, as methods can throws unchecked exceptions the caller might need to be aware of, so this in reality doesn't involve extra work.

For me, either of these solutions is preferrable to checked exceptions.