Type inference regression with implicit extension methods.

[LukaJCB]

Minimized code

trait Monad[F[_]]

case class StateT[F[_], S, A](run: S => F[(S, A)])

implicit class MonadOps[F[_], A](private val fa: F[A]) extends AnyVal {
  def whileM_(p: F[Boolean])(implicit M: Monad[F]): F[Unit] = ???
}

def inspect[F[_], S, A](f: S => A)(implicit F: Monad[F]): StateT[F, S, A] = ???

type Id[A] = A

implicit def stateTMonad[F[_]: Monad, S]: Monad[[X] =>> StateT[F, S, X]] = ???
implicit def idMonad: Monad[Id] = ???

def increment: StateT[Id, Int, Unit] = ???

increment.whileM_(inspect(i => i > 4)).run(3)

Output

value > is not a member of Any, but could be made available as an extension method.

One of the following imports might make progress towards fixing the problem:

  import math.Ordered.orderingToOrdered
  import math.Ordering.Implicits.infixOrderingOps

no implicit argument of type Monad[([X0] =>> StateT[Id, Int, X0] | StateT[[A] =>> A, Any, X0])] was found for parameter M of method whileM_ in class MonadOps.
I found:

    main$package.stateTMonad[F, S]

But method stateTMonad does not match type Monad[([X0] =>> StateT[Id, Int, X0] | StateT[[A] =>> A, Any, X0])].

Expectation

This should compile fine as it does in Scala 2.

[smarter]

So I've spent a while staring at this and I think this isn't fixable unfortunatel (skip to the bottom of this message for some actual suggestions on what to do). It can be reduced to:

trait Monad[F[_]]

class ST[A, B]

class MonadOps[M[_], A](ma: M[A]) {
  def whileM_(p: M[Boolean]): M[Unit] = ???
}

object Test {

  def inspect[C, D](f: C => D): ST[C, D] = ???

  val increment: ST[Int, Unit] = ???

  new MonadOps(increment).whileM_(inspect(i => i > 4))
}

In the last expression, we start by typing the new call which gives us:

new MonadOps[?M, ?A](increment)
where
  ?M >: [X] =>> ST[Int, X]
  ?A := Unit

Because we only constrained one bound of ?M, it turns out that there isn't information here to deduce that the binder i of the lambda should have type Int. The details are a bit complicated but it's more or less equivalent to:

object Test {
  def foo[A >: List[B], B](x: A)(y: B => Boolean): Unit = ???

  val li: List[Int] = ???
  foo(li)(x => x > 0) // error
}

Intuitively, we'd probably like to infer B := Int to type the lambda, but that information isn't there in the constraints:

?A >: List[?B] | List[Int]

If we were to instantiate ?A, we would try to simplify the union and therefore set ?B := Int, but at the point where we try to type the lambda, we haven't instantiated ?A yet and have no reason to do so.

So why does the original example work in Scala 2? I haven't investigated in details but I suspect it's just because Scala 2 will eagerly instantiate ?M := [X] =>> ST[Int, X] after typing new MonadOps(increment), from which we can deduce that i must have type Int, but doing this can break other usecases, for example the following works in Dotty but not Scala 2:

class Bar[+B, A]

object Test {
  def foo[F[_]](x: F[Int])(y: F[Int]): F[Unit] = ???


  val z = foo(new Bar[String, Int])(new Bar[Int, Int])
  // Result type is Bar[String | Int, Unit]
}

---

OK, so what can be done in cats concretely to deal with this? Let's look again at the original extension method:

implicit class MonadOps[F[_], A](private val fa: F[A]) extends AnyVal {
 def whileM_(p: F[Boolean])(implicit M: Monad[F]): F[Unit] = ???
}

The interesting thing is that we don't really need to type the parameter p of whileM_ to determine F, since it should already be completely dermined from fa, so I think we could just as well run the implicit search before searching for p:

implicit class MonadOps[F[_], A](private val fa: F[A]) extends AnyVal {
 def whileM_(using M: Monad[F])(p: F[Boolean]): F[Unit] = ???
}

And as if by magic, everything typechecks now! This works because doing the implicit search on F forces us to actually instantiate it to F := [X] =>> StateT[Id, Int, X], so F[Boolean] is just StateT[Id, Int, Boolean] and typing the lambda is easy.

I was hoping that using an actual Dotty extension method would also work:

trait Monad[F[_]] {
  extension [A] (fa: F[A]) def whileM_(p: F[Boolean]): F[Unit] = ???
}

But that doesn't seem to work, haven't investigated why yet.

Anyway, I'll leave this issue open for a few days but will probably close it as won't fix afterwards.

[LukaJCB]

Any idea if I can run implicit search before searching for p with Scala 2 compatible syntax?

[smarter]

Yes, but it'll cost an allocation:

  implicit class MonadOps[F[_], A](private val fa: F[A]) extends AnyVal {
    def whileM_(implicit M: Monad[F]): F[Boolean] => F[Unit] = ???
  }

It also breaks binary compatibility so not really an option for cats, I think separate source files for the scala 2 and 3 versions can't be avoided.

[joroKr21]

That won't work without using .apply explicitly, but you could add the implicit parameter to the implicit class (and drop AnyVal) or as unused parameter to an implicit conversion that returns the value class.

[LukaJCB]

Okay cool, thanks for your help!

[odersky]

Seems there's nothing we can do in the short term about this