Gather, list, contact interested parties for an Either/Or/Xor/Validation etc SLIP and possible expert group

[dickwall]

Either has been the subject of multiple improvement suggestions in the past. Or, Xor and validation come up a lot in related (possibly more expansive) discussions.

Changing the nature of Either, or introducing new library types and defining their relationship to Either, is likely to be a big task. Multiple interested parties and suggestions are listed below.

We need a volunteer to start contacting the parties, gauge their interest and ask for a commitment to be involved in defining a SLIP proposal for this.

I would also like to record my own suggestion (strictly a suggestion) that perhaps the problem is broken into more than one phase, e.g. a quick fixup to increase the value of Either (maybe implicit bias or similar) in the short term, and a longer term SLIP around the whole area of Validation, etc. which would also defined the inter-relationships.

Links to existing material and known interested parties will be listed in a comment below.

[SethTisue]

Rob Dickens's proposal for the optional implicits to bias the existing Either is here: https://github.com/scala/scala.github.com/pull/100

[dickwall]

Deliverable from this issue should be another (or multiple) next steps in terms of new github issues.

That may be dependent on scope or scopes of differing projects.

Can we fix up Either as it is now, is the scope much larger like a new module in the core libs?

[soc]

I would be interested in participating in an expert group.

In my opinion, the first thing to do would be to make the desired changes to Either and then discuss how the gap between what we have and what we want can be bridged.

I'm against introducing a new name or type, because it will cause long-term confusion, and I prefer having to pay the price once instead of having to tell people "if you want an Either, ignore Either and use X instead" indefinitely.

I'm also sceptic about having optional implicits except as a migration route: Those who want an Either and currently implement their own will probably consider an "Either with optional implicits" not good enough, and keep shipping their own thing.

[Ichoran]

I'm also interested in participating. I've written about four Either-clones so far, so I've had a good chance to test out various things (e.g. do the equivalents of Left and Right keep track of the type of the other option or not)?

The problem with changing the nature of Either is that there is more than one use case for a sum type. The two primary ones are (1) Validation / error reporting, with one type being "good" and the other "bad" (2) A genuinely unbiased sum type, where two different but equivalent options are possible.

Either as it stands is pretty good at (2) and not very good at (1). The problem with using things that are really good at (1) for (2) is that when you need to operate on the "other" type, you have to flip your logic upside-down (i.e. e.map(foo) vs. e.swap.map(foo).swap). Because swapping is memoryless, it's easy to lose track of it and get the two values confused.

Because of this, in my own code I now use Either for sum types and my own variant ("Okay" with "Yes" and "No" subtypes) for validation.

I also think that implicit bias for Either is a good first quick step and has relatively few downsides. But I don't think this is the final solution either, due to the inherent tension I mention above.

If anyone can show a clean way to do both things well, that would be great. So far I've tried and failed four times. (Well, more like two and a half; some of the other implementations were actually meant to replace Option[Either[A,B]] with a single class.)

--Rex

On Mon, Aug 17, 2015 at 1:36 PM, Dick Wall notifications@github.com wrote:

Either has been the subject of multiple improvement suggestions in the past. Or, Xor and validation come up a lot in related (possibly more expansive) discussions.

Changing the nature of Either, or introducing new library types and defining their relationship to Either, is likely to be a big task. Multiple interested parties and suggestions are listed below.

We need a volunteer to start contacting the parties, gauge their interest and ask for a commitment to be involved in defining a SLIP proposal for this.

I would also like to record my own suggestion (strictly a suggestion) that perhaps the problem is broken into more than one phase, e.g. a quick fixup to increase the value of Either (maybe implicit bias or similar) in the short term, and a longer term SLIP around the whole area of Validation, etc. which would also defined the inter-relationships.

Links to existing material and known interested parties will be listed in a comment below.

— Reply to this email directly or view it on GitHub https://github.com/scala/slip/issues/5.

[SethTisue]

I agree with Rex that Either should be left alone (except perhaps adding optional biasing implicits). because 1) history/compatibility, and 2) it's valuable for the standard library to include a general unbiased sum type.

it would be awesome if Rob's implicits experiment were available as a JAR that people could add to their libraryDependencies, so that the community get easily get some experience with it in our projects and decide whether it's good enough and useful enough to merit inclusion in stdlib.

[SethTisue]

as for adding a new type along the lines of Validation or Or... maybe if people get their heads together an appealing solution can be found, but my initial feelings about it are... iffy.

on the one hand, I have a soft spot for Or, since @bvenners has explicitly stated harmony with stdlib a goal (whereas scalaz often ignores or even opposes stdlib and aims instead at their own internal consistency).

but it concerns me a bit that Or is still pretty new and I don't know how much experience the community has with it yet.

