What is the ? type?

Question

I am trying to implement a cats Monad instance for a type that has multiple type parameters. I looked at the cats Either instance to see how it was done there. Part of the Either Monad instance code from cats is copied below:

import cats.Monad

object EitherMonad {
  implicit def instance[A]: Monad[Either[A, ?]] =
    new Monad[Either[A, ?]] {
      def pure[B](b: B): Either[A, B] = Right(b)

      def flatMap[B, C](fa: Either[A, B])(f: B => Either[A, C]): Either[A, C] =
        fa.right.flatMap(f)
    }
}

It fails to compile with the error: error: not found: type ?

What is the ? type and how can I use it when creating instances for my own types?

Answer 1

It is special syntax for so-called type lambdas that is added by the kind projector plugin.

Either[A, ?]

is a shortcut for

({type L[X] = Either[A, X]})#L

The whole code desugars to

import cats.Monad

object EitherMonad {
  implicit def instance[A]: Monad[({type L[X] = Either[A, X]})#L] = new Monad[({type L[X] = Either[A, X]})#L] {
    def pure[B](b: B): Either[A, B] = Right(b)

    def flatMap[B, C](fa: Either[A, B])(f: B => Either[A, C]): Either[A, C] =
      fa.right.flatMap(f)
  }
}

Type lambdas look frightening, but they are essentially a very simple concept. You have a thing that takes two type parameters, like Either[A, B]. You want to provide a monad instance for Either, but trait Monad[F[_]] takes only one type parameter. But in principle that's OK, since your monad instance is only concerned with the second (the "right") type argument anyway. A type lambda is just a way to "fix" the first type argument so you have the right shape.

If you would do the same thing at value level, you wouldn't even think about it twice. You got a function of two arguments

val f: (Int, Int) => Int = ...

And something you want to pass f to, which only takes 1 argument

def foo(x: Int => Int) = ...

The only way to make things fit is to fix one of the arguments

foo(x => f(1, x))

And that's exactly what a type lambda does at type level.