fixing Either

[Rob Dickens]

Dear All,

Following the earlier, inconclusive debate on 'right-biasing Either',

https://groups.google.com/group/scala-debate/browse_thread/thread/2bac2fe8aa6124ad?hl=en

I had a go at writing a SIP, but ended up with the following blog post:

Fixing scala.Either - unbiased vs biased
http://robsscala.blogspot.co.uk/2012/06/fixing-scalaeither-unbiased-vs-biased.html

If you aren't already bored to death with the subject, please take a
look, and let's try to reach a consensus this time.

Best regards,

Rob

[Gary Pampara]

Right-bias. The alternate simply does not make sense. If no consensus
can be reached, then rather do nothing. I'd rather deal with an
implicit conversion.

[Chris Marshall]

I think they should right-bias it.

I don't like your applicative stuff, I'm afraid. It's pointless adding applicative for Either but for no other types ~ the scalaz approach is manifestly superior (I find myself thinking that a lot now)

Chris

> Date: Thu, 14 Jun 2012 17:13:18 +0100
> Subject: [scala-debate] fixing Either
> From: robcd...@gmail.com
> To: scala-...@googlegroups.com; jza...@gmail.com

[Tony Morris]

It should be right-biased, like it was back at the start.

Consensus failed due to a derailing with irrelevant discussion e.g. exceptions, errors. We should try not to do that. Either is a binary functor denoting summation, nothing more. Talk of exceptions are orthogonal to this matter. Oh, almost forgot, I also heard that Either is a glorified tuple, but that might be nonsense.

[Rob Dickens]

Chris, Oh well. I haven't included anything about the applicative
stuff, and wouldn't expect that to be incorporated in the fix.

[Rob Dickens]

Tony, Do you agree with my proposal to exclude filter (and withFilter)?

[Tony Morris]

Yes. Either does not have filter, because it does not have a unit constructor. It should never have existed. It's a dirty, stinking hack.

The existing filter might continue to exist, as _.toOption andThen _.filter(p), but it is currently misnamed.

[Kevin Wright]

Agreed.  All we're proposing - so far as I can tell - is to add the map and flatMap methods (but not filter/withFilter) onto the Option class and to have them behave in the same fashion as on a right projection.

exceptions/errors aren't relevant.  Interesting points were raised, but this proposal doesn't make things any worse for those who raised them.  It just makes things easier for everyone else.

[Daniel Sobral]

The problem with lack of withFilter is that it makes pattern matching
impossible. For example, say "either" is of type [Exception,(Int,
String)], then this becomes impossible:

for ((n, s) <- either) yield s

--
Daniel C. Sobral

I travel to the future all the time.

[Rex Kerr]

I don't see any way to let Either do this.  This suggest to me that Either is simply the wrong concept to use in for-comprehensions.  If it's the wrong concept to use it for-comprehensions, it doesn't much matter whether it's right-biased or not, IMO.  You need something isomorphic to Either[Option[L],R] (assuming right-bias).

Creating something isomorphic is not hard and works well (for me, at least); I posted a link to code for something called "Has" on the other thread which is exactly this.  It does the for ((n,s) <- e) thing as desired, but it's not Either.  I don't think there's a sensible path for Either to become something like that.

So I'm unconvinced presently that right-biasing Either is the correct move.  For those cases where you really want right-biasing (i.e. you want to be able to focus fully on the right branch), you probably don't want Either at all--you'll be tripped up by the inability to filter.

I propose adding something new that is isomorphic to Either[Option[L],R] and which is right-biased.  Alternatively, perhaps there is a way to get a right-biased Either to act appropriately when it is actually an Either[Option[_],_].

  --Rex

[Tony Morris]

The inability to filter Either is unavoidable and always has been. It has no unit constructor. This fact of the matter is distinct, orthogonal and not relevant to the necessity to right-bias.

[Rob Dickens]

First, Daniel, thanks for that torpedo of enlightenment!

> The problem with lack of withFilter is that it makes pattern matching
> impossible.

I'd completely overlooked pattern-matching.

> for ((n, s) <- either) yield s

This results in,

error (points to either): value filter is not a member of
Either[Exception, (Int, String)]

Okay, using -Xprint:typer shows what it desugars to:

either.filter(((check$ifrefutable$1) => check$ifrefutable$1:
@scala.unchecked match {
case scala.Tuple2((n @ _), (s @ _)) => true
case _ => false
})).map(((x$1) => x$1: @scala.unchecked match {
case scala.Tuple2((n @ _), (s @ _)) => s
}))

So it looks like the compiler is assuming that _anything_ that appears
in a for-comprehension has a filter, which maybe it shouldn't do!

You can pattern-match on anything, but it doesn't follow that all
containers must have filters, as Either demonstrates.

Perhaps the compiler needs to do some extra work to check this first,
and if necessary, employ, in this case, an (Int, String) =>
Option[(Int, String)].

Rob

PS tried to reply earlier but lost my internet connection until just.

[√iktor Ҡlang]

Or perhaps:

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

e: Either[Int,String] = Right(foo)

scala> for(Right(s) <- e) println(s)

<console>:9: error: value filter is not a member of Either[Int,String]

              for(Right(s) <- e) println(s)

--
Viktor Klang

Akka Tech Lead

Typesafe - The software stack for applications that scale

Twitter: @viktorklang

[Lars Hupel]

> scala> for(Right(s) <- e) println(s)
> <console>:9: error: value filter is not a member of Either[Int,String]
> for(Right(s) <- e) println(s)

I'm not sure whether that already popped up in the discussion, but isn't
`collect` the appropriate method here? However, the desugaring of `for`
comprehensions had to be changed, and I don't know whether this is a
good idea.

[Runar Bjarnason]

On Saturday, June 16, 2012 8:33:48 AM UTC-4, Rex Kerr wrote:

I don't see any way to let Either do this.  This suggest to me that Either is simply the wrong concept to use in for-comprehensions.  If it's the wrong concept to use it for-comprehensions, it doesn't much matter whether it's right-biased or not, IMO.  You need something isomorphic to Either[Option[L],R] (assuming right-bias).

Either is exactly the kind of thing that should be usable with a monad comprehension. Maybe what this rather points to is that this expression is currently desugared incorrectly:

for { (a, b) <- either } yield a

It should desugar to something like:

