Understanding “Partial Unification” in Scala

And how it fixes the Scala compiler’s type inference

This article aims to explain a problem in the Scala compiler’s type inference fixed in Scala 2.13 with an innovative solution called Partial Unification. We will explain what was the problem, how Partial Unification solves it and the implications of implementing Partial Unification in the Scala compiler. Scala 2.13 comes with Partial Unification by default. For Scala 2.12 and earlier it has has to be enabled with the compiler flag -Ypartial-unification .

Let’s get started.

Introduction

As we all know, the Scala compiler is very powerful. It has some nice features like type inference, macros or implicit scopes which allow us to do all sorts of interesting things.

There are some scenarios, however, where it falls short. One of this scenarios is the one described in SI-2712 where Scala compiler’s type inference fails when inferring type constructors of different arities. Don’t worry just now about what that means, we will explain it in detail!

This might not be a common scenario for most Scala applications but it’s not rare to encounter it when doing functional programming with Scala, and it’s worthwhile understanding it.

We will start by explaining type constructors and what these are.

Type constructors

Type constructors are constructors for types. They take types as arguments and yield types in return.

scala> val intOption: Option[Int] = Some(1)
intOption: Option[Int] = Some(1)
scala> val stringOption: Option[String] = Some("Hello world")
stringOption: Option[String] = Some(Hello world)

As we can in the above example Option (just the name without the [ and ]) is actually a type constructor. Option can take type arguments Int and String and return the new types Option[Int] and Option[String] consequently.

You can think of type constructors as regular constructors that operate at the type level. Instead of taking other values as arguments and yielding new values in return, type constructors take types and yield types.

Defining type constructors & type constructor arity

A type constructor is defined whenever we declare a type that takes type parameters. For example:

class MyType[A]

We can see that MyType[A] takes a type parameter A . Therefore MyType is a type constructor that will yield new types like MyType[Int] , MyType[String] , the list goes on.

We can also define types that take type constructors as parameters, instead of regular type parameters.

import scala.language.higherKinds
class AnotherType[F[_]]

That fancy F[_] syntax is how we define a type constructor parameter. F
is the type constructor. Since F is a type constructor, we can use it to create new types like F[Int] or F[Boolean] .

Both the MyType and F type constructors have an arity of 1. They take 1 type parameter. Other type constructors of artity 1 are Option , Seq and List , but not Map or Either which have an arity of 2.

import scala.language.higherKinds
class YetAnotherType[F[_, _]]

That is how we define a type constructor parameter of arity 2. Keep in mind this concept of arity, it is important!

On a side note, notice we are importing scala.language.higherKinds when defining type constructors parameters. Types which take type constructors as parameters are called higher-kinded types. The Scala compiler requires these to be explicitly enabled. We can do that by importing scala.language.higherKinds or using the compiler flag -language:higherKinds .

Now that we defined our higher-kinded types we can see them in action:

scala> new AnotherType[Option]
res0: AnotherType[Option] = AnotherType@5c53f292
scala> new YetAnotherType[Map]
res1: YetAnotherType[Map] = YetAnotherType@32ea16b7

As we saw earlier AnotherType takes a type constructor of arity 1 and YetAnotherType takes a type constructor of arity 2 as type parameters. We are passing as arguments Option and Map which both satisfy the required arities and everything is fine.

Type inference and type constructor arities

In the previous example, when we wrote new AnotherType[Option] and new YetAnotherType[Map] , we explicitly told the compiler that Option and Map are the type constructors arguments for F[_] and F[_,_] .

However, some times the compiler has work out which are these type constructors on its own by means of type inference. Let’s see an example:

def foo[F[_], A](fa: F[A]): String = fa.toString
foo(List(1))

In the above example we defined a foo method which takes:

• A type constructor parameter F
• A type parameter A
• A parameter fa: F[A]

We then supplied List(1): List[Int] as an argument for fa: F[A] from which the compiler was able to infer that F is List and A is Int . It was able to do so because both F and List share the same arity. So far so good.

But… what happens when they don’t?

foo { x: Int => x.toDouble }

Here foo takes as argument a value of type Function1[Int, Double] for fa: F[A] . From such, the Scala compiler can infer two different possibilities for F[A] and A :

• A is Double and F[A] is Function1[Int, A]
• A is Int and F[A] is Function1[A, Double]

Both alternatives will make code compile and work as intended. As you can see the compiler fixed one of the two type parameters from Function1 and set the other to A . This is a similar concept to partial application, which is actually very common in functional programming.

The only problem is with the solution above is… the Scala compiler doesn’t implement it! We will get a compile error instead:

scala> foo { x: Int => x.toDouble }
<console>:14: error: no type parameters for method foo: (fa: F[A])String exist so that it can be applied to arguments (Int => Double)
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : Int => Double
 required: ?F[?A]
       foo { x: Int => x.toDouble }
       ^
<console>:14: error: type mismatch;
 found   : Int => Double
 required: F[A]
       foo { x: Int => x.toDouble }

Enter Partial Unification.

