Problem with given instances writing MTL style code with Scala cats

Question

I am trying to write some Scala code to have custom behaviour in an mtl style. For example, in order to expose the "write to DB" functionality abstracting over the specific effect I wrote my own type class:

trait CanPersist[M[_]]:
  def persistToDB[A](a: A): M[Unit]

given CanPersist[IO] with
  def persistToDB[A](a: A): IO[Unit] = IO(???) // Write to DB

The IO instance can be easily implemented but what I'm interested in is automatically providing the instance for any IO-based monad stack:

// If a Transformer wraps a Monad that can persist then it can persist too
given persistTA[M[_]: CanPersist: Monad, T[_[_], _]: MonadTransformer]:
  CanPersist[[A] =>> T[M, A]] with 
  def persistToDB[A](a: A): T[M, Unit] =
    summon[MonadTransformer[T]].lift(summon[CanPersist[M]].persistToDB(a))

The problem is apparently cats does not define its own MonadTransformer type class; luckily its pretty straightforward to write your own:

trait MonadTransformer[T[_[_], _]]:
  def lift[M[_]: Monad, A](ma: M[A]): T[M, A]

// A Monad Transformer is a Monad if it wraps a Monad
given monadTA[M[_]: Monad, T[_[_], _]: MonadTransformer]: Monad[[A] =>> T[M, A]] with
  def pure[A](a: A): T[M, A] = ??? // implementations are not relevant
  def flatMap[A, B](fa: T[M, A])(f: A => T[M, B]): T[M, B] = ???
  def tailRecM[A, B](a: A)(f: A => T[M, Either[A, B]]): T[M, B] = ???

// Both WriterT and EitherT are Monad Transformers
given writerMT[L: Monoid]: MonadTransformer[[M[_], A] =>> WriterT[M, L, A]] with 
  def lift[M[_]: Monad, A](ma: M[A]): WriterT[M, L, A] =
    WriterT.liftF(ma)

given eitherMT[Err]: MonadTransformer[[M[_], A] =>> EitherT[M, Err, A]] with 
  def lift[M[_]: Monad, A](ma: M[A]): EitherT[M, Err, A] =
    EitherT.liftF(ma)

And now onto the code that actually uses the CanPersist functionality:

def saveIntString[M[_]: Monad]
  (int: Int, string: String)
  (using P:CanPersist[M])
  : M[String] =
  for {
    _ <- P.persistToDB(int)
    _ <- P.persistToDB(string)
  } yield "done"

val res: WriterT[IO, String, String] = saveIntString(2, "test")
// Does not compile:
// no implicit argument of type CanPersist[M] was found for parameter P of method saveIntString
// where:    M is a type variable with constraint <: [V] =>> cats.data.WriterT[cats.effect.IO, String, V]
// I found:
//    persistTA[M, T]
// But given instance persistTA does not match type CanPersist[M].

The problem is the compiler apparently can not derive the correct instances; this confuses me though. I thought the compiler would be able to derive the correct instance:

• WriterT has a Transformer instance
• IO has a CanPersist instance
• Since WriterT is a Transformer and IO a monad that can persist WriterT[IO, _, _] should also have a CanPersist instance Is there a way to define the described Transformer typeclass this way? Can the compiler derive such instances or is it impossible in Scala?

Generalissimo

Answer 1

Problems with inference seem to be one of the reasons why the particular MTL implementation that you linked is relying on traits such as MonadPartialOrder instead of MonadTransformer-typeclasses.

Basically, what happens here is this: When you want to get from F to G

• The MonadPartialOrder-approach asks for a bridge from F to G
• Your approach asks to deconstruct G into [X] =>> T[M, X], then find a fancy universal bridge-builder T, and then use that contraption to build a bridge from F to ([X] =>> T[M, X]).

Thus, cats.mtl's approach is much simpler, and far less demanding of the inference algorithm. That's why cats.mtl works, whereas your approach doesn't.

---

I'll first sketch how your example can be fixed, then I'll speculate a little about why your approach does not work.

A solution with MonadPartialOrder

Here is how I'd try to approach your problem using the MonadPartialOrder from cats.mtl:

import cats.data.WriterT
import cats.syntax.all._
import cats.mtl.MonadPartialOrder

trait CanPersist[M[_]]:
  def persistToDB[A](a: A): M[Unit]

given CanPersist[IO] with
  def persistToDB[A](a: A): IO[Unit] = IO(???) // Write to DB

given persistTA[F[_]: CanPersist: Monad, G[_]]
  (using mpo: MonadPartialOrder[F, G]): CanPersist[G] with 
    def persistToDB[A](a: A): G[Unit] =
      mpo(summon[CanPersist[F]].persistToDB(a))

