Connecting...

# Understanding Parametricity in Scala by Daniel Sebban

Happy Friday! Today's learn is from Daniel Sebban on Understanding Parametricity in Scala where he uses code examples to explain a fundamental functional programming concept called parametricity.

'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.

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 !

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``````

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 'B' to '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 'A's. 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``

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 'Int's)
We jumped to another dimension here, so many possible implementations, so many ways to implement bugs …

Let’s recap

input output # implementations
`a: A` `A` 1
`a: A, b: A` `A` 2
`as: List[A]` `List[A]` little bit more
`a: A` `Int` a lot more!

• 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 'A's because we know nothing about individual 'A's)
• 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!'

This article was written by Daniel Sebban and posted originally on Medium.