Scala 3's Type System, Part 7: Higher-Kinded Types and Type Lambdas

At some point every Scala codebase grows four copies of the same function: one for Option, one for List, one for Either, one for Future. The bodies are character-for-character identical apart from the container. Higher-kinded types let you write it once, and Scala 3’s type lambdas finally make that practical without a compiler plugin.

🔗The problem: four copies of the same shape

Start with something trivial and obviously duplicated:

import scala.concurrent.{Future, ExecutionContext}

final case class Order(id: String, total: BigDecimal)

def totalOpt(o: Option[Order]): Option[BigDecimal] = o.map(_.total)
def totalList(os: List[Order]): List[BigDecimal] = os.map(_.total)
def totalEither(e: Either[String, Order]): Either[String, BigDecimal] = e.map(_.total)
def totalFuture(f: Future[Order])(using ExecutionContext): Future[BigDecimal] =
  f.map(_.total)

You can’t factor that with a normal type parameter. def total[C](c: C) gives you nothing — C is opaque, there’s no map on it. The thing that varies isn’t a type, it’s the container: Option, List, Either[String, _], Future. You need a type parameter that stands for a container rather than for a finished type.

It gets worse than map. Here’s the version that actually shows up in production — turn a List[A] into a container of List[B], short-circuiting on the first failure:

def traverseOpt[A, B](as: List[A])(f: A => Option[B]): Option[List[B]] =
  as.foldRight(Option(List.empty[B])) { (a, acc) =>
    f(a).flatMap(b => acc.map(bs => b :: bs))
  }

def traverseEither[A, B](as: List[A])(f: A => Either[String, B]): Either[String, List[B]] =
  as.foldRight(Right(List.empty[B]): Either[String, List[B]]) { (a, acc) =>
    f(a).flatMap(b => acc.map(bs => b :: bs))
  }

Two functions, one algorithm. The fold, the flatMap, the cons — all identical. Only Option/Either[String, _] and their pure differ.

🔗Kinds, in one paragraph

A kind classifies types the way a type classifies values.

Thing	Kind	Notes
Int, String, Order	*	A finished type. Values can have it.
List, Option, Future	* -> *	Give it one type, get a type back.
Either, Map, Function1	(*, *) -> *	Needs two.

List on its own is not a type — no value ever has type List. It’s a type constructor, a function at the type level. “Higher-kinded” just means: a type parameter whose kind isn’t *. In Scala you write that as F[_].

def sizeOf[A](xs: List[A]): Int = xs.size        // A has kind *
def emptyOf[F[_]](f: F[Int]): Boolean = false    // F has kind * -> *

🔗One implementation, all containers

With F[_] you can define the two capabilities the duplicated code actually needed, and write traverse once:

trait Functor[F[_]]:
  def map[A, B](fa: F[A])(f: A => B): F[B]

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

given Monad[Option] with
  def pure[A](a: A): Option[A] = Some(a)
  def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] = fa.flatMap(f)

given Monad[List] with
  def pure[A](a: A): List[A] = List(a)
  def flatMap[A, B](fa: List[A])(f: A => List[B]): List[B] = fa.flatMap(f)

def traverse[F[_], A, B](as: List[A])(f: A => F[B])(using M: Monad[F]): F[List[B]] =
  as.foldRight(M.pure(List.empty[B])) { (a, acc) =>
    M.flatMap(f(a))(b => M.map(acc)(bs => b :: bs))
  }

@main def run(): Unit =
  println(traverse(List("1", "2"))(_.toIntOption))   // Some(List(1, 2))
  println(traverse(List("1", "x"))(_.toIntOption))   // None

Monad here is a type class exactly like the ones in Part 5; the only new thing is that its parameter has kind * -> *. Nothing about traverse mentions Option.

🔗Where it breaks: Either has the wrong kind

Monad[Option] works because Option has kind * -> *. Either has kind (*, *) -> *, so Monad[Either] is a kind error. What you want is Either with the error type already filled in and the success type left open — partial application of a type constructor.

Scala 2 had no syntax for that. The community encoding was a structural type plus a type projection:

