data.Xor and instances/either.scala: Either is now right-biased

[soc]

Either has become right-biased in Scala 2.12, so I think it would make sense to

• check whether instances/either.scala can be cleaned up/stream-lined
• consider whether keeping Xor has benefits that are greater than converging on a single Either implementation in the Scala ecosystem

[adelbertc]

I like removing Xor and XorT in favor of Either (stdlib) and EitherT (a rename of XorT). Since Either will be right-biased starting in Scala 2.12, with libraries like Argonaut FS2 and Scodec using Either, and since we often recommend folks import cats.implicits._ anyways (so we can add methods we want via enrichment) it seems moving to Either would provide some conveniences for users. In my experience having used Scodec, one of the pain points is getting an Either and having to convert it myself. In general conversions back and forth are a pain.

I'm sure there will be some opposition so I'll wait for them to speak up :-) Otherwise if nobody complains I'll try to put a patchset together this weekend.

[mpilquist]

@adelbertc Any thoughts on 2.10/2.11 compatibility? E.g., would import cats.implicits._ patch right-biasness on to Either?

[adelbertc]

@mpilquist Yeah that's what I was thinking. Users will have to pay a penalty if they wish to stick with a la carte imports, I'm guessing via cats.syntax.either._ or something like that. Though that also opens the doors for Cats beginning to support syntax for stdlib types, something in the past we've decided not to do. But I do think the benefit of moving onto stdlib Either is something worth considering, I've always found it weird we use Option, List, etc but have our own Either.

It also makes for some funny explanations when I say "Cats sticks with stdlib types when possible... oh except for Either..." And when encouraging folks to use Either in lieu of Try or just throwing I constantly find myself saying "I would use Either... except Either isn't really good because it's unbiased... Cats has Xor... but now you have to bring in a whole dependency just to get Either." While that's more an issue of the Scala stdlib, it'd be nice if in the future I could say use Either, and bring in Cats to get even more goodies with it versus you could use Either now... and switch to cats.data.Xor in the future maybe?

Also if simple right-biased monadic Either is what people want, we already have the instance. Importing syntax then gets us what we're after:

scala> val e0: Either[String, Int] = Right(5)
e0: Either[String,Int] = Right(5)

scala> val e1: Either[String, Int] = Left("boo")
e1: Either[String,Int] = Left(boo)

scala> for {
     |   a <- e0
     |   b <- e1
     | } yield b
<console>:15: error: value flatMap is not a member of Either[String,Int]
         a <- e0
              ^
<console>:16: error: value map is not a member of Either[String,Int]
         b <- e1
              ^

scala> import cats.implicits._
import cats.implicits._

scala> for {
     |   a <- e0
     |   b <- e1
     | } yield b
res1: scala.util.Either[String,Int] = Left(boo)

[adelbertc]

Oo I also just realized you can do (possibly immoral) tricks like this:

import scala.util.{Either => SEither}

package object foo {
  implicit class Either[A, B](val either: SEither[A, B]) extends AnyVal {
    def map[C](f: B => C): SEither[A, C] = either match {
      case Left(a)  => Left(a)
      case Right(b) => Right(f(b))
    }
  }
}

// in REPL

scala> val e: Either[String, Int] = Right(5)
e: Either[String,Int] = Right(5)

scala> e.map(_ + 1)
<console>:13: error: value map is not a member of Either[String,Int]
       e.map(_ + 1)
         ^

scala> import foo.Either
import foo.Either

scala> e.map(_ + 1)
res1: scala.util.Either[String,Int] = Right(6)

[soc]

@mpilquist You could have a version-specific import, which would add the missing methods to Either on 2.10/2.11 and would be empty on 2.12.

[adelbertc]

So assuming nobody objects to this today I'll start work on this tomorrow. My plan:

1. Add any missing methods currently available on Xor to Either via an implicit class available under cats.syntax.either
2. Redo XorT to be centered around Either
3. Fix the compiler errors (yay types!)

[travisbrown]

I finally get to use the :-1: on GitHub! :smile:

As I said on Gitter, I'm strongly opposed to removing Xor (or replacing it with Either in the Cats API), at least until we stop supporting 2.11, and probably after.

