Can't use flatMap as an extension method on a self-written instance of a monad

Question

I've tried to use flatMap on WriterT and it was successful.

So the problem is with my type probably but I can't find what's wrong with it.

import cats.Monad
import cats.syntax.flatMap._

object Main extends App {
    type Optional[A] = A | Null
    
    val maybeInt1: Optional[Int] = 1
    val maybeInt2: Optional[Int] = null
    
    given Monad[Optional] with {
        def pure[A](x: A): Optional[A] = x
        def flatMap[A, B](fa: Optional[A])(f: A => Optional[B]): Optional[B] = {
            fa match {
                case null => null
                case a: A => f(a)
            }
        }
        def tailRecM[A, B](a: A)(f: A => Optional[Either[A, B]]): Optional[B] = {
            f(a) match {
                case null     => null
                case Left(a1) => tailRecM(a1)(f)
                case Right(b) => b
            }
        }
    }

    def f[F[_]: Monad, A, B](a: F[A], b: F[B]) = a.flatMap(_ => b)
    
    println(Monad[Optional].flatMap(maybeInt1)(_ => maybeInt2)) //OK: null
    println(f[Optional, Int, Int](maybeInt1, maybeInt2)) // OK: null
    println(maybeInt1.flatMap(_ => maybeInt2)) // Compilation Error
}

The error is:

value flatMap is not a member of Main.Optional[Int].
An extension method was tried, but could not be fully constructed:
cats.syntax.flatMap.toFlatMapOps([A] =>> Any), A(given_Monad_Optional)

Answer 1

Your definition has several issues.

Issue 1. You are using non-opaque type alias to a non-parametric type

I.e. type Optional[A] = A | Null is a type expression that will be expanded as soon as possible. When you are using it as a result type what you actually get is

val maybeInt1: Int | Null = 1
val maybeInt2: Int | Null = null

So when the compile compiler has something like

implicit def toFlatMapOps[F[_], A](fa: F[A])(implicit F: Monad[F]): MonadOps[F, A]

imported from scala 2 library or equivalent extension in scala 3, and finally comes to maybeOption.flatMap,
then tries to apply former extension method,
it fails to typecheck the expression toFlatMapOps(maybeInt1).flatMap(_ => maybeInt2)

So now you have Int | Null as an argument since Optional have been already expanded and need to calculate corresponding F[_] and A, it has many solutions such as

1. F[X] = Int | X , A = Null
2. F[X] = X | Null, A = Int
3. F[X] = A | Null, A = Nothing
4. F[X] = [X] =>> X, A = Int | Null

So scala naturally fails this attempt to guess.

Despite that scala 3 compiler can use additional information such as implicit\contextual value here, the implicit value matching Monad with the highest priority here is

    given Monad[Optional]

Now can can attempt to apply toFlatMapOps[F = Maybe](maybeInt1 : Int | Null) Then having F[X] = X | Null you need to calculate the A knowing that F[A] = Null | A and that has many plausible solutions as well

1. A = Int
2. A = Int | Null

So even if scala wouldn't fail at the first step it'd stuck here

Solution 1. Use Opaque Type Aliases

Add scalacOptions += "-Yexplicit-nulls" to your sbt config and try this code

import cats.Monad
import cats.syntax.flatMap.given

object Optional:
  opaque type Optional[+A] >: A | Null = A | Null

  extension [A] (oa: Optional[A]) def value : A | Null = oa

  given Monad[Optional] with 
    def pure[A](x: A): Optional[A] = x
    def flatMap[A, B](fa: A | Null)(f: A => B | Null) = 
      if fa == null then null else f(fa)       
    def tailRecM[A, B](a: A)(f: A => Optional[Either[A, B]]): Optional[B] = 
        f(a) match 
            case null     => null
            case Left(a1) => tailRecM(a1)(f)
            case Right(b) => b

type Optional[+A] = Optional.Optional[A]   

@main def run =    
    val maybeInt1: Optional[Int] = 1
    val maybeInt2: Optional[Int] = null   

    def f[F[_]: Monad, A, B](a: F[A], b: F[B]) = a.flatMap(_ => b)
    
    println(Monad[Optional].flatMap(maybeInt1)(_ => maybeInt2)) //OK: null
    println(f(maybeInt1, maybeInt2)) // OK: null
    println(maybeInt1.flatMap(_ => maybeInt2)) // Compilation Error

Issue 2. This type is not a monad

Even in this fixed version Optional[A] fails basic monadic laws Consider this code

def orElse[F[_], A](fa: F[Optional[A]])(default: => F[A])(using F: Monad[F]): F[A] = 
    fa.map(_.value).flatMap(fb => if fb == null then default else F.pure(fb : A))   

def filterOne(x: Int): Optional[Int] = if x == 1 then null else x - 1

println(orElse(maybeInt1.map(filterOne))(3)) 

The first method attempts to resolve missing values with the given calculated monadic value, the second just filter out ones. So, what do we expect to see when something like this evaluated?

orElse(maybeInt1.map(filterOne))(3)

We take non-empty maybe, then replacing the 1 with the missing place, and then immediately fixing it using provided 3. So I would expect to see 3 but actually, we gain null as result since null inside the wrapped value considering as a missing branch for outer Optional during flatMap. This is because such naively defined type violates the left-identity law

UPDATE Regarding comment by @n-pronouns-m How this definition violates left identity law. Left identity states that

pure(a).flatMap(f) == f(a) 
for all types A, B, and values a: A, f: A => Optional[B]

so lets take A = Optional[Int], B = Int, A = null, f(a) = if a == null then 3 else 2

pure(a) is still null, flatMap returns null for every in first argument, so pure(a).flatMap(f) == null while f(a) == 3

Answer 2

Odersky's response on topic

It does work if you make Null a separate class, or you compile with -Yexplicit-nulls.

The way things are Null is a bottom type. So every class instance of Optional[C] is in fact C.

I tried to change the definition of Optional to

type Optional[A] = A

then the implicit is not found either. So the problem looks like not a problem with union types at all. If Optional[A] defines a real union it works. It looks rather like a limitation of HK type inference that it cannot infer identities. That's actually expected, I think.