Partial unification

We saw that we were able to work out by hand two possible alternatives for F and A when passing an argument of type Function1[Int, Double] :

• A is Double and F[A] is Function1[Int, A]
• A is Int and F[A] is Function1[A, Double]

Recall that we achieved these by fixing one of the two type parameters for Function1 with either Int or Double . What if we supplied a Function2 instead?

foo {
  (x: Int, y: String) => {
    println(y)
    x.toDouble
  }
}

Here we supplied foo with an argument of type Function2[Int, String, Double] . What alternatives does the compiler have to work out F[A] and A ? It has three alternatives:

• A is Double and F[A] is Function2[Int, String, A]
• A is String and F[A] is Function2[Int, A, Double]
• A is Int and F[A] is Function2[A, Int, Double]

Calculating the amount of alternatives is a basic combinatorial problem, but that’s not interesting to us. The important thing to notice is that when the compiler has to infer a type constructor which has a lower arity than the type constructor supplied, it has to select one of many alternatives.

Partial Unification is basically that. When we have a type constructor parameter provided with a type constructor argument of a higher arity, it fixes types in the argument until we get both parameter and argument of the same arity.

This is still leaves us with the problem of selecting one of the many alternatives (the combinatorial amount) for fixing types. Out of all the possibilities, which one will the should the compiler select?

Unfortunately, there is no correct answer here. There is however an opinionated choice, motivated by the similarity with partial application we mentioned earlier and the common convention used in it. This is fixing the left-most types.

In our foo examples:

• A is Double and F[A] is Function1[Int, A]
• A is Double and F[A] is Function2[Int, String, A]

This can actually be extended to any arities for both type constructor parameter and argument (as long as the argument has a higher arity) . See the following example:

// type constructor parameter
F[_, _, _]

// type constructor argument
Function4[Int, String, Double, Boolean, Unit]

// inferred type constructor
[A, B, C]Foo[Int, String, A, B, C]

That’s it. That is how Partial Unification fixes type inference for these kinds of situations.

Despite being a solution to this problem, taking this opinionated choice of fixing the left-most types has some implications that should be accounted for.

Right-bias

In the dummy examples we have been using so far, selecting any alternative would make the code work exactly the same. This is not true however for all Scala applications. Some times selecting different alternatives will produce different outcomes!

This occurs for example when we use the type constructor parameter to construct the return type of a method:

def transform[A, B, F[_]](fa: F[A], func: A => B): F[B]

In the example above transform takes two type parameters A and B , a type constructor parameter F and two parameters fa: F[A] and func that transforms A => B . The return type of the transform method is naturally F[B] .

We don’t show the implementation for the transform method; for our purposes it’s not necessary (it is actually abstract). Just the method signature is enough for our demonstration.

So transform takes an fa: F[A] and a function func: A => B which we will use to transform our F[A] into an F[B] , just like the map method we all know and love.

Now let’s provide transform with some arguments:

transform(map: Map[String, String], i: String => i.toInt)

We supplied transform with a map: Map[String, String] and a function String => Int . As we know, the compiler has to infer A , B and F from the supplied argument types Map[String, String] and Function1[String, Int].

As we also know, the type constructor parameter F has a lower arity than the argument Map[String, String] supplied, so it will have to choose between:

• A is String, B is Int, F[A] is Map[String, A]
• A is String, B is Int, F[A] is Map[A, String]

Since we are using the type constructor F to construct the return type of our transform method (returns F[B]), each choice will produce a different return type!

Given that B is Int :

• If we set F[A] to Map[String, A] , F[B] will be Map[String, Int]
• If we set F[A] to Map[A, String], F[B] will be Map[Int, String]

Each alternative changes completely the semantics of the transform method. In the example above, each alternative means that the the function A => B will be applied to either the keys or values of the Map[String, String] .

Partial Unification fixes the left-most types so the transform method will return Map[String, Int] . The compiler assumed the function will be applied to the values of the Map[String, Int] because the values are represented by the right-most type parameter. In other words, whenever we use Map[K, V] to infer a type constructor F of arity 1, K will be fixed because it is the left-most type parameter and V will become the single type parameter of our type constructor F . This is what is known as the right-bias resulting from Partial Unification.

In most cases we don’t have to worry about the right-bias. If we are doing functional programming or if we are using type constructors in our Scala application, then the right-bias has to be accounted for when we design our data types. Our types should be right-biased.

Imagine we need to choose between the types Either[Error, Result] or Either[Result, Error] . Choosing one of these seems like a convention we should follow throughout our code. It seems it doesn’t matter which one we choose as far as we are consistent.

However, we should know that methods like transform will transform the Result or Error types depending on which alternative we select. Methods like transform can be defined in completely different places, like other modules or even other libraries that consume our code.

How we design our data type will affect how these methods will work and
that is why we have to account for the right-bias when designing our data types.

Fun fact: the image at the start of this post showcases the ladders at EPFL from which the Scala logo was inspired. It was taken by the author of Partial Unification himself, Miles Sabin.