Understanding Parametricity in Scala

In this post I’ll use code examples to explain a fundamental functional programming concept called parametricity. This concept is an essential step in convincing yourself that there is something more profound to functional programming that meets the eye.

Type and value parameters

def f[A](a: A, b: String): String = "hi"

a and b are value parameters, the one you use most of the time.

A is a type parameter, the caller will decide what it is when he calls the function:

scala> f("hello", "panda")
res0: String = hi
scala> f(2, "panda")
res1: String = hi
scala> f(List(1,2,3), "panda")
res2: String = hi

As you can see I can pass whatever I want in the first parameter, which seems to give more generality, but something more is going on here

What is Parametricity?

Parametricity was defined in Theorems for free! by Philip Walder, here is a click-baity quote from the introduction:

“Write down the definition of a polymorphic function on a piece of paper. Tell me its type, but be careful not to let me see the function’s definition. I will tell you a theorem that the function satisfies.”

Basically he claims that given any function with type parameters he can guess things that are true about this function or, in a sense, guess its implementation!

Seems magical, but I guarantee you by the end of this post you will also know how to do it.

Let’s make this concrete with a game

Rules of the game:

We operate in the FP world, so no exceptions, println or any nonsense like this. Also you are not allowed to use the built-in toString, hashCode, or others methods that come from the Object base class in Java/Scala.

Your task:

Find out How many implementation can this function have ?

We will go through different code examples, playing with their type parameters and types and see how it affects the number of implementations.

Let’s start!

def f[A](a: A): A = ???

A is a type parameter, it can be any type. We can implement this way:

def f[A](a: A): A = a

And that’s it !

Answer: 1

That is the only possible answer, that’s interesting, try to ask yourself why is it the only possibility ? We will answer this later.

Let’s add another value parameter b

Nothing much changed here, we only added b, let’s see how it affects the implementation space

def f[A](a: A, b: A): A = ???

We can implement this way:

def f[A](a: A, b: A): A = a
def f[A](a: A, b: A): A = b

Answer: 2

Notice you cannot do anything between a and b, even if they are from the same type, we cannot do this for example a + b.

Again ask yourself why? soon you will see the whole picture and it will become clear.

Let’s change b and Bto String instead of a parametric type

def f[A](a: A, b: String): String = ???

If you were tempted to use +, don’t!

The rules of the game also prohibit this and here is why:

def f[A](a: A, b: String): String = a + b
scala> f(1, "a")
res3: String = 1a

What does the + operator do ?

• a is converted to String using the illegal toString default method of every java object
• + finds (String, String) parameters, it can now concatenate them

Not good! We don’t like surprises so we are not allowing this.

We make the type richer with List[A]

def f[A](as: List[A]): List[A] = ???

We can implement this way:

def f[A](as: List[A]): List[A] = as
def f[A](as: List[A]): List[A] = if (as.isEmpty) Nil else as.tails.toList.head
def f[A](as: List[A]): List[A] = if (as.isEmpty) Nil else as.head :: Nil

Answer: A little bit more than 1, but still not so many

We are still fairly limited in our possible implementations and that is because we don’t know anything about specific As. We cannot sort them as we don’t have an ordering, we are just stuck to return a subset of the original list.

We add a new type parameter B

def f[A,B](as: List[A]): List[B] = ???

We can implement this way:

def f[A,B](as: List[A]): List[B] = Nil

Answer: 1

Interesting, we are back to one when adding a new type parameter

We change the return type to Int

def f[A](a: A): Int = ???

We can completely ignore the input type here and start implementing away

def f[A](a: A): Int = 1
def f[A](a: A): Int = 2
def f[A](a: A): Int = 3
def f[A](a: A): Int = 4

Answer: 2³² + 1 (Number of Ints)

We jumped to another dimension here, so many possible implementations, so many ways to implement bugs …

Let’s recap

• By introducing type parameters we hide information from the implementation of the function.
• The implementation space is reduced because we cannot use any properties on this type (think about List[A] we cannot sort As because we know nothing about individual As)
• Making a function more parametric will reduce the number of possible implementations.
• It will also make your code more re-usable as we can plug any type we want instead of our type parameters.
• Reduced possibilities of implementation means reduced possibilities of errors in code!

Takeaways

• Type parameters are like normal value parameters but at the type level f[A](a: A)
• Parametric functions do not use fixed types like String, Int, …
• By introducing type parameters, we hide information from the implementation of the function
• By hiding information we lower the implementation space and thus reduce the amount of possible mistakes
• This notion is called Parametricity
• Parametricity is NOT about code re-use, it’s a nice side effect though!