def saveIntString[M[_]: Monad]
  (int: Int, string: String)
  (using P:CanPersist[M])
  : M[String] =
  for {
    _ <- P.persistToDB(int)
    _ <- P.persistToDB(string)
  } yield "done"

def res: WriterT[IO, String, String] = saveIntString(2, "test")

@main def main(): Unit =
  println("Run it with 'sbt clean compile run'")

The basic idea is to use MonadPartialOrder[F, G] to get from F to G, instead of requiring a MonadTransformer[T] to get from F to [X] =>> T[F, X].

This compiles and runs just fine on Scala 3.1.2, here is a complete build.sbt, if you want to try it out:

import Dependencies._

ThisBuild / scalaVersion     := "3.1.2"
ThisBuild / version          := "0.1.0-SNAPSHOT"
ThisBuild / organization     := "com.foobarbaz"
ThisBuild / organizationName := "example"

lazy val root = (project in file("."))
  .settings(
    name := "cats-mtl-so-question-72407103",
    scalacOptions += "-explaintypes",
    libraryDependencies += scalaTest % Test,
    libraryDependencies += "org.typelevel" %% "cats-core" % "2.7.0",
    libraryDependencies += "org.typelevel" %% "cats-mtl" % "1.2.1",
    libraryDependencies += "org.typelevel" %% "cats-effect" % "3.4-389-3862cf0",
  )

Why your approach does not work

The logic in your explanation seems fine to me, so I would say that the compiler currently cannot infer the required typeclasses. The reason why your solution does not work (whereas cats.mtl does), is that your solution is attempting to work at a higher level of abstraction than cats.mtl does.

The problem that an average MTL implementation is usually trying to solve looks somewhat like this:

For a fixed property P and two fixed monads LameMonad and FancyMonad, find a way to lift P from the LameMonad to the FancyMonad.

This is done for a few useful properties P (such as that you can Ask, Tell, access and mutate Stateful stuff and so on), and a reasonable amount of different combinations of LameMonad and FancyMonad, with the fancy monads usually arising from the lame monads by applying some monad transformer (such as those from cats.data._). Note how the the quantifiers "for a few", "for a reasonable amount" appear in the metadiscussion outside of the problem statement that we're trying to solve automatically.

Now, contrast this to your code, where you greet the compiler with the following signature:

given monadTA[M[_]: Monad, T[_[_], _]: MonadTransformer] // ... etc

The contextual bound : MonadTransformer demands that the compiler solves a problem that looks roughly like

For a fixed T, find a unique constructive proof that for all monads M, [X] => T[M, X] is also a monad.

Note how the for all quantifier has now slipped into the problem statement of the task we are trying to automate, and also note that now the compiler is somehow supposed to infer the "right" way to match a higher kind Foo against [A] =>> T[M, A] with a higher-kinded M.

The task of matching against [A] =>> T[M, A] is tricky (thanks to subclassing / inheritance even trickier than in Haskell), and actually somewhat ill-defined. For example, WriterT[IO, String, V] can be decomposed in multiple ways: is it

[X[_], Y] =>> WriterT[X, String, Y] applied to IO and V

or is it

[X[_], Y] =>> WriterT[IO, Y, X[V]] applied to Id[_] and String

or is it any other combination? Some conventions (taking the rightmost argument first etc.) seem to work in most common cases, but apparently not in your particular case.

So, without being able to tell for sure, I assume that all those universal quantifications over higher kinds somehow manage to confuse the compiler badly enough that the approach becomes impractical. I also assume that this is one of the reasons why cats.mtl is using MonadPartialOrder instead of MonadTransformer-typeclasses: the MonadPartialOrder[F, G] tells you just that you can do with G anything you can do with F, for two fixed monads F and G. The kinds of both parameters are * -> *, which is much more benign than all those higher-kinded [X[_], Y] =>> Z[X, Y]-lambdas.

So, to reiterate, MTL is doing this:

For a few selected `P`, `F`, `G`, solve problem: "lift P from F to G"
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  ^^^^^^^^^^^^^^^^^^
meta-level, interpreted by humans                 easy for compiler

whereas you are attempting something closer to this (waves hands handwavily):

For a fixed `P`, solve: "for all `F`, `G`, lift `P` from `F` to `G`"
^^^^^^^^^^^^^^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
meta-level, easy                 too hard for the compiler

which is sufficient, but not necessary (and therefore unnecessarily hard for the compiler).

Higinbotham