Type L is in contravariant position in type A => Either[L, B]

Question

I tried to write simple implementation of flatMap for Either

sealed trait Either[+L, +R] {
  def flatMap[B](f: R => Either[L, B]): Either[L, B] = this match {
    case Left(e) => Left(e)
    case Right(e) => f(e)
  }
}

final case class Right[+A, +B](right: B) extends Either[A, B]
final case class Left[+A, +B](left: A) extends Either[A, B]

and faced following problem: covariant type L is in contravariant position in type f: R => Either[L, B] of value f, but why is it so? I thought that our type is in contravariant position when we take variant type as an argument for function and it has nothing to do with a type declaration

Answer 1

You can think of R => Either[L, B] as a "generalized value of type L" - it's not exactly the same thing as an L, but given an R it might produce an L. So, your flatMap "consumes generalized values of type L". At the same time, your variance declaration claims that Either[+L, +R] is covariant in L, therefore, an Either[VerySpecial, R] would have to be a special case of Either[RatherGeneral, R]. But this is impossible, because the flatMap that can consume only VerySpecial values would choke on a RatherGeneral input.

• In Either[+L, +R], L is in covariant position (it "produces" Ls, at least sometimes)
• In R => Either[L, B], L is still in covariant position (because the function produces Either[L, B], and Either[L, B] in turn produces Ls, so the whole thing produces Ls)
• In (R => Either[L, B]) => Either[L, B], the first L appears in contravariant position, because the argument part is consumed by the method flatMap.

This is easily fixed with the standard lower-type-bounds trick:

sealed trait Either[+L, +R] {
  def flatMap[B, M >: L](f: R => Either[M, B]): Either[M, B] = this match {
    case Left(e) => Left(e)
    case Right(e) => f(e)
  }
}

final case class Right[+A, +B](right: B) extends Either[A, B]
final case class Left[+A, +B](left: A) extends Either[A, B]