also, if we end up with a situation where both scalaz and cats feel obliged to ignore the new stdlib type and roll their own instead, then it's not clear the stdlib addition will have been worth doing. and in order to compete with Or and Validation, a new type would have to support error accumulation — it's not enough to just have biasing — and I'm not sure it would be possible to get everyone to agree on how that should be supported. (via a Monoid type? whose? or via something like Or's friend Bad? thinking out loud...)

[bvenners]

I am happy to participate and/or lead the expert group. Dick asked me to post something creative and inspiring here, and this was the best I could come up with.

[mpilquist]

Looking forward to participating in this SLIP.

I've used Either, scalaz.\/ and scalaz.EitherT extensively in large code bases and on large teams, helped with the design of cats.data.Xor, wrote cats.data.XorT, and wrote scodec.Attempt for scodec as a (specialized) replacement for scalaz.\/.

[dickwall]

Request for status update for Sept 10th SLIP meeting. How is formation of the expert group going?

[Ichoran]

Nobody has contacted me about forming the expert group. @bvenners - Are you going to get us started / organized? I second Bill's nomination, if it needs seconding and if he wants to do it. I could also organize the group, I suppose.

[bvenners]

Sorry I was busy last week after a rather all-consuming contract. Perhaps we could begin with a meeting of interested parties. What time zones are each of you in? I'm in California, so Pacific time. Monday is a holiday in the US. So either sometime Tuesday or Wednesday would work for me, and still give Dick something to report on the Thursday 10th.

[Ichoran]

I am busy all day Tuesday. Almost any time on Wednesday would work.

[bvenners]

@Ichoran Wednesday works. What time zone are you in (so that we can avoid 3AM your time)?

[Ichoran]

@bvenners Same as you. I'm game for 3 AM if you are :)

[non]

(So, I definitely agreed to participate as well, but due to work and illness have failed to have the time I expected. But here are my thoughts.)

I agree with the general feelings (which @Ichoran articulates) that the Either ship has sailed. Other types do a better job than Either at being right-biased and trying to shoe-horn this behavior in is probably not a good plan.

I also share @SethTisue's concerns -- before agreeing that we should have a right-biased disjunction in the standard library I'd want to see what we were going to add and what semantics we expected (especially since the error-accumulating behavior and the right-biased monadic either behavior are incompatible).

I'm in the US Eastern time zone, and am available Tuesday and earlier (until about 3pm EDT) on Wednesday.

[bvenners]

Hi All,

Why don't we tentatively pencil in 11AM Pacific, 2PM eastern time on Wednesday, Sep 9. I believe @mpilquist and @SethTisue are in US time zones. We haven't yet heard from @soc. @soc is that a convenient time for you? Once confirmed I'll create a Google Hangout and invite everyone. If anyone else is interested in participating, please post here.

Thanks.

Bill

[Ichoran]

11 am works for me. (So do other times if 11 doesn't work for some.)

[non]

18:00 UTC (i.e. 2pm EDT) works for me too.

[SethTisue]

I'm in (for 2pm EDT).

[soc]

This should be in five and a half hours from now, right? Works for me! :-)

[bvenners]

Hi All,

This is the first Google Hangout I've actually created. I think I need emails from everyone who wants to participate. Please email me at bill@artima.com and I'll invite you.

Thanks.

Bill

[bvenners]

Here's the video recording of our meeting for your viewing pleasure:

https://www.youtube.com/watch?v=RUgMMAaZnx4

For next steps we decided to use this github repo to create a "bestiary" of current implementations of Either-like creatures, with a one or two page description with example code of each. We volunteered as follows:

Simon - Either as it now exists Seth - Scalactic Or Rex - Cats Xor and Validated Erik - Rex's favorite of his Either clones, the one he uses the most Bill - Scalaz \/ and Validation, and the enhance-Either-itself option

[bvenners]

Two discussions about the pros and cons of defining a filter method that takes a function that does not result in Boolean are here:

https://groups.google.com/forum/#!topic/scalatest-users/Eo7z5Db3mzg

and here:

https://groups.google.com/forum/#!msg/scalatest-users/XPtBcsFvmDk/I5fhy1AiKSIJ

[soc]

Does someone have a link to the Either repo?

[SethTisue]

I think we said we'd just use this repo. We can all push to it.

[swaldman]

Hi. I've been working on fixing Either for a while, and am certainly interested in helping.

For what it's worth, I've extracted my implementation of Either-biasing through implicit enrichment to a separate library (out from my fork of scala.util.Either). That library is called leftright, its code (intended to be embedded in the companion object to Either) is here.

If you want to try this out, it's on Maven Central, "com.mchange" %% "leftright" % "0.0.1"