either.map { case (a, b) => a }

Requiring filter here doesn't make a great deal of sense.


Runar

[Rex Kerr]

On Sat, Jun 16, 2012 at 4:08 PM, Runar Bjarnason <runar...@gmail.com> wrote:

On Saturday, June 16, 2012 8:33:48 AM UTC-4, Rex Kerr wrote:

I don't see any way to let Either do this.  This suggest to me that Either is simply the wrong concept to use in for-comprehensions.  If it's the wrong concept to use it for-comprehensions, it doesn't much matter whether it's right-biased or not, IMO.  You need something isomorphic to Either[Option[L],R] (assuming right-bias).

Either is exactly the kind of thing that should be usable with a monad comprehension. Maybe what this rather points to is that this expression is currently desugared incorrectly:

for { (a, b) <- either } yield a

Well, yes, that's of course true also.  But

  for { (a,b) <- either if b>5 } yield a

is still out.  Some instances of filtering are correct, and this is what makes Either a bad fit for for-comprehensions.  It would be fine if there were a way to inject a Left in there, but I don't know of one that isn't intolerably clunky.  You'd need an orElse equivalent in the for comprehension syntax.

  --Rex

 

[Runar Bjarnason]

On Sat, Jun 16, 2012 at 5:51 PM, Rex Kerr <ich...@gmail.com> wrote:
> Well, yes, that's of course true also.  But
>
>   for { (a,b) <- either if b>5 } yield a
>
> is still out.

Right, the desugaring of if cannot be done with Either. But pattern
assignment should still work, and it's a mistake to conflate the two.

> Some instances of filtering are correct, and this is what
> makes Either a bad fit for for-comprehensions.

The fact that for-comprehensions support monads with a seminearring
structure doesn't mean that something smaller like Either is a "bad
fit". It just means it can't avail itself of all of the features. That
would be like saying that the rational numbers are a bad fit for
mathematical notation because they don't support square roots of one.

>It would be fine if there
> were a way to inject a Left in there

That's not possible unless the left type is a monoid. Would be awesome
if Scala could in fact figure that out.

[Jason Zaugg]

On Sat, Jun 16, 2012 at 11:51 PM, Rex Kerr <ich...@gmail.com> wrote:
>
>
> On Sat, Jun 16, 2012 at 4:08 PM, Runar Bjarnason <runar...@gmail.com>
> wrote:
>>
>>
>> On Saturday, June 16, 2012 8:33:48 AM UTC-4, Rex Kerr wrote:
>>>
>>> I don't see any way to let Either do this.  This suggest to me that
>>> Either is simply the wrong concept to use in for-comprehensions.  If it's
>>> the wrong concept to use it for-comprehensions, it doesn't much matter
>>> whether it's right-biased or not, IMO.  You need something isomorphic to
>>> Either[Option[L],R] (assuming right-bias).
>>>
>>
>> Either is exactly the kind of thing that should be usable with a monad
>> comprehension. Maybe what this rather points to is that this expression is
>> currently desugared incorrectly:
>>
>> for { (a, b) <- either } yield a
>
>
> Well, yes, that's of course true also.  But
>
>   for { (a,b) <- either if b>5 } yield a
>
> is still out.  Some instances of filtering are correct, and this is what
> makes Either a bad fit for for-comprehensions.  It would be fine if there
> were a way to inject a Left in there, but I don't know of one that isn't
> intolerably clunky.  You'd need an orElse equivalent in the for
> comprehension syntax.

`Left a | Right b` isn't worse or better than `Nope | Fail f | Success s`;
they are just different datatypes, for different situations. Sometimes your
control flow will be better modelled with one or the other.

The intention isn't to mould Either to work in arbitrary for comprehensions.
Rather, we should make sure that they work well for natural usages
of Either. If the projections return themselves, rather then Either, we
solve SI-5793; if Either itself has right biased map/flatMap we reduce some
clutter for common usage.

-jason

[Tony Morris]

On a related note, I think we should right-bias Either.

--
Tony Morris
http://tmorris.net/

[Paul Phillips]

On Sat, Jun 16, 2012 at 1:08 PM, Runar Bjarnason <runar...@gmail.com> wrote:

for { (a, b) <- either } yield a

It should desugar to something like:

either.map { case (a, b) => a }

I don't know if that's hypothetical syntax or what, but to the extent it maps onto the actual Either, see and perhaps reopen https://issues.scala-lang.org/browse/SI-1336 .  Irrefutable patterns without guards should not have filter calls in the desugaring.

[Daniel Sobral]

On Sat, Jun 16, 2012 at 12:14 PM, Rob Dickens <robcd...@gmail.com> wrote:
> First, Daniel, thanks for that torpedo of enlightenment!
>
>> The problem with lack of withFilter is that it makes pattern matching
>> impossible.
>
> I'd completely overlooked pattern-matching.
>
>> for ((n, s) <- either) yield s
>
> This results in,
>
>  error (points to either): value filter is not a member of
> Either[Exception, (Int, String)]
>
> Okay, using -Xprint:typer shows what it desugars to:
>
> either.filter(((check$ifrefutable$1) => check$ifrefutable$1:
> @scala.unchecked match {
>  case scala.Tuple2((n @ _), (s @ _)) => true
>  case _ => false
> })).map(((x$1) => x$1: @scala.unchecked match {
>      case scala.Tuple2((n @ _), (s @ _)) => s
>    }))

Note that it tries withFilter first.

>
> So it looks like the compiler is assuming that _anything_ that appears
> in a for-comprehension has a filter, which maybe it shouldn't do!

It assumes nothing, actually. It simply desugars some things into
other things. Non-yielding loops desugar into foreach, yielding into
map+flatMap, pattern matching and if into withFilter/filter, and so
on. It doesn't even care what type signature those methods have! You
could have a zero-arity flatMap returning an object that has an apply
method, for instance.

Or, more important, you can have a "withFilter" that takes a partial
function and simply throws an exception if it doesn't match.

> You can pattern-match on anything, but it doesn't follow that all
> containers must have filters, as Either demonstrates.

What happens when the pattern match doesn't match? That's the point of
using withFilter on a pattern match.

[Daniel Sobral]

1. What happens if the match fails?
2. So why not do that on the "withFilter" method?

[Runar Oli]

Because Either does not and cannot have one.

[Tony Morris]

x.filter(_ => true) == x
x.filter(_ => false) == Monoid.zero

These are reasonable expectations of filter. Things with filter can be achieved with a monad with plus/empty. Not all monads have this. Notice that Function1 had map +flatMap but not filter. This is because it cannot exist, like for Either. Because not all monads have plus/empty. Some monads do not have filter. This is fine, mundane, common.

This fact is all completely beside the point of the necessity to right-bias Either. I wish this topic wasn't derailed each time it is brought  up. Perhaps we can have a "I really wish Either had filter, what a stupid universe" thread or something.

[Rob Dickens]

> either.map { case (a, b) => a }

How about this, instead:

either map { b => val (n, s) = b; s }

https://github.com/robcd/scala-either-proj-map-returns-proj/blob/right-biased/src/test/scala/DanielsPatternMatchingExample.scala

Rob

[Rob Dickens]

Well, I for one am convinced that Either shouldn't have a filter (or
withFilter). However, we still need to sort out the pattern-matching
business (which got raised along the way).

Regarding unbiased vs biased, if anyone could come up with an example
which required both returnsEither.rp AND returnsEither.lp, I'd be much
obliged. Otherwise, I'll assume that the use cases are so rare that we
might as well go biased.

Rob

[Jason Zaugg]

On Sun, Jun 17, 2012 at 11:39 AM, Rob Dickens <robcd...@gmail.com> wrote:
> Well, I for one am convinced that Either shouldn't have a filter (or
> withFilter). However, we still need to sort out the pattern-matching
> business (which got raised along the way).

As Paul suggested, that problem is fixed in Scala 2.10.

https://github.com/scala/scala/commit/c82ecabad6

~/code/scala scala210
Welcome to Scala version 2.10.0-20120504-065643-e52be82eef (Java
HotSpot(TM) 64-Bit Server VM, Java 1.6.0_31).
Type in expressions to have them evaluated.
Type :help for more information.

scala> val r = Right((1, 1))
r: Right[Nothing,(Int, Int)] = Right((1,1))

scala> for { (a, b) <- r.right } yield a
res0: Either[Nothing,Int] with Product with Serializable = Right(1)

> Regarding unbiased vs biased, if anyone could come up with an example
> which required both returnsEither.rp AND returnsEither.lp, I'd be much
> obliged. Otherwise, I'll assume that the use cases are so rare that we
> might as well go biased.

I don't understand the question. I agree with your suggestion to add new
projections and deprecate the existing ones. I also suggest to add right
biased methods directly to Either.

-jason

[Rob Dickens]

> As Paul suggested, that problem is fixed in Scala 2.10.

Sorry, still digesting that!

>> Regarding unbiased vs biased, if anyone could come up with an example
>> which required both returnsEither.rp AND returnsEither.lp, I'd be much
>> obliged. Otherwise, I'll assume that the use cases are so rare that we
>> might as well go biased.
>

> I don't understand the question. I agree with your suggestion to add new
> projections and deprecate the existing ones. I also suggest to add right
> biased methods directly to Either.

I'd been thinking (all along) that we should do one thing _or_ the
other. So you're suggesting we do both, eh?

Okay, well why not?!

We'd get the convenience of not having to append .rp (or .lp) and .e
all over the place in the vast majority of use-cases, while still
having them around for the rarer ones.

On Sun, Jun 17, 2012 at 11:23 AM, Jason Zaugg <jza...@gmail.com> wrote:

> On Sun, Jun 17, 2012 at 11:39 AM, Rob Dickens <robcd...@gmail.com> wrote:
>> Well, I for one am convinced that Either shouldn't have a filter (or
>> withFilter). However, we still need to sort out the pattern-matching
>> business (which got raised along the way).
>

> As Paul suggested, that problem is fixed in Scala 2.10.
>
> https://github.com/scala/scala/commit/c82ecabad6
>
>  ~/code/scala scala210
> Welcome to Scala version 2.10.0-20120504-065643-e52be82eef (Java
> HotSpot(TM) 64-Bit Server VM, Java 1.6.0_31).
> Type in expressions to have them evaluated.
> Type :help for more information.
>
> scala> val r = Right((1, 1))
> r: Right[Nothing,(Int, Int)] = Right((1,1))
>
> scala> for { (a, b) <- r.right } yield a
> res0: Either[Nothing,Int] with Product with Serializable = Right(1)
>

>> Regarding unbiased vs biased, if anyone could come up with an example
>> which required both returnsEither.rp AND returnsEither.lp, I'd be much
>> obliged. Otherwise, I'll assume that the use cases are so rare that we
>> might as well go biased.
>

[Rob Dickens]

Have just added a new branch to the project:

* Either now has both unbiased (via lp, rp) AND right-biased capability

* have added some pattern-matching tests (which, though far from
exhaustive, work fine)

* the pattern-matching requires Scala 2.10 (and therefore sbt 0.11.3).

This version looks to me like the SIP candidate - please take a look
and see if you agree:

https://github.com/robcd/scala-either-proj-map-returns-proj/tree/add_right-bias_2-10

Rob

[Rex Kerr]

On Sat, Jun 16, 2012 at 10:53 PM, Tony Morris <tonym...@gmail.com> wrote:

x.filter(_ => true) == x
x.filter(_ => false) == Monoid.zero

These are reasonable expectations of filter. Things with filter can be achieved with a monad with plus/empty. Not all monads have this. Notice that Function1 had map +flatMap but not filter. This is because it cannot exist, like for Either. Because not all monads have plus/empty. Some monads do not have filter. This is fine, mundane, common.

Completely agreed.
 

This fact is all completely beside the point of the necessity to right-bias Either.

Completely disagreed.  I use Either outside of for-comprehensions and have never missed the right bias in contexts where I do not care if I have a filter or not.  To me, this is the key issue.  If I am going to
  e match {
    case Left(x) => ...
    case Right(x) => ...
  }
then I don't care what bias Either has.  Likewise with fold.  In fact, if I am actually dealing with a symmetric case, then I'd rather _not_ have bias because e.left.map(f) makes it more obvious what is going on than the tempting e.swap.map(f).swap with a right-biased either, and the latter also poses risks of forgetting to swap back.