Relying on extension methods for something as basic as flatMap on a core type like this just isn't worth whatever interop benefits we'd get by using Either everywhere. It's either more noise or more imports and magic, more bytecode, more runtime overhead, less Java-friendly, etc.

[adelbertc]

@travisbrown Is there as big of a performance difference with an implicit value class?

[travisbrown]

@adelbertc It helps in the for-comprehension case, but then you're balancing a flatMap you get directly vs. the one you get from the Monad instance and syntax, you've got different sets of imports that do the same thing but work very differently, and in general it's just a whole big awful bag of half-broken Scala magic instead of nice and simple Xor.

[soc]

@travisbrown This sounds all very unspecific to me. Are there some specific issues that you can share?

[travisbrown]

@soc For the record, here's one concrete example of that kind of prioritization issue.

[djspiewak]

Strongly in favor. Data classes like Xor, State and (to a lesser extent) Kleisli are incredibly hard to work around, compatibility wise, when you're talking in terms of middleware frameworks. fs2 is already using Either, and it seems like http4s is going to standardize on Either for broadly the same reason. Even if cats keeps Xor, there's a very real chance that no one will use it in the end.

I feel the runtime overhead of implicits needed in the short term is very manageable. I don't disagree that the prioritization issue is real if done via imports. I think the better approach would be to add the implicit to the Xor companion object. The downside is you get the slower one by default then if you import monad implicits, but the upside is that a) you don't need an import at all, and b) you never get ambiguities.

