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.data.State
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

https://scastie.scala-lang.org/DmytroMitin/cVmdwXy7RKSWUbn9V0TBGw (Scala 2)

https://scastie.scala-lang.org/DmytroMitin/cVmdwXy7RKSWUbn9V0TBGw/6 (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[_], _]

with

// 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]

with

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

https://scastie.scala-lang.org/DmytroMitin/cVmdwXy7RKSWUbn9V0TBGw/3

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

https://scastie.scala-lang.org/DmytroMitin/cVmdwXy7RKSWUbn9V0TBGw/5

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

https://scastie.scala-lang.org/DmytroMitin/cVmdwXy7RKSWUbn9V0TBGw/13

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

https://scastie.scala-lang.org/DmytroMitin/cVmdwXy7RKSWUbn9V0TBGw/16

---

In Scala 2 I can't make this compile

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

https://scastie.scala-lang.org/DmytroMitin/Ov3BYdS5RjGXcXKEleoIlw/2

scalac: 
  ?BoundedWildcardType?
     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>

or

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[?], *])

https://scastie.scala-lang.org/DmytroMitin/Ov3BYdS5RjGXcXKEleoIlw/3

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]

https://scastie.scala-lang.org/james-oncloud/uCAPMvBvR7OLuEW27jyt6Q/4