Missing given instance for EitherT using type alias

[jorolicht]

Compiler version

val scala3Version = "3.3.3"
with cats core library
libraryDependencies += "org.typelevel" %% "cats-core" % "2.12.0"

import scala.concurrent.{ Future, ExecutionContext }
import scala.concurrent.ExecutionContext.Implicits.global
import cats.data.EitherT
import cats.syntax.all._

type FuEiErr[T] = Future[Either[Error, T]]

case class Error(msg: String)
def fA(x:Int): FuEiErr[Int] = Future(Right(x)) 
def fB(x:Int): FuEiErr[Int] = Future(Right(x))  

@main def TestEitherT(): Unit = 
  (for 
    a  <- EitherT(fA(7))
    b  <- EitherT(fB(42))
  yield a+b).value.map {
    case Left(err)  => println(s"Error: ${err.msg}")
    case Right(res) => println(s"Result: ${res}")
  }

Output

[error] -- [E172] Type Error: ...src/main/scala/Main.scala:16:11 
[error] 16 |  yield a+b).value.map {
[error]    |           ^
[error]    |No given instance of type cats.Functor[[X0] =>> scala.concurrent.Future[Either[Error, X0] | X0]] was found for parameter F of method map in class EitherT

Expectation

No compilation error, works in version 2.13

[Gedochao]

The same repro with Scala CLI:

//> using dep org.typelevel::cats-core:2.12.0
import scala.concurrent.{ Future, ExecutionContext }
import scala.concurrent.ExecutionContext.Implicits.global
import cats.data.EitherT
import cats.syntax.all._

type FuEiErr[T] = Future[Either[Error, T]]

case class Error(msg: String)
def fA(x:Int): FuEiErr[Int] = Future(Right(x))
def fB(x:Int): FuEiErr[Int] = Future(Right(x))

@main def TestEitherT(): Unit =
  (for
    a  <- EitherT(fA(7))
    b  <- EitherT(fB(42))
  yield a+b).value.map {
    case Left(err)  => println(s"Error: ${err.msg}")
    case Right(res) => println(s"Result: ${res}")
  }

[Gedochao]

We need to minimize this without the cats-core dependency.
@jorolicht would you be able to help?

[jorolicht]

We need to minimize this without the cats-core dependency. @jorolicht would you be able to help?

well, try to do so

[jorolicht]

Have to add/copy some code from the cats library, hope this helps:

import scala.concurrent.{ Future, ExecutionContext }
import scala.concurrent.ExecutionContext.Implicits.global

type FuEiErr[T] = Future[Either[Error, T]]

case class Error(msg: String)
def fA(x:Int): FuEiErr[Int] = Future(Right(x)) 
def fB(x:Int): FuEiErr[Int] = Future(Right(x))  

implicit def monadInstancesForFuture(implicit ec: ExecutionContext): Monad[Future] =
  new Monad[Future] {
    def pure[A](x: A): Future[A] = Future.successful(x)
    def flatMap[A, B](fa: Future[A])(f: A => Future[B]): Future[B] = fa.flatMap(f)
  }  

implicit def functorInstancesForFuture(implicit ec: ExecutionContext): Functor[Future] =
  new Functor[Future] { def map[A, B](fa: Future[A])(f: A => B): Future[B] = fa.map(f) }  
  
object EitherUtil:
  def leftCast[A, B, C](right: Right[A, B]): Either[C, B] =
    right.asInstanceOf[Either[C, B]]
  def rightCast[A, B, C](left: Left[A, B]): Either[A, C] =
    left.asInstanceOf[Either[A, C]]
  val unit = Right(())

trait FlatMap[F[_]]:
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]

trait Functor[F[_]] { self =>
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

trait Monad[F[_]] extends FlatMap[F]: 
  def map[A, B](fa: F[A])(f: A => B): F[B] = flatMap(fa)(a => pure(f(a)))
  def pure[A](x: A): F[A]  
  
final case class EitherT[F[_], A, B](value: F[Either[A, B]]):
  def flatMap[AA >: A, D](f: B => EitherT[F, AA, D])(implicit F: Monad[F]): EitherT[F, AA, D] =
    EitherT(F.flatMap(value) {
      case l @ Left(_) => F.pure(EitherUtil.rightCast(l))
      case Right(b)    => f(b).value
    })   
  def map[D](f: B => D)(implicit F: Functor[F]): EitherT[F, A, D] = bimap(identity, f)  
  def bimap[C, D](fa: A => C, fb: B => D)(implicit F: Functor[F]): EitherT[F, C, D] =
    EitherT(
      F.map(value) {
        case Right(b) => Right(fb(b))
        case Left(a)  => Left(fa(a))
      }
    )  


@main def TestEitherT(): Unit = 
  (for 
    a  <- EitherT(fA(21))  // EitherT[Future,Error,Int](fA(21))  //ok
    b  <- EitherT(fB(21))  // EitherT[Future,Error,Int](fB(21))  //ok
  yield a+b).value.map {
    case Left(err)  => println(s"Error: ${err.msg}")
    case Right(res) => println(s"Answer: ${res}")
  }

[jorolicht]

cleaner code for demo:

import scala.concurrent.{ Future, ExecutionContext }
import scala.concurrent.ExecutionContext.Implicits.global
import scala.util.{Either, Left, Right}


type FuEiErr[T] = Future[Either[String, T]]
def fA(x:Int): FuEiErr[Int] = Future.successful(Right(x)) 
def fB(x:Int): FuEiErr[Int] = Future.successful(Right(x))  

case class EitherT[F[_], A, B](value: F[Either[A, B]]):
  def map[C](f: B => C)(using functor: Functor[F]): EitherT[F, A, C] = {
    EitherT(functor.map(value)(_.map(f)))
  }