I've left out the documentation to keep the code more concise and readable. However, extensive documentation remains in the scaladoc of the forked Either. Nothing has changed, except Either.LeftBias becomes BiasedEither.LeftBias and Either.RightBias becomes BiasedEither.RightBias. (oh... and you have to import com.mchange.leftright.BiasedEither now.)

There's a closed pull request and a proposed SLIP about this implementation as well.

I'm interested in helping out any way I can, whether or not the library code or implicit enrichment approach proves useful. Thanks!

[soc]

https://github.com/scala/scala/pull/5135

[soc]

@bvenners @Ichoran @SethTisue @non Ping?

[SethTisue]

well, this didn't happen. I guess we all overestimated the time and commitment we had for this. but 2.12 got right-biased Either anyway — which should probably have been SLIPped, but the process wasn't functioning at the time, so, good it could happen anyway.

(the fact that this (a functioning expert group, on this, or some other subject) didn't happen once doesn't rule out that it could happen in the future...)

[bvenners]

Yes, my plan was to work on it after I got ScalaTest 3.0 out the door, and that didn't happen until just last week. I felt the right-biased Either in 2.12 addressed this issue pretty nicely.

[Ichoran]

FWIW I am uneasy about the solution in 2.12 for a number of not-very-compelling reasons (limited functionality, loss of unbiased sum type, no monoid/filter, invites even more profusion of mediocre hand-rolled validation constructs, doesn't fix casting vs performance tradeoff, etc.). But my fears are not always well-founded, and I didn't have time to give any more input then than I did. I do think the 2.12 implementation is better than eternal stasis!

[SethTisue]

I'm afraid we won't really know until some of the people who have been using \/ or Or or Xor actually try using the new Either instead and see what happens.

[bvenners]

@Ichoran Yes, it would have been better if we'd at least picked up the discussion about the PR in this group. That's really my fault as I was the leader. I was just overwhelmed trying to get ScalaTest/Scalactic 3.0 out the door. But in the meantime the PR was discussed elsewhere and accepted into 2.12. I'll echo @SethTisue that we should see how people use the new Either in 2.12. In the meantime I have no plans on removing Or from Scalactic.

What's the "casting vs performance" tradeoff?

[Ichoran]

@bvenners - I mean this kind of thing.

def lmap1[A,B,A2](e: Either[A,B])(f: A => A2): Either[A2,B] = e match {
  case Left(a) => Left(f(a))
  case r: Right[A, B] => r.asInstanceOf[Either[A2,B]]   // Casting :(
}

def lmap2[A,B,A2](e: Either[A,B])(f: A => A2): Either[A2,B] = e match {
  case Left(a) => Left(f(a))
  case Right(r) => Right(r)  // No cast but slow :(
}

def lmap3[A,B,A2](o: Ok[A,B])(f: A => A2): Ok[A2,B] = o match {
  case No(n) => Left(f(n))
  case y: Yes[B] => y  // Fast, no cast
}

I likewise have no plans yet to drop use of Ok in my own libraries. (I might someday switch to Or or Xor which have similar properties IIRC.)

But if the 2.12 Either is widely used for this sort of thing and a nice set of standard practices develop, then maybe I would reconsider. (There are some places I already just use Either because I don't want any dependencies.)

[swaldman]

with @Ichoran, i'm not so excited with the result here, but non-stasis is a consolation prize. @soc was kind enough to write up an explanation of his views. i continue to disagree, strongly, but it is time to move on.

i will migrate my own libraries away from Either, as the 2.12 changes don't address the issues that concern me. i didn't mind the projection boilerplate. i don't like using a construct that sort of works in for comprehensions but fails capriciously when certain features are used. that has not been fixed. we all have different priorities. library heterogeneity is a great thing.

i'm sorry this didn't go differently. there might have been a better result and a better aftertaste. but no one should feel too bad. @soc did a lot of work, and even those of us who don't like the outcome should be grateful for that. @bvenners has a life, and i don't think anyone thought he had any special obligation to make something happen here.

[soc]

I hope we can address the missing parts in the future, when we have a Monoid in the standard library, as this feels like the cleanest way to fix it. The change for 2.12 was made with this in mind: do what's possible right now, without introducing anything that might become obsolete a bit further down the road and keep the door open for the improvements we want in the future (filter when Monoid arives, an unbiased 90% replacement of unbiased Either when we get union types).

[swaldman]

@soc You probably have a better idea than I do of what is or is not likely in future standard library API. So far it seems like standard library APIs have (perhaps foolishly!) avoided explicitly algebraic constructs. Regardless, there might be a way to "have your cake and eat it too", given that for comprehensions can make use of two special methods (filter and withFilter), and reliably prefers withFilter if it is present. Would it be possible to define a means now of nominating an empty Left token for withFilter, and let filter make use of a standard Monoid if and when such a thing is defined? Then old code that nominated an empty wouldn't break (because withFilter would have precedence) while new code in future that defined an appropriate implicit Monoid would "just work" as long as the old nomination API isn't used.

I don't know if this is a workable idea or not. Both the current and future method could be implemented directly on right-biased Either with an extra implicit argument list or via an implicit enrichment wrapper class with no need for an extra argument list on filter/withFilter. It would take some thought I think to persuade oneself that things prioritize cleanly and will always do so (i.e. that whatever might work now follows from the language specification, and is not an artifact of implementation details of the compiler that might change).

Anyway, this might be a ridiculous idea. I haven't tried to implement it, and won't, I'm moving on. This is the kind of thing we might have discussed (and perhaps eliminated) if we had discussed things. Thank you again for all your work, and for taking the time to provide such a detailed rationale.

[soc]

I think support for filter in for-comprehensions has already been deprecated/removed. So we only have a single method left, leaving only the route via an implicit wrapper. I'm concerned that this isn't the right way as we have already too many of these things in the standard library, and I don't want to imagine how things interact with external libraries which already implement various extensions for typeclasses.

[mpilquist]

For what it's worth, I'm very much against defining filter in terms of the identity element of a Monoid. Using the identity element is rarely desirable and often leads to surprising behavior. That's why cats.data.Xor does not define filter, preferring ensure which has the signature:

sealed abstract class Xor[+A, +B] extends Product with Serializable {
  def ensure[AA >: A](onFailure: => AA)(f: B => Boolean): AA Xor B
}

@soc Do you have a compilation of complaints / suggestions / improvements for Either compiled somewhere? If so, maybe we could move the conversation there (even if it is a new issue in this repo).

[bvenners]

@mpliquist I was going to say something similar about Monoid. I didn't realize Cats went that way. Nice. I never felt Scalaz's approach of using Monoid to determine a desired error value for a type was appropriate, because something more domain specific is needed. In Scalactic Or we have a filter (and withFilter) method that takes a "Validation function."

sealed abstract class Or[+G,+B] extends Product with Serializable {
  def filter[C >: B](f: G => Validation[C]): G Or C
}

Validation is either a Pass or a Fail, where Pass is a singleton object and Fail holds an error value of type T. (Validation, by the way, is conceptually like the type of a test. When a test succeeds, you don't want any further info other than an indication of success. If a test fails, however, then you want some info about what went wrong.)

This allows Or to be used in for comprehensions with a filter that produces Validation instead of Boolean. The one problem with this approach is that sometimes the compiler will unnecessarily generate a filter that takes a predicate (T => Boolean), and then you get a compiler error that can be fixed with a implicit conversion. It is rare, and I'm hopeful that someday the compiler will optimize away the unnecessary filter call. Until that happens, I wouldn't recommend this approach for the standard library. Though if that does get fixed (and Adriaan hinted he hoped someday it would happen) then something like Scalactic's Validation can be used to add support in right-biased Either for for expression filters.

[bvenners]

@swaldman I'm not sure I'd call it "having a life," more like "having one massive open source activity on my plate that left no room for other open source activities." We also got quite far behind in PRs and issues on ScalaTest while we were trying to focus on getting 3.0 done. It is nice now we can start giving those some attention as well as other things (like this SLIP had the PR effort not happened).

Also, although some in this group wondered out loud if we could get something into 2.12, I always felt that would be too rush and that 2.13 was the better target, especially since 2.13 will be a "library release" and 2.12 is a "compiler release." I do think that with the standard library progress must be balanced with stability. We want to make the standard library better but need to really care about the managing the impact on existing code and try very hard to get it right before we release. (I have a get it right bias.)

[bvenners]

@Ichoran Ah, yes and fixing the "casting vs performance tradeoff" would require dropping the extra type param in each of Left and Right. That's a breaking change for which I can't think of a way to have a deprecation cycle. I just did that to Or in Scalactic 3.0. Originally in an attempt to be consistent with Either in the standard library I had two type params on each of Good and Bad. I decided (realized) this was a mistake, so in 3.0 we dropped the unnecessary type param. I forgot to remove the casts that I had internally, so I did that just now:

https://github.com/scalatest/scalatest/commit/d40d278f2bb8e73431b942d87881fb6dbab75cb9

Felt good. I figured because of Or's particular syntax that dropping the unnecessary type parameter would in practice break very little code. But it may break some, which makes it quite tricky to do in the standard library.

[Ichoran]

For what it's worth, the case Left(l) => Left(f(l)); case _ => e.asInstanceOf[Either[A2, B]] pattern is usually slightly faster yet, and still needs the cast. (The main problem with the Right(r) => Right(r) thing is really memory churn; when GC is easy and memory isn't an issue, it's about the same speed as the cast.)