Explaining "theorems for free" and parametricity, for practicing programmers. With code in Scala

Sergei Winitzki explains the practical applications of parametricity and Philip Wadler's Theorems for Free paper using Scala code.

Philip Wadler's well-known paper "Theorems for Free" is not easy to understand and does not clearly explain what programmers need to know in order to apply parametricity in their work. This tutorial focuses on the practical applications of parametricity and describes five concrete advantages software engineers will gain from learning about parametricity properties. Contents: Examples of code refactorings that are guaranteed to be correct Writing code refactorings as equations, called "naturality laws" Naturality laws in typeclasses and their advantages Four things programmers need to learn in order to use parametricity in practice What is "fully parametric" code: examples and a rigorous definition Example of non-fully parametric code. How much "theorems for free" actually cost Two approaches to the theory of parametricity: using relations vs. using dinatural transformations What are profunctors and how to use them to formulate dinatural transformations The general dinaturality law for transformations with type signature P[A, A] ⇒ Q[A, A] Example: deriving the naturality law for `filter` from the general dinaturality law Further applications of parametricity: Commutativity law for bifunctors Further applications of parametricity: Why the code of `map` is unique Summary: five practical applications of parametricity Slides: github.com/winitzki/sofp/blob/master/sofp-src/explaining-the… Link to the book draft "Science of Functional Programming": github.com/winitzki/sofp