Why can't the compiler figure out (_ >: T) => (_ <: V[_ <: U]) <: T => V[U] for V[+_]?

209 views Asked by At

So I was playing around a bit, trying to write something on existentials and variance, and I came across this interesting piece of code.

final case class Box[+T](val value: T) {
  def >>=[U](f: T => Box[U]) = f(value)
  def flatMap[U](f: (_ >: T) => (_ <: Box[_ <: U])): Box[U] = this >>= f
}

This fails to compile:

Variance.scala:3: no type parameters for method >>=: (f: T => Box[U])Box[U] exist so that it can be applied to arguments (_$1 => _$2)
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : _$1 => _$2 where type _$2 <: Box[_ <: U], type _$1 >: T
 required: T => Box[?U]
  def flatMap[U](f: (_ >: T) => (_ <: Box[_ <: U])): Box[U] = this >>= f
                                                                   ^
Variance.scala:3: type mismatch;
 found   : _$1 => _$2 where type _$2 <: Box[_ <: U], type _$1 >: T
 required: T => Box[U]
  def flatMap[U](f: (_ >: T) => (_ <: Box[_ <: U])): Box[U] = this >>= f
                                                                       ^

which I find strange, as isn't (_ >: T) => (_ <: Box[_ <: U]) a subtype of T => Box[U]? Because Function1 is contravariant in the first type parameter, this is a subtype of T => (_ <: Box[_ <: U]). Since Function1 is covariant in the result type, this is a subtype of T => Box[_ <: U], and since Box is covariant in its parameter, isn't the entire thing a subtype of T => Box[U]?

Strangely, changing the code to

// This change is not required ;)
type Box[T] = `What A Category Theorist Calls "The Identity Monad" And What Everyone Else Calls "A Box"`[T]
final case class `What A Category Theorist Calls "The Identity Monad" And What Everyone Else Calls "A Box"`[+T](val value: T) {
  def >>=[U](f: T => Box[U]) = f(value)
  def flatMap[U](f: (_ >: T) => (_ <: Box[_ <: U])): Box[U] = this >>= (f: T => Box[U])
}

with a type ascription to "hint" the compiler that f: T => Box[U] makes it compile. Since there's no implicit conversion or variable declaration here shouldn't this have made no difference?

The other way I found of getting this to compile is writing

def flatMap[U](f: (_ >: T) => (_ <: Box[_ <: U])): Box[U] = this.>>=[U](f)

This makes me believe that the issue is less with the compiler having a hard time getting that (_ >: T) => (_ <: Box[_ <: U]) <: T => Box[U] and more with it not being able to infer the type parameter of >>=, which seems to be what the error message is alluding to.

(Using Scala 2.12.1 (with sbt, if that changes anything))

1

There are 1 answers

4
Cullen On
final case class Box[+T](val value: T) {
  def >>=[U](f: T => Box[U]) = f(value)
  def flatMap[U](f: (_ >: T) => (_ <: Box[_ <: U])): Box[U] = this >>= f
}

flatMap retrun type is Box[U], but to use this >>= f.

So >>= will automatic to change to f type (_ >: T) => (_ <: Box[_ <: U]).

So Box[(_ >: T) => (_ <: Box[_ <: U])] not match Box[U].

I think you can change like that:
def flatMap[U](f: (_ >: T) => (_ <: Box[_ <: U])): Box[U] = this >>=[U] f