  def flatMap[C](f: B => EitherT[F, A, C])(using monad: Monad[F]): EitherT[F, A, C] = 
    EitherT(monad.flatMap(value) {
      case Left(a) => monad.pure(Left(a))
      case Right(b) => f(b).value
    })

trait Functor[F[_]]:
  def map[A, B](fa: F[A])(f: A => B): F[B]

trait Monad[F[_]] extends Functor[F]:
  def pure[A](a: A): F[A]
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def map[A, B](fa: F[A])(f: A => B): F[B] = flatMap(fa)(a => pure(f(a)))


// Example instances for Future
given futureMonad(using ec: ExecutionContext): Monad[Future] = new Monad[Future] {
  def pure[A](a: A): Future[A] = Future.successful(a)
  def flatMap[A, B](fa: Future[A])(f: A => Future[B]): Future[B] = fa.flatMap(f)
}


@main def TestEitherT(): Unit = 
  (for 
    a  <- EitherT(fA(21))  // error
    b  <- EitherT(fB(21))  // error
    // a  <- EitherT[Future,String,Int](fA(21))  //ok
    // b  <- EitherT[Future,String,Int](fB(21))  //ok
  yield a+b).value.map {
    case Left(msg)  => println(s"Error: ${msg}")
    case Right(res) => println(s"Answer: ${res}")
  }
``

[road21]

We have faced with similar issue when trying to use syntax for F[Either[..]].
The example above can be reduced to:

trait TCl[F[_]]

extension [F[_], A](e: F[Option[A]]) def boo(using ev: TCl[F]): Unit = ()

type Result[F[_], A] = F[Option[A]]

given t: TCl[Option] = new TCl[Option] {}

val b: Result[Option, Int] = None
b.boo // No given instance of type Playground.TCl[[X0] =>> Option[Option[X0] | X0]] was found for parameter ev of method

scastie: https://scastie.scala-lang.org/road21/6dblHcs1RpSrkK4JrnEPAQ

Also I want to note that:

1. Similar code works in scala 2.13.5

trait TCl[F[_]]

implicit class Stx[F[_], A](e: F[Option[A]]) {
  def boo(implicit ev: TCl[F]): Unit = ()
}

type Result[F[_], A] = F[Option[A]]

implicit val t: TCl[Option] = new TCl[Option] {}

val b: Result[Option, Int] = None 
b.boo // ok

scastie: https://scastie.scala-lang.org/road21/6dblHcs1RpSrkK4JrnEPAQ/5

2. As ugly workaround the following works:

trait TCl[F[_]]

extension [F[_], A, X](e: X)(using X =:= F[Option[A]])
  def boo(using ev: TCl[F]): Unit = ()

type Result[F[_], A] = F[Option[A]]

implicit val t: TCl[Option] = new TCl[Option] {}

val b: Result[Option, Int] = None 
b.boo // ok

scastie: https://scastie.scala-lang.org/road21/6dblHcs1RpSrkK4JrnEPAQ/8

[mbovel]

I could reproduce the above minimization. It indeed passes with 2.13 but fails with 3.6.2:

package issue20519

object Main {
  trait TCl[F[_]]

  implicit class Stx[F[_], A](e: F[Option[A]]) {
    def boo(implicit ev: TCl[F]): Unit = ()
  }

  type Result[F[_], A] = F[Option[A]]

  implicit val t: TCl[Option] = new TCl[Option] {}

  def main(args: Array[String]): Unit = {
    val b: Result[Option, Int] = None 
    b.boo // fails in 3.6.2, passes in 2.13

    // works without the alias:
    val b2: Option[Option[Int]] = None
    b2.boo // ok
  }
}

➜  ~/scala-snippets-6 scala -S 2.13 issue20519.scala
Compiling project (Scala 2.13.15, JVM (21))
Compiled project (Scala 2.13.15, JVM (21))
➜  ~/scala-snippets-6 scala -S 3.6.2 issue20519.scala
Compiling project (Scala 3.6.2, JVM (21))
[error] ./issue20519.scala:16:10
[error] No given instance of type issue20519.Main.TCl[[X0] =>> Option[Option[X0] | X0]] was found for parameter ev of method boo in class Stx.
[error] I found:
[error] 
[error]     t
[error] 
[error] But Found:    (issue20519.Main.t : issue20519.Main.TCl[Option])
[error] Required: issue20519.Main.TCl[[X0] =>> Option[Option[X0] | X0]].
[error]     b.boo // ok
[error]          ^
Error compiling project (Scala 3.6.2, JVM (21))
Compilation failed