Scala type inference rule over contravarience?

Question

I'm using Circe and noticed something that i am not so confortable with and would like to understand what is going on under the hood ?

Fundamentally it is not really a circe issue. Also i was just playing with circe around to test few thing. So could have decoded in JsonObject straight but that is beside the point.

val jobjectStr = """{
    |    "idProperty": 1991264,
    |    "nIndex": 0,
    |    "sPropertyValue": "0165-5728"
    |  }""".stripMargin



val jobject = decode[Json](jobjectStr).flatMap{ json =>
    json.as[JsonObject]
}

My issue is with the flapMap signature of Either, contravariance and what is happening here:

We have the following types:

decode[Json](jobjectStr): Either[Error, Json]

json.as[JsonObject]: Decoder.Result[JsonObject]

where circe defines

final type Result[A] = Either[DecodingFailure, A]

and

sealed abstract class DecodingFailure(val message: String) extends Error {

Now the signature of flatMap in either is:

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

In other words, talking only about type it is like my code is doing

Either[Error, Json] flatMap Either[DecodingFailure, JsonObject]

Hence my issue is: DecodingFailure >: Error is not true

And Indeed the type of the full expression is:

decode[Json](jobjectStr).flatMap{ json =>
    json.as[JsonObject]
}: Either[Error, JsonObject]

Hence i'm confused, because my understanding is that the type of the first Parameter of Either is Contravariant in the flatMap Signature. Here there seems to be some wierd least upper bound inferencing going on ... But i am not sure why or if it is even the case.

Any explanation ?

Answer 1

So first of all, we need to understand that the compiler will always try to infer types that allow compilation. The only real way to avoid something to compile is to use implicits.
(not sure if this is part of the language specification, or a compiler implementation detail, or something common to all compilers, or a bug or a feature).

Now, let's start with a simpler example List and ::.

sealed trait List[+A] {
  def ::[B >: A](b: B): List[B] = Cons(b, this)
}

final case class Cons[+A](head: A, tail: List[A]) extends List[A]
final case object Nil extends List[Nothing]

So, assuming the compiler will always allow some code like x :: list will always compile. Then, we have three scenarios:

1. x is of type A and list is a List[A], so it is obvious that the returned value has to be of type List[A].
2. x is of some type C and list is a List[A], and C is a subtype of A (C <: A). Then, the compiler simply upcast x to be of type A and the process continues as the previous one.
3. x is of some type D and list is a List[A], and D is not a subtype of A. Then, the compiler finds a new type B which is the LUB between D and A, the compiler finally upcast both x to be of type B and list to be a List[B] (this is possible due covariance) and proceeds like the first one.
   Also, note that due to the existence of types like Any and Nothing there is "always" a LUB between two types.

Now let's see Either and flatMap.

sealed trait Either[+L, +R] {
  def flatMap[LL >: L, RR](f: R => Either[LL, RR]): Either[LL, RR]
}

final case class Left[+L](l: L) extends Either[L, Nothing]
final case clas Right[+R](r: R) extends Either[Nothing, R]

Now, assuming my left side is an Error, I feel this behaviour of returning the LUB between the two possible lefts is the best, since at the end I would have the first error, or the second error or the final value, so since I do not know which of the two errors it was then that error must be of some type that encapsulates both possible errors.