Scala Tagless Final - Not compiling

This is a basic Scala Tagless Final pattern implementation of a contrived login process. It doesn't compile because as it shows near the end 'No implicits found for parameters ...'

But if I remove ': Monad: LoginProcessAlgebra[F]' from the program generic type that specific error goes away but the for-comprehension starts to complain because F[_] is no longer narrowed down to a Monad

Question: Why does Scala think State isn't a Monad?

import cats.Monad
import cats.implicits._

import java.util.UUID
import scala.language.higherKinds

case class Credentials(uid: String, pwd: String)
case class Session(sessionId: String, credentials: Credentials)

object LoginProcessTaglessFinal {

  trait LoginProcessAlgebra[F[_]] {
    def captureCredentials(name: String, password: String): F[Credentials]
    def login(credentials: Credentials): F[Session]

  type LoginProcessState = State[LoginProcessAlgebra[_], _]
  type LoginProcessStateA[A] = LoginProcessState[A]

  implicit object LoginProcessInterpreterUsingState extends LoginProcessAlgebra[LoginProcessStateA] {
    override def captureCredentials(name: String, password: String): LoginProcessStateA[Credentials] =
      State(login => (login, Credentials(name, password)))
    override def login(credentials: Credentials): LoginProcessStateA[Session] =
      State(login => (login, Session(UUID.randomUUID().toString, credentials)))

  def program[F[_]: Monad: LoginProcessAlgebra[F]](userName: String, password: String)
    (implicit interpreter: LoginProcessAlgebra[F]): F[Session] = for {
      credentials <-  interpreter.captureCredentials(userName, password)
      session <-  interpreter.login(credentials)
    } yield session

  val sessionState = program("someUserName", "p455w0rd")
  //compile error here 
  //due to 'No implicits found for parameters ...'


  • import scala.language.higherKinds is deprecated (since Scala 2.13.1).

    Compilation errors start earlier (Scala 2) (Scala 3)

    You have incorrect kinds in these lines

    type LoginProcessState = State[LoginProcessAlgebra[_], _]
    type LoginProcessStateA[A] = LoginProcessState[A]

    Your code seems to be in Scala 3.

    I replaced

    type LoginProcessState = State[LoginProcessAlgebra[_], _]


    // scalacOptions += "-Ykind-projector"
    type LoginProcessState = State[LoginProcessAlgebra[?], *]

    i.e. with a type lambda [A] =>> State[LoginProcessAlgebra[?], A] into existential type LoginProcessAlgebra[?]

    Polymorphic method works with type lambda, but not with type wildcard in Scala 3

    Also I replaced

    def program[F[_]: Monad: LoginProcessAlgebra[F]](userName: String, password: String)
        (implicit interpreter: LoginProcessAlgebra[F]): F[Session]


    def program[F[_]: Monad](userName: String, password: String)
        (implicit interpreter: LoginProcessAlgebra[F]): F[Session]

    (it's LoginProcessAlgebra that can be a context bound, not LoginProcessAlgebra[F]; also you had both context bound LoginProcessAlgebra and the same implicit LoginProcessAlgebra[F] once again, which can't be correct).

    Now the error is Ambiguous given instances: both value catsStdInstancesForOption in trait OptionInstances and value catsStdInstancesForVector in trait VectorInstances match type cats.Monad[F] of an implicit parameter of method program in object LoginProcessTaglessFinal

    You just need to specify type parameter F=LoginProcessStateA at the call site. It can't be inferred.

    val sessionState = program[LoginProcessStateA]("someUserName", "p455w0rd")

    The code now compiles

    LoginProcessStateA seems to be the same as LoginProcessState. I'm removing the former.

    Also in Scala 3 it's better to use given/using instead of implicit

    In Scala 2 I can't make this compile

    type LoginProcessState[A] = State[LoginProcessAlgebra[F], A] forSome { type F[_] }

         while compiling: ...
            during phase: typer
      last tree to typer: Apply(method apply)
           tree position: ...
                tree tpe: Credentials
                  symbol: case method apply in object Credentials
       symbol definition: case def apply(uid: String, pwd: String): Credentials (a MethodSymbol)
          symbol package: <empty>
           symbol owners: method apply -> object Credentials -> object App
               call site: method captureCredentials in object LoginProcessInterpreterUsingState in package <empty>


    type LoginProcessAlgebraE = LoginProcessAlgebra[F] forSome { type F[_] }
    type LoginProcessState[A] = State[LoginProcessAlgebraE, A]

    (this should be the literal translation of Scala 3 type LoginProcessState = State[LoginProcessAlgebra[?], *])

    can't existentially abstract over parameterized type F
      State((login: LoginProcessAlgebraE) => (login, Credentials(name, password)))
      State((login: LoginProcessAlgebraE) => (login, Session(UUID.randomUUID().toString, credentials)))

    WeakTypeTag for higher kinded type

    "can't existentially abstract over parameterized type..."

    Finally this turned out to be Scala 2 and

    type LoginProcessState[A] = State[String, A]