Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Missing given instance for EitherT using type alias #20519

Closed
jorolicht opened this issue Jun 4, 2024 · 12 comments · Fixed by #22339
Closed

Missing given instance for EitherT using type alias #20519

jorolicht opened this issue Jun 4, 2024 · 12 comments · Fixed by #22339
Assignees
Milestone

Comments

@jorolicht
Copy link

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

@jorolicht jorolicht added itype:bug stat:needs triage Every issue needs to have an "area" and "itype" label labels Jun 4, 2024
@Gedochao
Copy link
Contributor

Gedochao commented Jun 4, 2024

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
Copy link
Contributor

Gedochao commented Jun 4, 2024

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

@Gedochao Gedochao added regression:scala2 stat:needs minimization Needs a self contained minimization and removed stat:needs triage Every issue needs to have an "area" and "itype" label labels Jun 4, 2024
@jorolicht
Copy link
Author

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

well, try to do so

@jorolicht
Copy link
Author

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
Copy link
Author

jorolicht commented Jun 5, 2024

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}")
  }
``

@Gedochao Gedochao added area:implicits related to implicits and removed stat:needs minimization Needs a self contained minimization labels Jun 5, 2024
@road21
Copy link
Contributor

road21 commented Dec 14, 2024

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

  1. 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
Copy link
Member

mbovel commented Jan 8, 2025

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

@mbovel
Copy link
Member

mbovel commented Jan 8, 2025

Same with the Scala 3 version:

package issue20519_3

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] {}

def main =
  val b: Result[Option, Int] = None
  b.boo
➜  ~/scala-snippets-6 scala -S 3.6.2 issue20519_3.scala 
Compiling project (Scala 3.6.2, JVM (21))
[error] ./issue20519_3.scala:13:3
[error] value boo is not a member of Result[Option, Int].
[error] An extension method was tried, but could not be fully constructed:
[error] 
[error]     boo[[X0] =>> Option[Option[X0] | X0], A](b)(t)
[error] 
[error]     failed with:
[error] 
[error]         No given instance of type TCl[[X0] =>> Option[Option[X0] | X0]] was found for parameter ev of method boo.
[error]         I found:
[error]         
[error]             t
[error]         
[error]         But given instance t does not match type TCl[[X0] =>> Option[Option[X0] | X0]].
[error]   b.boo
[error]   ^^^^^
Error compiling project (Scala 3.6.2, JVM (21))
Compilation failed

@mbovel
Copy link
Member

mbovel commented Jan 8, 2025

Further minimized (the extension method and the implicits are not needed):

package issue20519_3_min

trait TCl[F[_]]

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

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

@main def main =
  summon[Result[Option, Int] =:= Option[Option[Int]]]

  val ev = new TCl[Option] {}

  val b: Result[Option, Int] = None
  boo(b, ev)

  val b2: Option[Option[Int]] = None
  boo(b2, ev)
➜  ~/scala-snippets-6 scala -S 3.6.2 issue20519_3_min.scala
Compiling project (Scala 3.6.2, JVM (21))
[error] ./issue20519_3_min.scala:15:10
[error] Found:    (ev : issue20519_3_min.TCl[Option])
[error] Required: issue20519_3_min.TCl[[X0] =>> Option[Option[X0] | X0]]
[error]   boo(b, ev)
[error]          ^^
Error compiling project (Scala 3.6.2, JVM (21))
Compilation failed

@mbovel
Copy link
Member

mbovel commented Jan 10, 2025

Here are the generated constraints for the non-alias and alias cases.

Without alias

class Box[T](val value: T)

def boo[F[_], A](e: F[Box[A]]): Unit = ()

type Result[G[_], B] = G[Box[B]]

def main =
  val b: Option[Box[Int]] = ???
  boo(b)
  // boo[[X0] =>> Option[X0]](b)
added constraint F :> Option to
 uninstantiated variables: F, A
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Option
     A
 ordering:
 co-deps:
 contra-deps:
 = true

added constraint A <: Int to
 uninstantiated variables: F, A
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Option
     A <: Int
 ordering:
 co-deps:
 contra-deps:
 = true

added constraint A :> Int to
 uninstantiated variables: F
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Option
     A := Int
 ordering:
 co-deps:
 contra-deps:
 = true

committing TS[8X, 1, 0] to TS[1, 0], fromConstr =  uninstantiated variables: F
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Option
     A := Int
 ordering:
 co-deps:
 contra-deps:
, toConstr =  uninstantiated variables: F, A
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1]
     A
 ordering:
 co-deps:
 contra-deps:

With alias

class Box[T](val value: T)

def boo[F[_], A](e: F[Box[A]]): Unit = ()

type Result[G[_], B] = G[Box[B]]

def main =
  val b: Result[Option, Int] = ???
  boo(b)
  // boo[[X0] =>> Option[Box[X0] | X0]](b)
added constraint F :> [B] =>> Result[Option, B] to
 uninstantiated variables: F, A
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Result[Option, B]
     A
 ordering:
 co-deps:
 contra-deps:
 = true

added constraint F :> Option to
 uninstantiated variables: F, A
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Result[Option, X0] | Option[X0]
     A
 ordering:
 co-deps:
 contra-deps:
 = true

added constraint A <: Int to
 uninstantiated variables: F, A
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Result[Option, X0] | Option[X0]
     A <: Int
 ordering:
 co-deps:
 contra-deps:
 = true