The only time I've missed the right-bias on either is when using for comprehensions.  And then, Either doesn't play nicely anyway _in part precisely because it does not have plus/empty_.
  for (rt <- e; x <- m.get(rt)) yield x   // Doesn't and can't work
  for (rt <- e; x <- m.get(rt).toRight("not found")) yield x  // Could work
  for (rt <- e; x <- m.get(rt) if x>0) yield x  // Can't work
  for (rt <- e; x <- m.get(rt).filter(_>0).toRight("nope")) yield x
  // Why even use for?

The reason I'm consistently lukewarm to negative about right-biasing Either is because Either is the wrong tool for the job for the most common uses of a right-biased union monad.

For being right-biased, either
  - Is misnamed ("either" doesn't suggest bias)
  - Isn't good for easy error handling (no filter)
  - Can't have full support within for-comprehensions (unless we change those also)
  - Historically wasn't that way
all of which recommends against the change.

Therefore, although I don't _strongly_ object to changing Either, I do strongly encourage us to consider whether a right-biased Either is a good enough solution for certain things (e.g. error handling), and if we had something that _was_ a good enough solution for error handling whether we would still want Either to be right biased.

In my case the answers are "no" and "no".  Other people may have different answers.  But I'm puzzled by the apparent reluctance of people to _even answer this question_.  It seems like there's too much enthusiasm for rushing into a partial fix to a problem that really warrants a complete fix, and which Either cannot theoretically deliver.

  --Rex

P.S. Actually, I think "else" statements in for comprehensions would adequately empower right-biased Either to be an adequate solution.  You would need to desugar
  for (x <- y if (p) else g) yield x
and
  for (x <- y else g)
into a conditional on p and y.isEmpty, respectively, inside an appropriate method.  Then Either would be as full-functioned as Option (and could enable some nice tricks with collections).
  def flatDefault(p: A=>Boolean, default: => Either[A,B]): Either[A,B] = ...
or the corresponding non-flat version (i.e. default: => B) would probably do the trick, but I haven't worked through all possible cases to make sure it would always do the right thing.

[Tony Morris]

I give up. Godspeed.

[Josh Suereth]

We could go strange on the Either front:

val x: Either[A,B] = 

  for {

    Left(x) <- doSomething

    Right(y) <- somethingElse(x)

  } yield Left(y)

has this already been negated as a bad idea?

What I think would be nice to fix is:

val x: Either.LeftProjection[A,B] = 

  for {

     x <- doSomething.left

     y <- doSomethingElse(x).right

   } yield y

or just:

val x : Either[A,B] =

  (for {

     a <- doA.left

     b <- doB(a)

     c <- doC(b)

  } yield c).toEither

Am I missing something?

[Derek Williams]

On Mon, Jun 18, 2012 at 12:11 PM, Rex Kerr <ich...@gmail.com> wrote:

then I don't care what bias Either has.  Likewise with fold.  In fact, if I am actually dealing with a symmetric case, then I'd rather _not_ have bias because e.left.map(f) makes it more obvious what is going on than the tempting e.swap.map(f).swap with a right-biased either, and the latter also poses risks of forgetting to swap back.

Would you really find e.swap.map(f).swap more tempting then e.left.map(f)?

 

The only time I've missed the right-bias on either is when using for comprehensions.  And then, Either doesn't play nicely anyway _in part precisely because it does not have plus/empty_.
  for (rt <- e; x <- m.get(rt)) yield x   // Doesn't and can't work
  for (rt <- e; x <- m.get(rt).toRight("not found")) yield x  // Could work
  for (rt <- e; x <- m.get(rt) if x>0) yield x  // Can't work
  for (rt <- e; x <- m.get(rt).filter(_>0).toRight("nope")) yield x
  // Why even use for?

I'd personally write the for comprehension as:

for {

  rt <- e

  x <- m get rt toRight "not found"

  y <- if (x > 0) Right(x) else Left("<= 0")

} yield y

which is similar to what you would get with your suggested if/else syntax, but it also adds a more refined error. To write this currently it would have to look like this:

for {

  rt <- e.right

  x <- (m get rt toRight "not found").right

  y <- (if (x > 0) Right(x) else Left("<= 0")).right

} yield y

But this isn't just about for comprehensions, and for better code reuse and testing it would probably look more like:

val notFound = Left("not found")

val notValid = Left("not valid")

def validate(x: Int) = if (x > 0) Right(x) else notValid

def lookup(key: A) = m get key map validate getOrElse notFound

e flatMap lookup

to turn this into a for comprehension example, maybe I want to get a list of values from that map and add them up:

(Right[String, Int](0) /: List(k1, k2, k3)) { (e, k) =>

  for (r <- e; x <- lookup(k)) yield r + x

}

and I could do this now, but it would look like this:

(Right[String, Int](0) /: List(k1, k2, k3)) { (e, k) =>

  for (r <- e.right; x <- lookup(k).right) yield r + x

}

It's an annoyance that isn't needed, especially if we keep backwards compatibility. Whenever I want to do anything useful with that value (using map or flatMap), I need to append '.right', which could end up being quite often. Very little of my code is going to be dealing with the Left value, just like very little of my code that uses Option checks for None.

Speaking of Option, we could call it misnamed as well since it is sometimes used for non optional values, and we deal with it like it's an error if it is None. That is no reason to introduce a Required class that does the same thing.

Therefore, although I don't _strongly_ object to changing Either, I do strongly encourage us to consider whether a right-biased Either is a good enough solution for certain things (e.g. error handling), and if we had something that _was_ a good enough solution for error handling whether we would still want Either to be right biased.

In my case the answers are "no" and "no".  Other people may have different answers.  But I'm puzzled by the apparent reluctance of people to _even answer this question_.  It seems like there's too much enthusiasm for rushing into a partial fix to a problem that really warrants a complete fix, and which Either cannot theoretically deliver.

My answers to those questions are "yes" and "I see no reason to have both an unbiased Either and a biased Either-like class in the standard library when it can be used both ways without conflict". Either does the job just fine, it's just annoying to have to call '.right' when using it like this.

--

Derek Williams

[Rob Dickens]

Rex, It would help me a lot if you could possibly build the project in
the branch I created yesterday

https://github.com/robcd/scala-either-proj-map-returns-proj/tree/add_right-bias_2-10

and then try to write some complete examples using that version of Either.

Then, if there's something that doesn't work, let's see _that_ code.

That way, we'll all know exactly what we're dealing with, and be able
to understand the limitations of what is a well-defined (and, so far,
workable) proposal.

Rob

[Rob Dickens]

Josh, Looking at just your first snippet, using the proposed Either*,
the following should work, once the 2.10 compiler is fixed** for this
kind of pattern (as it already is for tuple patterns):

type EInner = Either[String, Int]
type EOuter = Either[String, EInner]
def doSomething: EOuter = Right(Left("er"))
def doSomethingElse(s: String): EOuter = Right(Right(s.toInt))

val x: EOuter =
for {
Left(x) <- doSomething
Right(y) <- doSomethingElse(x)
} yield Left(y.toString)

It that's not what you had in mind (which I fear it isn't), please
give us a more complete version!

