Hard-won Scala 3 knowledge: make your type-holes the last type-parameter

Question
1

I wanted to share some knowledge about designing with multiple type-parameters in Scala 3 that has been hard-won, by much staring at compile errors and experimentation.

The Scala 3 compiler has some (AFAIK undocumented) quirks around where it likes “type holes” to appear in types that take multiple type-parameters: apparently, it likes them last!

The issue shows up when we have a type that takes more than one type parameter. For example the Either[L, R] type has 2 type params, L and R.

Now, we might want to pass such a type into a context where a so-called “type-hole” is expected, by partially applying (ie choosing) one of the type parameters, but leaving the other one free.

Here’s an example where we expect a higher-kinded type F[_] that has one hole (unfilled type param). These cases are routine when programming with the Cats library, for example.

def example[F[_], A](fa: F[A])(using Typeclass[F]): Unit = ???

Now there are two possible ways we could partially apply Either to fit this shape, being [X] =>> Either[X, R] (“Either[_, R]”) or [X] =>> Either[L, X] (“Either[L, _]”). How to choose?

It’s common in typeclass-based programming to let the availability of a typeclass instance guide the inference of a type satisfying that constraint. Roughly, example above would like to find a type F[_] which matches the value parameter fa and also the given param Typeclass[F].

While in many scenarios, such type-inferencer constraint satisfaction works well, for some reason it doesn’t work at all for choosing amongst partially applied types.

If we provide a given instance for eg type [X] =>> Either[X, String], or any where the hole is not in the last position, it will not work:

object Typeclass:
given Typeclass[[X] =>> Either[X, String]

We’ll see an error like No given instance of type Typeclass[[B] =>> Either[Int, B]] was found for parameter x$2 of method example. Scala has arbitrarily decided to, first, put the hole in last position, and then search for a matching type-class.

This limitation has implications when designing abstractions with multiple type-parameters. Think about which parameters are typically like to be free, to be the hole. This might be the parameter you expect would be mapped over, for example, and thus need a cats.Functor[_] instance. Put this parameter last!

Finally, there’s another twist in the tail. If one creates a regular type alias that swaps the order of type parameters, and then passes an aliased type, then one can get non-last parameters to be selected as the hole (This is one of the very few cases where type aliases are not fully transparent in Scala 3).

trait Typeclass[F[_]]
object Typeclass:
  given Typeclass[[X] =>> Either[X, String]] = ???
  // given Typeclass[[X] =>> Either[Int, X]] = ???

case class Either[A, B]()

val v = Either[Int, String]()

def example[F[_], A](fa: F[A])(using Typeclass[F]): Unit = ???

type SwapEither[X, Y] = Either[Y, X]

val v2: SwapEither[String, Int] = v

val wontCompile = example(v) //No given instance of type Typeclass[[B] =>> Either[Int, B]] was found for parameter x$2 of method example

val compiles = example(v2)
1 Like
2

Not to be a wiseacre but isn’t that the behavior that was added under the -Ypartial-unification flag and has been enabled by default since scala 2.13?

1 Like
3

It is, isn’t it! I think I even emojied when “partial unification” was merged into scalac.. and yet failed to recognise the very same when I bumped into it in the wild, these years later.

The partial unification flag is long gone though, and there’s a real risk that this aspect of “how the scala language works” getting buried in folklore about an obscure, and discontinued, compiler flag.

This is a nice write-up:

1 Like
4

The fact that type aliasing changes the inferred type is also quite surprising and I’m not sure if that’s intended language semantics, or a quirk of the implementation. My money is on the latter..

5

Type dealiasing is the real dark magic of the Scala compiler. Even the most experienced type wizards don’t dare depend on it.

6

That’s actually very much by design and is the thing that makes partial unification work in most cases. @smarter would know more of the details..

1 Like
7

The smarter comment on leveraging the type alias:

1 Like