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

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 = adef 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 = 1def f[A](a: A): Int = 2def f[A](a: A): Int = 3def 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

• 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!