* right-biased, retains unbiased capability (via lp, rp methods), no filter
** error ( > doSomething): value filter is not a member of EOuter

Rob

[Josh Suereth]

I'll have to work on a complete version, but the below is something I think Either should handle....

What I didn't have in mind was this:

 val x: EOuter =
   for {
     Left(x) <- doSomething

     z = doSomethingWithoutEither
     Right(y) <- doSomethingElse(x)
   } yield Left(y.toString + z)

That z there HOSES IT ALL UP!

Let me tinker some more.  Maybe I'll hit some inspiration on that too.

[Rob Dickens]

Re your second snippet,

> What I think would be nice to fix is:
>
> val x: Either.LeftProjection[A,B] =
> for {
> x <- doSomething.left
> y <- doSomethingElse(x).right
> } yield y

y is of type B, which is the wrong one for a LeftProjection.

But you _can_ do this if you take away the yield. Have never tried this before!

for {
x <- doSomething.left
y <- doSomethingElse(x).right

} println(x +" and "+ y)

So thanks for introducing me to one clear advantage using Either's
unbiased capability!

Rob

On Mon, Jun 18, 2012 at 11:19 PM, Josh Suereth <joshua....@gmail.com> wrote:

[Rob Dickens]

Regarding being able to use both projections in the same
for-comprehension provided you don't use yield, the last three tests
in this suite demonstrate this:

https://github.com/robcd/scala-either-proj-map-returns-proj/blob/add_right-bias_2-10/src/test/scala/unbiased_Tests.scala

However, I'm not sure it's really that useful!

Rob

[Rex Kerr]

Hi Rob,

All the examples I gave before do not work, as it is logically impossible for them to work.  If you want test cases, here they are as methods (unbiasedAlternative versions use the existing Scala Either):

// Rules: if it's a number, map it to a string
// If it's not a number, the string should be Left
// If it is a number and not in the map, don't care as long as it's not Right
def cantLiftToOption = {
  // These three lines are always the same
  val s = "42"
  val m = Map(42 -> "Meaning of life")
  val e = try { Right(s.toInt) } catch { case _: Exception => Left(s) }

  // This is actually trying to for-comprehend something
  for (n <- e; what <- m.get(n)) yield what
}

def workingAlternativeOp = {
  val s = "42"
  val m = Map(42 -> "Meaning of life")
  val e = try { Right(s.toInt) } catch { case _: Exception => Left(s) }

  for (n <- e; what <- m.get(n).map(x => Right(x)).getOrElse(Left(s))) yield what
}

def unbiasedAlternativeOp = {
  val s = "42"
  val m = Map(42 -> "Meaning of life")
  val e = try { Right(s.toInt) } catch { case _: Exception => Left(s) }

  e.fold(l => Left(l), r => m.get(r).map(x => Right(x)).getOrElse(Left(s)))
}

