Search code examples
scala

What does "Binds the given function across Right" mean?

I'm new-ish to functional programming, and I have a question about a description from the Either documentation that I'm having a really hard time wrapping my mind around.

I understand that an Either is kind of like an evolution to the Option in that an Either represents happy and sad path values with Right and Left similar to how an Option represents the presence or absence of a value with Some and None. I also understand that an Option is a special case of List, one containing either 0 or 1 values, which is why we see so many List-ish methods (map, filter, fold, etc) on the Option type, and by extension, on the Either type as well.

I also understand that, at some point, Eithers were intentionally 'right-biased' so that they could be given given a flatMap method, and that this method allows us to transform an Either[A, B] into an Either[C, D], which allows us to chain various Either computations together and this is the basis for why we're able to use Eithers in for-comprehensions.

Every time I visit the Either documentation, I see that the flatMap method has the description "Binds the given function across Right", and I have never been able to figure out what this description means. Can anyone explain it to me?

Solution

  • and that this method allows us to transform an Either[A, B] into an Either[C, D]

    This part isn't quite right. While it is true that, if we have A => C and B => D, then we can convert Either[A, B] into Either[C, D], that's not given to us by the "generalization of Option" functions you're talking about. When we speak of Either as an error-handling type (where, by convention, the error type is the left-hand argument and the "happy path" is the right-hand argument), we generally hold the left-hand argument constant. So the type we're looking at is Either[A, _], where _ can change but A is some fixed error type.

    Then we get

    def map[B1](f: (B) => B1): Either[A, B1]

    That is, our map is right-biased. It assumes the left-hand argument (the "sad path") remains the same and only the right-hand argument changes. This isn't a theoretical constraint; we could just as easily have defined map to work on the left argument. But we didn't.

    Now the word "bind", in particular, comes from Haskell. In particular, it's the usual way to pronounce the (>>=) operator defined on the Monad typeclass.

    (>>=) :: m b -> (b -> m b') -> m b'

    I won't get into all of the category-theoretical goodies, except to say that what Haskell calls (>>=) (and pronounces "bind") is what Scala calls flatMap. On Either in Haskell, (>>=) looks like this.

    (>>=) :: Either a b -> (b -> Either a b') -> Either a b'

    And flatMap on Scala's Either is defined as[1]

    def flatMap[B1](f: (B) => Either[A, B1]): Either[A, B1]

    In both cases, we take an Either[A, B] and a way to go from B to Either[A, B1], and we produce an Either[A, B1]. This operation is called "binding" the Either. And since we're binding it on the right-hand argument instead of the left-hand one (again, purely a convention, but one we choose and stick to consistently), we say we're binding on the right.

    [1] Okay, I lied a little. The full Scala type signature is

    def flatMap[A1 >: A, B1](f: (B) => Either[A1, B1]): Either[A1, B1]

    This is covering for variance annotations. A is covariant in Either[A, B], so strictly speaking we shouldn't be able to have Either[A, B1] in argument position for flatMap. But we can do this little incantation and have "Either[A1, B1] for some A1 >: A" as an argument to get basically the same idea.