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.
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]'
We can implement this way:
def f[A](as: List[A]): List[A] = ???
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
||little bit more|
||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!
- 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!'