What cause that type mismatch with underlying type in Scala

Question

I have the following code:

trait M[A] {
  def unit(a: A): M[A]
  def ★[B](f: A => M[B]): M[B]
}

case class State[A, S](run: S => (A, S)) extends M[A] {
  def unit[S](a: A): M[A] = State((s: S) => (a, s))
  def ★[B, S](f: A => M[B]): M[B] = State((s0: S) => {
    val (a, s1) = this.run(s0)
    val (b, s2) = f(a)(s1)
    (b, s2)
  })
}

but I get:

error: type mismatch;
 found   : s0.type (with underlying type S)
 required: S
    val (a, s1) = this.run(s0)
                           ^
error: type mismatch;
 found   : a.type (with underlying type Any)
 required: A
    val (b, s2) = f(a)(s1)
                    ^
error: type mismatch;
 found   : b.type (with underlying type Any)
 required: B
    (b, s2)
     ^
three errors found

Does it means that I cannot mix abstract type A, B, S and case class instances in the definition of unit and ★ and that I should use a trait State[A] extends M[A] {...} instead ?

Answer 1

This example could be forced to be compilable (see part 2), but instead of doing so, I believe it's more valuable to compare it to the standard approach with typeclasses, and understand why attempting to fix this approach results in so much trouble.

Comparison with the standard approach

Recall that modeling the state-monad with typeclasses would look somewhat like this:

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

case class State[S, A](run: S => (S, A)):
  def flatMap[B](f: A => State[S, B]): State[S, B] = State(s0 =>
    val (s1, a) = this.run(s0)                                                           
    f(a).run(s1)                                              
  )

object State:
  given stateMonad[S]: Monad[[X] =>> State[S, X]] with
    def pure[A](a: => A): State[S, A] = State(s => (s, a))
    def flatMap[A, B](a: State[S, A], f: A => State[S, B]): State[S, B] =
      a.flatMap(f)

Note that there are three distinct parts here:

• Monad[F]-typeclass, which basically corresponds to the statement "F is a monad", parameterized by F
• The State, a separate data structure about which we are making statements
• The implicit/given stateMonad, which is a constructive proof of the statement "for all S, [X] => State[S, X] is a monad".

Note that the Monad part (the statement) is strictly separate from the F part (the object about which we are making the statement).

Taken together, these three parts can be described by natural language roughly as follows:

"There is a data structure State. It is a Monad. Here is the proof: ..."

Now compare this to the formulation with extends from the question:

trait M[A] {
  def unit(a: A): M[A]
  def ★[B](f: A => M[B]): M[B]
}

case class State[A, S](run: S => (A, S)) extends M[A] { ... }

Here, the statement "something is a monad" is supposed to be extended by "something" that it itself attempts to describe. The M is both the statement that the "something" has such-and-such methods (unit, *), but it's also the thing that is being described. Translated into natural language prose, this formulation corresponds roughly to the unwieldy

"M states that it itself will be extended by something that has certain methods (unit, * etc.), whose definitions refer to the extending thing itself."

which is a special case of

"M states that it will be extended by some S, and that the S will satisfy some properties that refer to S (and thus also to M)"

which is a special case of

"M states that M has some properties"

which is a known recipe for creating all kinds of self-referential cyclical statements such as

"M states that M is false."

better known as the Liar's paradoxon

"This statement is false."

So, the emergence of F-bounded polymorphism and the explosion of all those invalid cyclic-reference errors is not accidental: by attempting to merge the thing that is being described with the statement that does the describing, you're creating this proto-paradoxical self-referential structure.

Therefore, I'd suggest to stick to the standard formulation, and keep the statements separate from the things about which one wants to make the statements.

---

How one could force it to compile

(All of the following is purely for educational purposes, I would not suggest to use the resulting code; It serves only as an example for demonstrating several interesting compilation errors; Long story short: don't attempt to use F-bounded polymorphism to define monad interfaces, use typeclasses instead)

The extends M[A] is a red flag. Theoretically, you can make it work, but it won't be pretty.

Several problems here:

1. You are binding S twice, so that the S in the State[A, S] is shadowed by the non-inferable S from unit[S], so that nothing fits together. This can be solved by eliminating some of the unnecessary S-s.
2. The A in unit seems to depend in an unexpected way on the type bound by State[A, S]. It would be better if it had its own A.
3. Even if you fix this, you immediately run into problem that the return types in the methods of your M are way too vague: you don't want just anything that implements M in some way, you want the same type that is implementing M. This can be solved by F-bounded polymorphism, but this leads you to an even worse problem that...
4. ...You need type-lambdas to express the F-bounded polymorphism. This gets outright ugly without kind-projector or first-class type lambda support.
5. There are multiple things that are unconventional: unit is usually called pure, the order of parameters is usually State[S, A], because the second parameter plays better with type inference.

Combining Scala 3's type lambda support with inexplicable amounts of unprovoked disproportionate violence, we thus obtain:

trait M[F[X] <: M[F, X], A] {
  def unit[A](a: A): F[A]
  def ★[B](f: A => F[B]): F[B]
}

case class State[S, A](run: S => (A, S)) extends M[[X] =>> State[S, X], A] {
  def unit[A](a: A): State[S, A] = State((s: S) => (a, s))
  def ★[B](f: A => State[S, B]): State[S, B] = State((s0: S) => {
    val (a, s1) = this.run(s0)
    val (b, s2) = f(a).run(s1)
    (b, s2)
  })
}

...which compiles, but is very awkward to use, because it requires an instance of a correctly typed State just in order to invoke unit, which defeats the purpose.

It's a good exercise, but the resulting code is highly suboptimal. There are good use cases for mixing monads with extends, but this is not one of them.