Does anyone know if members of supertypes of imported objects are at a lower priority than members of the imported object itself? Somehow I doubt that would override import ordering though. (edit they aren't at a lower priority)

[travisbrown]

@djspiewak I don't understand what you mean by the Xor companion object here, or how you could make Either behave consistently across 2.11 and 2.12 without imports.

[djspiewak]

@travisbrown Oh derp. For some reason I thought we could put the implicit magic in Xor's companion and somehow have that resolve for Either. Blame it on travel fatigue. Imports are clearly required, but I feel that's a relatively small price to pay.

[alexandru]

In my projects I already preferred Either to Xor, even before finding out that Either will be right biased in 2.12. The reason is that Either is standard and in use much more than alternatives like Xor will ever be. And this is important for interoperability and learning curve. Don't get me wrong, the right bias is cool, but using a right projection on Either is a bearable nuisance. Plus I actually miss those projections when the left value is not just some error I want to ignore. So now that Either will be right biased, I'll probably never use Xor.

That said, consider that Scala 2.11 will be around for a really long time, because 2.12 is the version that breaks compatibility with Java 6.

[adelbertc]

Since it looks like there's a bit of debate going on I'll hold off on submitting a PR (if necessary) until we reach some sort of agreement.

[rossabaker]

The commit above has an exploratory, ugly implementation of this. I won't step on @adelbertc's toes for a pull request, but the commit discusses some pros and cons in the context of a cats library that has to deal with Either anyway.

[adelbertc]

It seems the fiddly-ness with regards to getting right-biased behavior on stdlib Either is entirely on our side. Assuming we do it correctly users need not know what's going on, which I think is fine.

As for the behavior for Scala 2.1{0, 1} and Scala 2.12, it should just work right? It won't look or an implicit conversion/class unless the method is missing. In Scala 2.1{0,1} calling flatMap will trigger the conversion and in 2.12 it won't.

How do we want to move forward on this? We seem to have a lot of folks in favor, but I also want to make sure there's no strong-arming or anything happening to those opposed.

EDIT

@rossabaker and I just discovered some evilness - it seems implicit syntax does not play nice with aliases. Consider:

trait Batteries extends cats.syntax.AllSyntax with cats.std.AllInstances with P0

trait P0 {
  implicit class EitherSyntax[X, A](either: Either[X, A]) {
    def map[B](f: A => B): Either[X, B] = either match {
      case Left(x) => Left(x)
      case Right(a) => Right(f(a))
    }
  }
}

object batteries extends Batteries

object MyApp {
  import batteries._
  type Result[A] = Either[String, A]
  val e: Result[Int] = Right(5)

  e.map(_ + 1)
}

The compiler complains with:

EitherSyntax.scala:19: type mismatch;
[error]  found   : MyApp.e.type (with underlying type MyApp.Result[Int])
[error]  required: ?{def map: ?}
[error] Note that implicit conversions are not applicable because they are ambiguous:
[error]  both method toFunctorOps in trait ToFunctorOps of type [F[_], A](target: F[A])(implicit tc: cats.Functor[F])cats.Functor.Ops[F,A]
[error]  and method EitherSyntax in trait P0 of type [X, A](either: Either[X,A])batteries.EitherSyntax[X,A]
[error]  are possible conversion functions from MyApp.e.type to ?{def map: ?}
[error]   e.map(_ + 1)
[error]   ^
[error] one error found
[error] (compile:compileIncremental) Compilation failed

Adding @milessabin 's SI-2712 plugin allows the alias to work. Not aliasing at all works as well. Aliasing with a binary type constructor (e.g. type Or[A, B] = Either[A, B]) works.

If we don't have a way around this then it may spell bad news for users.

EDIT 2 I suppose the Unapply machinery could solve this

[rossabaker]

batteries is a concept to reduce branch divergence while I attempt to support http4s on two stacks for a bit. Here it is with more traditional a la carte imports (Scala 2.11.8, cats 0.6.1):

scala> object EitherSyntax { // this would be added to cats
     |   implicit class EitherOps[A, B](self: Either[A, B]) {
     |     def map[C](f: B => C) = self.fold(Left(_), b => Right(f(b)))
     |   }
     | }
defined object EitherSyntax

scala> import cats.std.either._, cats.syntax.functor._, EitherSyntax._
import cats.std.either._
import cats.syntax.functor._
import EitherSyntax._

scala> Right(5).map(_ * 2)
res0: Product with Serializable with scala.util.Either[Nothing,Int] = Right(10)

scala> type ParseResult[+A] = Either[String, A]
defined type alias ParseResult

scala> (Right(5): ParseResult[Int]).map(_ * 2)
<console>:23: error: type mismatch;
 found   : ParseResult[Int]
    (which expands to)  scala.util.Either[String,Int]
 required: ?{def map: ?}
Note that implicit conversions are not applicable because they are ambiguous:
 both method toFunctorOps in trait ToFunctorOps of type [F[_], A](target: F[A])(implicit tc: cats.Functor[F])cats.Functor.Ops[F,A]
 and method EitherOps in object EitherSyntax of type [A, B](self: Either[A,B])EitherSyntax.EitherOps[A,B]
 are possible conversion functions from ParseResult[Int] to ?{def map: ?}
       (Right(5): ParseResult[Int]).map(_ * 2)
                ^
scala> type Disjunction[+A, +B] = Either[A, B]
defined type alias Disjunction

scala> (Right(5): Disjunction[Nothing, Int]).map(_ * 2)
res3: Product with Serializable with scala.util.Either[Nothing,Int] = Right(10)

This is only going to bite people not using SI-2712, supporting Scala < 2.12, with _[_] type aliases for Either. This might be a small population, but it bit me almost immediately.

[philwills]

In general I'm all for both using stdlib types and optimising for the future, but the kind of subtle inconsistencies that @rossabaker and @travisbrown mention do make me nervous.

I wouldn't know which way to cast a vote, so I'm not sure this is a terribly helpful contribution, but I'm glad to see it getting plenty of thought.

[jonoabroad]

Keeping Xor around until 2.12 is out seems like less work for those of us relying on it.

[adelbertc]

I think if we manage to solve the _[_] alias problems (perhaps with Unapply) that covers most if not all use cases (does anyone type alias Either with 3+ type params?). How do we want to move forward with this?

[rossabaker]

Cats adoption is growing while Scala 2.11 is near its crest. More Cats apps will be written on Scala >= 2.12 than on Scala < 2.12, so I give more weight to the 2.12+ experience.

Secondly, the more Cats apps have already been written, the more expensive change becomes. The worst choice is to keep Xor now with an intent to standardize on Either later. I hope that whatever we do in cats-0.8 is still in cats-1.0 and cats-2.0.

Thirdly, I hope that Typelevel projects reach a consensus. Our projects all gain value when they interoperate with minimal friction. I am actively porting http4s to Cats, and intend to steer toward Cats' preferred disjunction, regardless of it being mine.

Standard library types need to be grossly deficient or little used to justify forfeiting their network effects. People will draw the line at different places, but Scala 2.12 brings Either back to the "not too gross" side of the line for me. I would like to see @adelbertc's take as a PR, where we can work through the tradeoffs, assure ourselves of performance, and try it on real projects to look for other lurking dragons.

[johnynek]

I am reluctantly pro-either. In most cases in cats, we have Functor or Monad instances in scope, and call methods on those. I am not a huge syntax user, so I don't care too much about not having clean access to .map/.flatMap on Either. I'd pay that price for better interop.

[adelbertc]

Our projects all gain value when they interoperate with minimal friction.

This rings the most true with me.

A couple years ago using Argonaut, Remotely, Doobie, Http4s, and Scalaz in a project was super nice, everything just clicked together and it was one of the most pleasant experiences I've had composing libraries across a variety of domains.

If everyone used Xor I think would be fine, but the reality we live in now is we have scalaz.\/, scala.util.Either, and cats.data.Xor. Libraries like Argonaut, FS2, and Scodec have chosen to use stdlib Either I'm guessing out of not wanting to re-invent yet-another-Either and not wanting to pick between Cats and Scalaz. Additionally, Scala 2.12.x is the path moving forward for everyone and it looks less terrible than it was prior to the right-bias PR.

[adelbertc]

Given the feedback in this ticket I'm going to start working on this again soon unless someone yells at me again /cc @travisbrown

[travisbrown]

@adelbertc I've resigned myself to having methods like tailRecM written in terms of Either instead of Xor, so as long as Xor isn't deprecated before 0.8 I'm okay with moving forward.

[adelbertc]

@travisbrown Sounds good :+1:

The plan:

• [ ] Change methods like tailRecM to use scala.util.Either instead of cats.data.Xor
• [ ] Copy cats.data.Xor methods into the syntax enrichment of scala.util.Either
• [ ] Copy cats.data.XorT into cats.data.EitherT but with changes to make it centered around scala.util.Either

These changes should be in the future 0.8.0 release. Note that cats.data.{Xor, XorT} will remain, but most of Cats will be centered around scala.util.Either with the expectation that libraries built around Cats do similarly. After 0.8.0 cats.data.{Xor, XorT} will be removed and all of Cats will be built on scala.util.Either - this should be in the 0.9.0 release.

[johnynek]

One interesting thing: if EitherT is an AnyVal, then EitherT[Id, A, B] should be a zero-cost enrichment to get .map/.flatMap. So, a method like def toEitherTId[A, B](e: Either[A, B]): EitherT[Id, A, B] = could be used to get .map:

for {
 b <- toEitherTId(e)
 c <- toEitherTId(fn(b))
} yield c

Not sure that is better than using e.right and fn(b).right but it should have fewer allocations.

[adelbertc]

Here ya go: https://github.com/typelevel/cats/pull/1289

[Ichoran]

How did you guys manage (or did you manage) to work around the ugliness of having two type parameters on Left/Right instead of one?

[mpilquist]

@Ichoran https://github.com/typelevel/cats/blob/v0.7.2/core/src/main/scala/cats/data/Xor.scala#L192-L193

[Ichoran]

@mpilquist - That is how Xor works, as do most of the other Either clones. But I want to know how you deal with the headache caused by the two type parameterization of scala.util.Left and scala.util.Right. If the plan is to switch away from Xor and to Either, this is something that should be considered. What is the plan to deal with that issue?

[samthebest]

I'm still stuck on 2.11 because I use EMR & Spark.

How do I get Xor now? Do I have to go back all the way to 0.8.0?

If your going to remove something, would be nice to document how to get it back somewhere. This is ungooglable!

[LukaJCB]

@samthebest you can't get it back, unless you use 0.8.0, however, you can use Either with 2.11 and cats 2.0.0, because we have implicit enrichment of it, which makes it just as fully featured as on 2.12. As for documentation, we're all just a bunch of unpaid volunteers, if you want to add something to the docs, please consider creating a PR :)