// scala-check: skip
// Scala 2, circa forever. This is the actual idiom, not a strawman.
implicit def eitherMonad[L]: Monad[({ type Lambda[X] = Either[L, X] })#Lambda] =
  new Monad[({ type Lambda[X] = Either[L, X] })#Lambda] {
    def pure[A](a: A): Either[L, A] = Right(a)
    def flatMap[A, B](fa: Either[L, A])(f: A => Either[L, B]) = fa.flatMap(f)
  }

Declare an anonymous structural type containing a type alias, then project the alias out with #. It is unreadable, and it had to be repeated at every use site. This is why essentially every serious Scala 2 library depended on the kind-projector compiler plugin, which let you write Either[L, ?] instead. A language feature delivered by a third-party plugin, for a decade.

🔗Type lambdas

Scala 3 has real syntax. A type lambda is [X] =>> body:

type StringOr = [X] =>> Either[String, X]

val a: StringOr[Int] = Right(1)
val b: StringOr[Int] = Left("nope")

It reads exactly like a term-level lambda (x => body) moved up one level, and it can be written inline wherever a type constructor is expected — including in a given:

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

given Monad[[X] =>> Either[String, X]] with
  def pure[A](a: A): Either[String, A] = Right(a)
  def flatMap[A, B](fa: Either[String, A])(f: A => Either[String, B]) =
    fa.flatMap(f)

def traverse[F[_], A, B](as: List[A])(f: A => F[B])(using M: Monad[F]): F[List[B]] =
  as.foldRight(M.pure(List.empty[B])) { (a, acc) =>
    M.flatMap(f(a))(b => M.map(acc)(bs => b :: bs))
  }

@main def run(): Unit =
  println(traverse(List("1", "2"))(s => s.toIntOption.toRight(s"bad: $s")))
  println(traverse(List("1", "x"))(s => s.toIntOption.toRight(s"bad: $s")))

That prints Right(List(1, 2)) then Left(bad: x). Same traverse as before, no new code.

Type lambdas take variance and bounds like any other parameter list: [+X] =>> ..., [X <: AnyRef] =>> .... The degenerate case type Id = [X] =>> X is genuinely useful — see the tagless-final section below.

If you’re porting a Scala 2 codebase full of kind-projector syntax, scalac -Ykind-projector accepts Either[String, *], and -Ykind-projector:underscores accepts Either[String, _]. It’s a migration aid: get the build green, then rewrite to =>>. New code should use =>> directly.

🔗The term-level analogue: polymorphic function types

Type lambdas abstract over types in types. Scala 3 also lets a value be generic, which Scala 2 could not express — a Function1 value had fixed parameter types:

val countAll: [A] => List[A] => Int = [A] => (xs: List[A]) => xs.size

@main def run(): Unit =
  println(countAll(List(1, 2, 3)))
  println(countAll(List("a", "b")))

[A] => List[A] => Int is the type; [A] => (xs: List[A]) => xs.size is the value. This matters when you need to pass a generic transformation as an argument — a natural transformation [A] => F[A] => G[A], for instance, which is how you swap one effect type for another without losing the element type.

🔗A realistic payoff: tagless final

The usual justification for all this is being able to write business logic once and run it under different effects — a real one in production, a synchronous one in tests. Abstract the repository over F[_]:

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

final case class User(id: String, email: String)

trait UserRepo[F[_]]:
  def find(id: String): F[Option[User]]
  def save(user: User): F[Unit]

// The logic. Written once, no effect type in sight.
def register[F[_]](id: String, email: String)(repo: UserRepo[F])(using M: Monad[F]): F[String] =
  M.flatMap(repo.find(id)):
    case Some(_) => M.pure(s"$id already registered")
    case None    => M.map(repo.save(User(id, email)))(_ => s"created $id")

// Production interpreter: failures are Left.
type Checked = [X] =>> Either[String, X]

given Monad[Checked] with
  def pure[A](a: A): Either[String, A] = Right(a)
  def flatMap[A, B](fa: Either[String, A])(f: A => Either[String, B]) = fa.flatMap(f)

object DbRepo extends UserRepo[Checked]:
  def find(id: String): Either[String, Option[User]] = Right(None)
  def save(user: User): Either[String, Unit] = Right(())

// Test interpreter: no effect at all.
type Id = [X] =>> X

given Monad[Id] with
  def pure[A](a: A): Id[A] = a
  def flatMap[A, B](fa: Id[A])(f: A => Id[B]): Id[B] = f(fa)

class InMemoryRepo(var users: Map[String, User]) extends UserRepo[Id]:
  def find(id: String): Option[User] = users.get(id)
  def save(user: User): Unit = users = users + (user.id -> user)

@main def run(): Unit =
  println(register[Checked]("u-1", "a@b.com")(DbRepo))
  println(register[Id]("u-1", "a@b.com")(InMemoryRepo(Map.empty)))

The test path has no Future, no ExecutionContext, no Await, no timeouts — Id erases the effect entirely, and it’s [X] =>> X that makes Id expressible as a type constructor at all.

🔗Gotchas

Inference degrades at higher kinds. Scala can usually infer F[_] from a concrete type by fixing all but the last type argument. That’s why Either[String, Int] infers F = [X] =>> Either[String, X] for free. Abstract over the left side and inference silently picks the wrong decomposition:

// scala-check: expect-error
trait Functor[F[_]]:
  def map[A, B](fa: F[A])(f: A => B): F[B]

given Functor[[X] =>> Either[X, String]] with
  def map[A, B](fa: Either[A, String])(f: A => B): Either[B, String] = fa.left.map(f)

def duplicate[F[_], A](fa: F[A])(using F: Functor[F]): F[(A, A)] =
  F.map(fa)(a => (a, a))

val r = duplicate(Left(1): Either[Int, String])

No given instance of type Functor[[B] =>> Either[Int, B]] was found
  for parameter F of method duplicate.
I found:
    given_Functor_Either
But Found:    given_Functor_Either.type
Required: Functor[[B] =>> Either[Int, B]].

The instance you wrote is right there and the error doesn’t say why it was rejected. The fix is to annotate explicitly — duplicate[[X] =>> Either[X, String], Int](...) — but you have to know that’s the problem first.

Error messages get long. Once F is a type lambda, every mismatch prints [X] =>> Either[String, X] inline. Naming the lambda (type Checked = [X] =>> Either[String, X]) makes errors substantially more readable, so do that even when the inline form would fit.

It’s often overengineering. Abstracting over F[_] costs you: worse inference, longer errors, an indirection every reader has to unwind, and a slower compile. It pays for itself when you genuinely need multiple interpreters (production plus a synchronous test one), or when you’re writing a library whose users pick the effect. It does not pay for itself in an application that will only ever run on one effect type — there, just write Future or IO and move on. “We might want to swap the effect later” is not a requirement; when you have one interpreter, F[_] is a parameter with exactly one argument.

None of this requires the Functor/Monad names or the laws behind them. What earns its keep is the mechanical fact that F[_] is a type parameter of kind * -> *. If the type-class vocabulary is a barrier on your team, name the traits after what they do — Mappable, Chainable — and nothing about the code changes.

🔗Next up

Type lambdas compute at the type level in a very limited way: substitution, nothing more. Part 8 covers match types, where a type can pattern-match on another type and recurse — plus inline and compiletime operations that let the term level follow along.