def cantIf = {
  val s = "42"
  val m = Map(42 -> "Meaning of life")
  val e = try { Right(s.toInt) catch { case _: Exception => Left(s) }

  for (n <- e if m.contains(n)) yield n
}

def workingAlternativeIf = {
  val s = "42"
  val m = Map(42 -> "Meaning of life")
  val e = try { Right(s.toInt) catch { case _: Exception => Left(s) }
 
  e.flatMap(n => if (m contains n) Right(n) else Left(s))
}

def unbiasedAlternativeIf = {
  val s = "42"
  val m = Map(42 -> "Meaning of life")
  val e = try { Right(s.toInt) catch { case _: Exception => Left(s) }

  e.fold(l => Left(l), r => if (m contains r) Right(n) else Left(s))
}

There simply isn't any way to handle these since there is no empty Either.  And note that the unbiased alternatives _already_ handle this approximately as well as the right-biased version can.  So in these cases, there is no benefit of biasing.

In contrast, with a third (empty) option, you can (using my Has class):

def canLiftToOption = {
  val s = "42"
  val m = Map(42 -> "Meaning of life")
  val e = try { Yes(s.toInt) } catch { case _: Exception => Plea(s) }

  for (n <- e; what <- m.get(n)) yield what
}

def canIf = {
  val s = "42"
  val m = Map(42 -> "Meaning of life")
  val e = try { Yes(s.toInt) } catch { case _: Exception => Plea(s) }

  for (n <- e if (m contains n)) yield n
}

which will return No if s is not in the map, Plea(s) on a non-integer string, and Yes(...) if it succeeds.

Anyway, I'm tired of arguing this point.  Enough people want a right-biased either that it makes sense to do it.  If I want to write an unbiased union container, I am always free to do so (I can call it Toggle with Up/Down), and I have already written something that does what is useful and maximally for-comprehension-feature-compatible in the biased case.

  --Rex

[Rob Dickens]

Rex, Thanks a lot for the examples. This is what I've added to the
project (sorry for the wait):

https://github.com/robcd/scala-either-proj-map-returns-proj/blob/add_right-bias_2-10/src/test/scala/RexsTests.scala

Since Either can't have a None, we have to employ a B => Either[A,
Option[C]] in for-comprehensions, or else return a Left (as you
demonstrate).

This suggested to me that we could perhaps add a withFilter that
returns an Either[A, Option[B]]:

def withFilter(p: B => Boolean): Either[A, Option[B]] = this match {
case Left(a) => Left(a)
case Right(b) => Right(if (p(b)) Some(b) else None)
}

However, the few tests I've so far carried out with this suggest that
it breaks the rules.

Rob

[Rob Dickens]

> ...

>      Left(x) <- doSomething
>      Right(y) <- doSomethingElse(x)

> ...
> should work, once the 2.10 compiler is fixed for this kind of pattern

Hm.. maybe not. Unfortunately, it looks to me as though 'refutable'
pattern-matching in for-comprehensions just can't be supported for
Either (not having a 'None' subclass or withFilter method). Unless
Josh has thought of something...

Rob

[Rex Kerr]

That looks fairly reasonable.  Not ideal, but about as good as one can expect given the constraints of logic and the decision to not add a third subclass of Either analogous to None.
  --Rex

On Mon, Jun 25, 2012 at 3:00 PM, Rob Dickens <robcd...@gmail.com> wrote:

Here's yet another branch, this time supporting for-comprehensions
containing 'if' and refutable pattern-matching:

https://github.com/robcd/scala-either-proj-map-returns-proj/tree/add_right-bias_2-10_withFilter

This one adds a withFilter to Either, that uses implicit conversions
to obtain a Left when the predicate is false.

Rob

[Rob Dickens]

Here's yet another branch, this time supporting for-comprehensions
containing 'if' and refutable pattern-matching:

https://github.com/robcd/scala-either-proj-map-returns-proj/tree/add_right-bias_2-10_withFilter

This one adds a withFilter to Either, that uses implicit conversions
to obtain a Left when the predicate is false.

Rob

[Rob Dickens]

Fingers crossed but I might just have pulled the rabbit out of the hat.

The implicit conversion used by the withFilter I added to Either
yesterday left a little bit to be desired: you had to supply implicit
conversions from particular tuples in some for-comprehensions
containing definitions, and there wasn't much control over which
conversions might be used.

Today I think I've successfully addressed both these problems, by
introducing a Left.Convert case class in which to put the value to be
converted. So all you do, if wishing to use 'if' or refutable
pattern-matching in for-comprehensions involving Either, is to provide
something like the following:

implicit def f(convert: Left.Convert) = convert.any.toString

Please take a look at withFilter and Convert here, and see what you think:

https://github.com/robcd/scala-either-proj-map-returns-proj/blob/add_right-bias_2-10_withFilter/src/main/scala/Either.scala

So it looks as though all that now remains to be done is to add a
similar withFilter to LeftProj and RightProj.

Rob

[Rob Dickens]

> So it looks as though all that now remains to be done is to add a
> similar withFilter to LeftProj and RightProj.

Now done. Tests involving 'Right(n) <- ...' also added.

Please see the project's README.md, which now goes into a bit more
detail about how withFilter works, and has links to the various test
suites:

https://github.com/robcd/scala-either-proj-map-returns-proj/tree/add_right-bias_2-10_withFilter

Think I'll now go back to writing that SIP.

Rob

[Rob Dickens]

> Think I'll now go back to writing that SIP.

Pull-request just submitted:

https://github.com/robcd/scala.github.com/blob/master/sips/pending/_posts/2012-06-29-fixing-either.md

Rob

[Daniel Sobral]

I really like it, but I must point out that there's no mention of any
migration strategy. I'm not sure one is even possible, but we must at
least address what old usage breaks, come up with deprecation where
possible, migration where deprecation is possible, meaningful error
messages where neither helps, big warnings where not even error
messages can be made to fit, and a migration guide for the release
notes.

[Rob Dickens]

Daniel, Great to hear!

In Part 1, it does at least mention the need to deprecate
LeftProjection, RightProject, and therefore left and right (which is
done in the project).

Otherwise, it's a case of adding new stuff, which (hopefully)
shouldn't break anything.

Btw, please reload the proposal page - I've been making improvements
here and there, including one just a few minutes ago.

[Daniel Sobral]

Also, I *really* dislike "lp" and "rp" as method names.

On Fri, Jun 29, 2012 at 5:36 PM, Daniel Sobral <dcso...@gmail.com> wrote:

> On Fri, Jun 29, 2012 at 5:29 PM, Rob Dickens <robcd...@gmail.com> wrote:
>> Daniel, Great to hear!
>>
>> In Part 1, it does at least mention the need to deprecate
>> LeftProjection, RightProject, and therefore left and right (which is
>> done in the project).
>

> I missed that, sorry. At any rate, do make a "Migration & Deprecation"
> section discussing these issues, please.

[Rob Dickens]

'Migration strategy' section now added.

> Also, I *really* dislike "lp" and "rp" as method names.

Well, I picked those names because they're nice and short. Compare the
following:

val lp = for {
b <- gt0(a).lp
c <- gt1(b).lp
} yield c

val leftProj = for {
b <- gt0(a).leftProj
c <- gt1(b).leftProj
} yield c

We can't use left and right, since they'd clash with the deprecated
ones, and anyway, the new methods now return projections (which
therefore also rules out using l and r).

[Tony Morris]

I *really really* want to stop entertaining the idea that "withFilter"
belongs on Either. Formally, there are additional properties required of
functors to give rise to withFilter. Either does *not* satisfy them, nor
do an enormous number of other functors. The gymnastic attempt using the
implicit is to be applauded only in its enthusiasm.

As a side note, I gave up on discussion of this matter in this forum and
spent a couple of yak-shaving hours writing scalaz.\/ with review by a
few others. It is a right-biased Either and includes a lot more library
functions.

Best of luck on your journey, but that withFilter truly does not belong!
I'm happy to formally or more rigorously demonstrate it to you if you
think it would help, but I also think there is a big enough red flag in
your implementation with that implicit argument wouldn't you say?

--
Tony Morris
http://tmorris.net/

[Rob Dickens]

Tony, Thanks for coming back.

First of all, by 'no withFilter' I take it you also mean no filter.
(Btw, if you wouldn't mind explaining why we have both, I'd be much
obliged.)

> Formally, there are additional properties required of

> functors to give rise to withFilter. ...
> I'm happy to formally or more rigorously demonstrate it to you ...

Yes please. (And be gentle.)

Btw, this is what I understand a functor to be:

trait M[A] {
def map[B](f: A => B): M[B]

[Daniel Sobral]

On Sat, Jun 30, 2012 at 9:57 AM, Rob Dickens <robcd...@gmail.com> wrote:
> Tony, Thanks for coming back.
>
> First of all, by 'no withFilter' I take it you also mean no filter.
> (Btw, if you wouldn't mind explaining why we have both, I'd be much
> obliged.)

Scala, up to 2.7.7, translated "if" statements and pattern matches
into calls to "filter".

From them on, the calls are made to "withFilter". The distinction is
this: "withFilter" is lazy -- it does not create a new collection.
Instead, it implements map, flatMap, foreach and withFilter in such a
way that they only receive the elements that satisfy the filter.
Meanwhile, "filter" follows the laziness of its collection. So
List.filter is strict, Stream.filter is lazy, but both List.withFilter
and Stream.withFilter are lazy.

Scala gives preference to withFilter in for comprehensions, only using
filter as a fallback.

If you do implement something, you should implement a lazy withFilter.

[Lars Hupel]

While looking at the trial source code, the case class `Convert` looked
odd to me. In part 1 of the SIP, you write:

"Note that `Convert` is a simple case class which serves to ensure that
the implicit conversion is properly targeted."

However, I don't even understand the problem this allegedly solves (see
the diff at
<https://github.com/robcd/scala-either-proj-map-returns-proj/commit/71d6fd8e3d8a46346ddda3a4ec287cceb6a44b6a>),
where it used to be:

case Right(b) => if (p(b)) Right(b) else Left(bToA(b))

I'd say, `bToA` should have the type `B => AA`. Why is it `Any` instead
of `B`? Shouldn't `B => AA` obsolete any kind of wrapper?

[Rob Dickens]

Fair questions, about something I haven't explained in the draught SIP.

> I'd say, `bToA` should have the type `B => AA`.

If the for-comprehension involves a definition, B is found to be a
tuple2 (whose first field is the b that the definition refers to, and
whose second field is the value of the definition). If there are two
definitions, B is found to be a tuple3, and so on.

> Why is it `Any` instead of `B`?

Considering that B is actually some tuple, whenever for-comprehensions
involve definitions, I first went with Any, as a catch-all.

However, I then realised how indiscriminate it would be to have an
implicit conversion from Any, and so introduced two containers
(Left.Convert, Right.Convert), which are just case classes having a
single field, any: Any.

[Tony Morris]

On 30/06/12 22:57, Rob Dickens wrote:
> Tony, Thanks for coming back.
>
> First of all, by 'no withFilter' I take it you also mean no filter.
> (Btw, if you wouldn't mind explaining why we have both, I'd be much
> obliged.)
>
>> Formally, there are additional properties required of
>> functors to give rise to withFilter. ...
>> I'm happy to formally or more rigorously demonstrate it to you ...
> Yes please. (And be gentle.)
>
> Btw, this is what I understand a functor to be:
>
> trait M[A] {
> def map[B](f: A => B): M[B]
> }
>

Well, let us try to come up with a formalism of filter. I am unaware of
anything that is as well-established as other operations such as
map/flatMap, however, we can take a crack ourselves.

We all know that a (semi)-Monad is required for flatMap and that flatMap
gives rise to map (with unit), but what gives rise to filter?

We might say that filter is defined on, any foldable in with
applicative+monoid out, defined like so:
def filter[F[_], G[_], A](x: F[A], p: A => Boolean)(implicit F:
Foldable[F], A: Applicative[G], M: Monoid[G[A]]): G[A] =
F.foldMap(a => if(p(a)) then A.point(a) else M.id)(x)

However, this is quite icky, given that:
a) We only use the Applicative's point (which opens up a bag of problems
-- too long to list)
b) We only use the Monoid's id.