added constraint A :> Int to
 uninstantiated variables: F
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Result[Option, X0] | Option[X0]
     A := Int
 ordering:
 co-deps:
 contra-deps:
 = true

CUT - prefer  uninstantiated variables: F
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Result[Option, X0] | Option[X0]
     A := Int
 ordering:
 co-deps:
 contra-deps:
 over  uninstantiated variables: F, A
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Result[Option, B]
     A
 ordering:
 co-deps:
 contra-deps:

committing TS[8X, 1, 0] to TS[1, 0], fromConstr =  uninstantiated variables: F
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Result[Option, X0] | Option[X0]
     A := Int
 ordering:
 co-deps:
 contra-deps:
, toConstr =  uninstantiated variables: F, A
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1]
     A
 ordering:
 co-deps:
 contra-deps:

added constraint F :> [X0] =>> Option[Box[X0] | X0] to
 uninstantiated variables: F
 constrained types: [F[_$1], A](e: F[Box[A]]): Unit
 bounds:
     F[_$1] >: Option[Box[X0] | X0]
     A := Int
 ordering:
 co-deps:
 contra-deps:
 = true

@mbovel
Copy link
Member

mbovel commented Jan 10, 2025

Considering this snippet:

class Box[T](val value: T)

def boo[F[_]](e: F[Box[Int]]): Unit = ()
type Result[G[_], X] = G[Box[X]]

def main =
  val b: Result[Option, Int] = ???
  boo(b)
  // boo[[X0] =>> Option[Box[X0] | X0]](b)

Mixing traces and printing, here is a summary of where the F :> [X] =>> Result[Option, X] constraint originates from:

==> isSubType (b : Result[Option, Int]) <:< F[Box[Int]] 
  TypeComparer.thirdTry$1(TypeComparer.scala:643)
    TypeComparer.compareAppliedType2$1(TypeComparer.scala:1442)
      TypeComparer.canInstantiate$1(TypeComparer.scala:1392)
        TypeComparer.appOK$1(TypeComparer.scala:1386)
          TypeComparer.compareAppliedTypeParamRef$1(TypeComparer.scala:1248)
            TypeComparer.directionalIsSubType$1(TypeComparer.scala:1220)
              ==> isSubType [X] =>> Result[Option, X] <:< F?
                ==> isSubType [X] =>> Result[Option, X] <:< F frozen?
                <== isSubType [X] =>> Result[Option, X] <:< F frozen = false
                adding constraint F :> [X] =>> Result[Option, X]
                ==> isSubType [X] =>> Result[Option, X] <:< [_] =>> Any?
                <== isSubType [X] =>> Result[Option, X] <:< [_] =>> Any = true
                added constraint F :> [X] =>> Result[Option, X]
              <== isSubType [X] =>> Result[Option, X] <:< F = true

This is a consequence of the "partial unification" algorithm described here:

/** Compare `tycon[args]` with `other := otherTycon[otherArgs]`, via `>:>` if fromBelow is true, `<:<` otherwise
* (we call this relationship `~:~` in the rest of this comment).
*
* This method works by:
*
* 1. Choosing an appropriate type constructor `adaptedTycon`
* 2. Constraining `tycon` such that `tycon ~:~ adaptedTycon`
* 3. Recursing on `adaptedTycon[args] ~:~ other`
*
* So, how do we pick `adaptedTycon`? When `args` and `otherArgs` have the
* same length the answer is simply:
*
* adaptedTycon := otherTycon
*
* But we also handle having `args.length < otherArgs.length`, in which
* case we need to make up a type constructor of the right kind. For
* example, if `fromBelow = false` and we're comparing:
*
* ?F[A] <:< Either[String, B] where `?F <: [X] =>> Any`
*
* we will choose:
*
* adaptedTycon := [X] =>> Either[String, X]
*
* this allows us to constrain:
*
* ?F <: adaptedTycon
*
* and then recurse on:
*
* adaptedTycon[A] <:< Either[String, B]
*
* In general, given:
*
* - k := args.length
* - d := otherArgs.length - k
* - T_0, ..., T_k-1 fresh type parameters
* - bodyArgs := otherArgs.take(d), T_0, ..., T_k-1
*
* Then,
*
* adaptedTycon := [T_0, ..., T_k-1] =>> otherTycon[bodyArgs]
*
* where the bounds of `T_i` are set based on the bounds of `otherTycon.typeParams(d+i)`
* after substituting type parameter references by the corresponding argument
* in `bodyArgs` (see `adaptedBounds` in the implementation).
*
* Historical note: this strategy is known in Scala as "partial unification"
* (even though the type constructor variable isn't actually unified but only
* has one of its bounds constrained), for background see:
* - The infamous SI-2712: https://github.com/scala/bug/issues/2712
* - The PR against Scala 2.12 implementing -Ypartial-unification: https://github.com/scala/scala/pull/5102
* - Some explanations on how this impacts API design: https://gist.github.com/djspiewak/7a81a395c461fd3a09a6941d4cd040f2
*/
def compareAppliedTypeParamRef(tycon: TypeParamRef, args: List[Type], other: AppliedType, fromBelow: Boolean): Boolean =

@mbovel
Copy link
Member

mbovel commented Jan 10, 2025

@smarter noted that there actually is a bug in compareAppliedTypeParamRef. The constraints are not properly rolled back when the call directionalIsSubType returns true but the call to directionalRecur returns false. #22339 fixes that.

@WojciechMazur WojciechMazur added this to the 3.6.4 milestone Jan 16, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants