Add error-handling methods to `EitherT`

[alexandru]

Addresses #2161 by adding redeem and redeemWith to MonadError.

These are derived by attempt.map and attempt.flatMap respectively:

trait MonadError[F[_], E] {
  // ...

  def redeem[A, B](fa: F[A])(recover: E => B, map: A => B): F[B] =
    redeemWith(fa)(recover.andThen(pure), map.andThen(pure))

  def redeemWith[A, B](fa: F[A])(recover: E => F[B], bind: A => F[B]): F[B] =
    flatMap(attempt(fa))(_.fold(recover, bind))
}

As mentioned in #2161, this represents an optimization on usage of attempt because for certain datatypes (e.g. IO, Task, Future):

1. it avoids the Either boxing
2. and even more importantly, it avoids a second map / flatMap operation

The benchmark results in that issue speak for themselves and note that I've measured IO / Task, which have fairly efficient map and flatMap operations. For a data type like Future working with attempt for error recovery is a disaster.

My use-case for redeem / redeemWith is in monix.tail.Iterant that now makes heavy use of attempt for error recovery. This is a streaming abstraction, so attempt.flatMap operations can pile up and add quite significant overhead.

---

Given that we have Future instances provided by Cats, it would have been a shame to not also provide optimized redeemWith and attempt operations — because a new, abstract Future#transformWith has been introduced in Scala 2.12 as the base function for all other operations (e.g.flatMap, recoverWith).

The difficulty here is to keep compatibility with Scala 2.11- so this commit introduces FutureShims provided with different implementations for different Scala versions. Compatibility is thus maintained even with Scala 2.10.

---

I also went ahead and enhanced EitherT with the following operations, straight on the class definition itself:

• widen
• leftWiden
• attempt
• attemptF
• handleError
• handleErrorF
• handleErrorWith
• handleErrorWithF
• recoverF
• recoverWith
• recoverWithF
• redeem
• redeemF
• redeemWith
• redeemWithF

So given EitherT[F, A, B], the functions suffixed with F operate on any F: MonadError[F, E] in scope, thus recovering from E errors thrown in the F[_] context.

Two reasons for it:

1. the F suffixed methods are provided because working with the provided MonadError[EitherT[F, L, ?], E] instance sucks (see #2029)
2. the call sites are too heavy for such common operations, so relying on implicit conversions to provide the necessary syntax creates short-term junk
3. discovery of features for new users is better this way

On performance, the JVM is able to do some limited escape analysis to avoid short-term allocations in certain situations and the garbage collector is usually good at dealing with short-term junk, but irregardless, the JVM has a limited budget for optimizations and the way to think about it is that obvious optimizations at some call sites detract from doing obvious optimizations at other call-sites.

---

In order to optimize memory allocations and the byte-code of those functions, I've rewritten some of them to do more explicit pattern matching, with a default cast _ => branch.

Benchmarks are a marketing scheme and an implementation that's easier on memory and possibly performance beats an implementation that's elegant. Libraries don't have to be elegant, libraries have to be efficient such that the user's code can be elegant.

Have also written ScalaDocs — which triggered the Scalastyle check for "maximum file size", which I had to disable completely, since it makes no sense to have a restriction that discourages the writing of ScalaDocs.

---

Unfortunately using a provided MonadError[EitherT[F, L, ?], E] that's explicitly imported in scope no longer works for those functions.

E.g. this sample will trigger an error, hence that particular test is now gone:

test("#2022 EitherT syntax no long works the old way") {
  import data._

  EitherT.right[String](Option(1)).handleErrorWith((_: String) => EitherT.pure(2))
  {
    implicit val me = MonadError[EitherT[Option, String, ?], Unit]
    // Triggers compile-time error!
    EitherT.right[String](Option(1)).handleErrorWith((_: Unit) => EitherT.pure(2))
  }
}

This is one reason for why I don't like type-class driven syntax. Such overloads should not be possible or desirable, being much worse than Java-driven overloads which I also prefer to avoid.

Another argument for doing this is that the previous implementation had inconsistent definitions for recover and recoverWith straight on the case class definition, but not for handleError and handleErrorWith. So you could do the above for handleError, but not for recover.

This means that this PR has a source incompatibility with 1.0.0, but this is not a binary incompatibility 😉 and is in my opinion a valid fix.

---

We've got the following incompatibilities:

// Internal classes, moved due to refactoring, not a problem
exclude[MissingClassProblem]("cats.syntax.EitherUtil$"),
exclude[MissingClassProblem]("cats.syntax.EitherUtil"),
// Scala 2.11 only — internal classes, not a problem
exclude[ReversedMissingMethodProblem]("cats.data.EitherTMonadErrorF.redeem"),
exclude[ReversedMissingMethodProblem]("cats.data.EitherTMonadErrorF.redeemWith"),
exclude[ReversedMissingMethodProblem]("cats.data.EitherTMonadErrorF.handleError"),
exclude[ReversedMissingMethodProblem]("cats.data.EitherTMonadErrorF.attempt"),
exclude[ReversedMissingMethodProblem]("cats.data.EitherTMonadError.redeem"),
exclude[ReversedMissingMethodProblem]("cats.data.EitherTMonadError.redeemWith"),
// BREAKAGE — Scala 2.11 only!
exclude[ReversedMissingMethodProblem]("cats.MonadError.redeem"),
exclude[ReversedMissingMethodProblem]("cats.MonadError.redeemWith")

Don't know what the current binary compatibility policy is, but due to adding methods with default implementations on traits, these are not backward compatible on Scala 2.11, because it targets Java 7, which doesn't support interfaces with "default implementations".

Scala 2.12 doesn't have such problems though.

But I'm guessing that due to this change, such a PR can only target Cats 2.0, is that correct?

[codecov-io]

Codecov Report

Merging #2237 into master will decrease coverage by 0.07%. The diff coverage is 90.69%.

@@            Coverage Diff             @@
##           master    #2237      +/-   ##
==========================================
- Coverage   95.05%   94.98%   -0.08%     
==========================================
  Files         333      336       +3     
  Lines        5789     5846      +57     
  Branches      211      218       +7     
==========================================
+ Hits         5503     5553      +50     
- Misses        286      293       +7

Impacted Files	Coverage Δ
core/src/main/scala/cats/syntax/either.scala	99.15% <ø> (-0.02%)	:arrow_down:
.../main/scala-2.12+/cats/internals/FutureShims.scala	0% <0%> (ø)
.../main/scala-2.11-/cats/internals/FutureShims.scala	0% <0%> (ø)
...ore/src/main/scala/cats/internals/EitherUtil.scala	100% <100%> (ø)
core/src/main/scala/cats/instances/option.scala	100% <100%> (ø)	:arrow_up:
core/src/main/scala/cats/MonadError.scala	100% <100%> (ø)	:arrow_up:
core/src/main/scala/cats/data/Ior.scala	98.48% <100%> (ø)	:arrow_up:
core/src/main/scala/cats/ApplicativeError.scala	100% <100%> (ø)	:arrow_up:
core/src/main/scala/cats/instances/either.scala	100% <100%> (ø)	:arrow_up:
...n/scala/cats/laws/discipline/MonadErrorTests.scala	100% <100%> (ø)	:arrow_up:
... and 8 more

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update ef05c76...ecdc544. Read the comment docs.

[LukaJCB]

We could add redeem and redeemWith add syntax on the SyntaxBinCompat trait :)

[alexandru]

@LukaJCB

We could add redeem and redeemWith add syntax on the SyntaxBinCompat trait :)

Not sure what you mean, I see there is a AllSyntaxBinCompat0, don't know what the purpose is.

@johnynek

I renamed upcastL to leftWiden and upcastR to widen. That naming is unfortunate tbh, because the technical term is upcasting. It explains for example why I had no idea they existed. But being consistent is more important.

[alexandru]

@johnynek actually I removed widen / leftWiden, as I don't want to defend adding those on the class itself 🙂 Their existence on Functor / Bifunctor is good enough.

[LukaJCB]

Sorry about the lack of depth on my last comment, was on mobile and on a train. We can create some MonadErrorExtraOps trait put the two functions there and then create another AllSyntaxBinCompat1 trait just like the one here. Then we can mix those into the AllSyntaxBinCompat trait as well as the object implicits found here. That should give everyone the ability to use these methods whenever they import all syntax.

When cats 2.0 comes around, we can then move them into their respective type classes :)

[alexandru]

@LukaJCB that's cool, but the syntax isn't the problem solved here — redeemWith isn't much of an improvement over .attempt.flatMap.

The real win is the ability to override redeemWith.

Related: https://github.com/typelevel/cats-effect/pull/191

[alexandru]

Actually I want to think about this more, given Cats 2.0's timeline I think that's OK, we've got time. Closing it to prevent merging or PR creep, will reopen if the case.

[alexandru]

OK, sorry for reopening it — I've carefully considered possibilities, doing benchmarks with alternatives, like a variant that takes a function with an Either[Throwable, A] parameter, plus I modified some Monix code to see how it feels like and I think this approach is the best.

The signature is nice too, it's basically a fold (catamorphism?) that happens in the F[_] context.

[joan38]

Is this PR scheduled to go in for 2.0? If yes can we add the label?

[alexandru]

Is this PR scheduled to go in for 2.0?

I hope so 🙂

[joan38]

Great! @kailuowang could you add the 2.0 label please ? 😄

[joan38]

Hey @kailuowang @alexandru, Did we forget to merge this for the 2.0 release? Is it still time?

[kailuowang]

We didn't forget. Our release plan changed. The original 2.0 release is going to be 2.1, the 2.0 release we are preparing now is different and doesn't allow PRs that break binary compat on Scala 2.11 like this one.

[travisbrown]

Removing this from the 2.1.0-RC1 milestone in favor of the subset in #3146. I do think we should aim to get the EitherT enhancements merged at some point, so I don't think we should close it yet.