As for implementation, there are also issues with value-boxing. For
example, for List, we all know that List(a) ::: b is not as elegant as a
:: b. I mention this definition because it is one that is often used to
generalise filter to provide any kind of general semantics.
Nevertheless, if we were to go with it, we see straight-away that Either
has no monoid, because it has no identity (except... see below).

Nevertheless, we might start again with some basic laws of any filter:
1) forall x. (x filter (_ => true) == x)
2) forall x. (x filter (_ => false) == Monoid.id)

However, again, although we have more elegant axioms, we are left in the
cold given that Either is absent a Monoid. It seems like we need a
nullary constructor for our ADT -- this can be easily achieved by
sticking Option in there, which is not particularly useful, since we
lose all the desirable properties of the ADT, which is to say, we are
now before the start line.

However, Either[A, B] does indeed have a Monoid on either side if A (or
B for the other side) has a Monoid. We might define it like so:

// please excuse any type errors!
class EitherMonoid[A, B](implicit M: Monoid[A]) extends Monoid[Either[A,
B]] {
def id = Right(M.id)
def op(x: Either[A, B], y: Either[A, B]) =
x match {
case Right(a) => y.fold(_ => x, b => Right(M.op(a, b)))
case Left(b) => y
}
}

We also have a similar monoid with def id = Left(M.id). This would
finally allow us a useful filter method, however, the standard libraries
have no support for such an implementation (Scalaz does and so the
implementation I gave has filter). There are also alternative monoid
definitions that would give us "or else" behaviour, similar to
Option.orElse (which is indeed associative).

All this aside, and assuming that Scala core libraries do not intend to
support this behaviour (which afaik, is true), then it is wise to
conclude that Either.filter cannot exist (and so should not).

I hope this is a decent balance of "handwaviness" to make the point to
help you out with understanding.

Please also note that I have given up on pursuing improvements for
scala.Either, preferring instead to just get on with fixing it myself
with peer review, so I'm only intending to provide further understanding
-- not argue in favour (or against) the original proposal.

[Rob Dickens]

Tony, Thank you for the explanation.

Without managing to follow everything you've said, I think I get the following:

* there _is_ after all a way to implement an Either which has a
properly defined filter (or withFilter) method

* however, that implementation would also require changes to the rest
of the Scala library [and compiler?]

* those changes are unlikely (ever) to be made.

Also (please correct me if I'm wrong), if changes to the compiler
would indeed be required, even your proposed scalaz.Either, with
proper filter, wouldn't support 'if' or pattern-matching in
for-comprehensions.

So it looks like we either (that word keeps cropping up),

* keep the proposed withFilter method, and with it, the use of 'if'
and pattern-matching in for-comprehensions involving Either

* or drop it, and keep our consciences clear.

What I could do is to change the proposal so as to make adding the
withFilter (to Either, LeftProj and RightProj) an option, given Tony's
argument against it.

Rob

[Rob Dickens]

Draught SIP now

* explains why it's aToB: Right.Convert => BB instead of aToB: A => BB

* has a reference to Tony's objection to having the filter.

https://github.com/robcd/scala.github.com/blob/master/sips/pending/_posts/2012-06-29-fixing-either.md

Also, have added a couple of tests to clarify how the tuple depends on
the definitions (in for-comprehensions):

test("map - Right, def, false")
test("map - Right, def, false 2")
test("map - Right, def, false 3")

https://github.com/robcd/scala-either-proj-map-returns-proj/blob/add_right-bias_2-10_withFilter/src/test/scala/rightbiased_Tests_with_if.scala

[Tony Morris]

On 02/07/12 21:41, Rob Dickens wrote:
> Draught SIP now
>
> * explains why it's aToB: Right.Convert => BB instead of aToB: A => BB
>
> * has a reference to Tony's objection to having the filter.
>
> https://github.com/robcd/scala.github.com/blob/master/sips/pending/_posts/2012-06-29-fixing-either.md
>
> Also, have added a couple of tests to clarify how the tuple depends on
> the definitions (in for-comprehensions):
>
> test("map - Right, def, false")
> test("map - Right, def, false 2")
> test("map - Right, def, false 3")
>
> https://github.com/robcd/scala-either-proj-map-returns-proj/blob/add_right-bias_2-10_withFilter/src/test/scala/rightbiased_Tests_with_if.scala
>
> On Sun, Jul 1, 2012 at 2:47 PM, Rob Dickens <robcd...@gmail.com> wrote:
>> Tony, Thank you for the explanation.
>>
>> Without managing to follow everything you've said, I think I get the following:
>>
>> * there _is_ after all a way to implement an Either which has a
>> properly defined filter (or withFilter) method

Correct.

>> * however, that implementation would also require changes to the rest
>> of the Scala library [and compiler?]

Just the library. Of course, I can think of lots of compiler
improvements as a flow-on, but that's just a pipe-dream.

>> * those changes are unlikely (ever) to be made.

I can only speculate here of course. Personally, I do not expect to see
Monoid any time soon and if I do, I really really really really really
hope, pray, wish, scream that it is split into Semigroup, then Monoid
and also that any "discussion" about why this is a good idea is not
endless or tangential.

trait Semigroup[A] { def op(a1: A, a2: A): A }
trait Monoid[A] extends Semigroup[A] { def id: A }

This also corresponds to Scala's built-in syntax for semi-monads
(flatMap+map).

I digress.

>> Also (please correct me if I'm wrong), if changes to the compiler
>> would indeed be required, even your proposed scalaz.Either, with
>> proper filter, wouldn't support 'if' or pattern-matching in
>> for-comprehensions.
>>
>> So it looks like we either (that word keeps cropping up),
>>
>> * keep the proposed withFilter method, and with it, the use of 'if'
>> and pattern-matching in for-comprehensions involving Either
>>
>> * or drop it, and keep our consciences clear.

Drop it, because it is not useful.

HTH.

[Rob Dickens]

>> ... the proposed withFilter ...

>
> Drop it, because it is not useful.

Er, 'if' and refutable pattern-matching in for-comprehensions?

Please could you explain (in simplified terms) what a properly
supported filter would be able to do that _would_ be useful (that
would justify the changes to the Scala library that you're calling
for).

[Lars Hupel]

> If the for-comprehension involves a definition, B is found to be a
> tuple2 (whose first field is the b that the definition refers to, and
> whose second field is the value of the definition). If there are two
> definitions, B is found to be a tuple3, and so on.

After reading this explanation and your updated SIP, I can see why `B`
won't work. However, using `Any` instead of that (or something which
wraps `Any`) is a show-stopper, because it's very unlikely that such a
conversion from `Any` to `AA` can do anything useful.

[Rob Dickens]

> using `Any` ... is a show-stopper, because it's very unlikely that such a

> conversion from `Any` to `AA` can do anything useful.

Lars, Thanks for scrutinising this.

Although I wouldn't call it quite that (since the test suites work
okay), it does look as though we could, and probably should, retain
the type of the value that goes into the Left.Convert (or
Right.Convert).

So I tried replacing

object Left/Right { case class Convert(any: Any) }

with

object Left { case class Convert[+B](b: B) }
object Right { case class Convert[+A](a: A) }

and found that I needed to supply multiple conversions in the test suites,

implicit def f(convert: Left.Convert[Option[Int]]) = convert.b.toString
implicit def g(convert: Left.Convert[Either[String, Int]]) =
convert.b.toString
implicit def f(convert: Left.Convert[Int]) = convert.b.toString
implicit def g(convert: Left.Convert[(Int, Int)]) = convert.b.toString
implicit def h(convert: Left.Convert[(Int, Double, Int)]) = convert.b.toString

where previously only one sufficed:

implicit def f(convert: Left.Convert) = convert.any.toString

However, I now realise that actual code (as opposed to test suites) is
only likely to involve one for-comprehension involving Either, which
will only require one implicit conversion, which might as well retain
the type of the value to be converted.

Furthermore, I've just realised that implicit conversions can be
polymorphic! (So test suites are back to using just one conversion.)

Therefore, I've taken the liberty of applying the above change to the
add_right-bias_2-10_withFilter branch, after first tagging it with
'Convert_any':

https://github.com/robcd/scala-either-proj-map-returns-proj/tree/add_right-bias_2-10_withFilter

Also, I've rewritten the discussion around the withFilter method in
the draught SIP:

https://github.com/robcd/scala.github.com/blob/master/sips/pending/_posts/2012-06-29-fixing-either.md

Rob

[Rob Dickens]

Working through the latest chapters of Tony et al.'s Functional
Programming in Scala book, I notice that the section on Either (4.3.3)
defines Left and Right using Nothing,

final case class Left[+A](a: A) extends Either[A, Nothing] { ... }

vs the Scala lib's

final case class Left[+A, +B](a: A) extends Either[A, B] { ... }

If anyone's interested, the same change may be made to the trial
version of the 'fixed' Either, and all tests still pass.

The main pro appears to be that Left and Right become 'as simple as
possible (but no simpler)'.

One sizeable con might be that changing Left[+A, +B] to Left[+A]
raises backwards-compatibility issues.

Can anyone spot any other implications of this change?

Rob