Parametricity
ryantm
Ad hoc Polymorphism
“Overloading”
f(int x)
f(bool x)
f(String x)
Parametric Polymorphism
“Generics”
def f[A](x: List[A]): List [A] // Scala
List<A> f<A>(List<A> x) // C#
<A> List<A> f(List<A> x) // Java
f :: [a] -> [a] -- Haskell
Parametric Polymorphism
Limits the function writer
Gives guarantees to the caller
Limits the function writer
f :: [a] -> [a]
`a` can be anything, which is very limiting
cannot dispatch on type of argument at runtime
Other limits on the function writer
fromMaybe :: a -> Maybe a -> a
Purely functional language: we can only use the arguments to construct the return.
Breaking parametricity
null, exceptions
Type-casing (isInstanceOf)
Type-casting (asInstanceOf)
Side-effects, equals/toString/hashCode
notify/wait, classOf/.getClass
General recursion
Parametric Polymorphism
Examples
f :: a -> a-> a
Examples
f :: a -> a-> a
f a1 _ = a1
or
f _ a2 = a2
Examples
f :: a -> Int
Examples
f :: a -> Int
f _ = 1
Examples
f :: [a] -> [b]
Examples
f :: [a] -> [b]
[ ] -- empty list
Examples
f :: [a] -> [a]
Examples
f :: [a] -> [a]
f = id
f = reverse
f as = as ++ as
Examples
q :: (a -> b) -> (b -> c) -> a -> c
Examples
q :: (a -> b) -> (b -> c) -> a -> c
q f g a = g (f a)
More complex guarantees
r :: [a] -> [a]
f :: a -> b
r (map f as) = map f (r as)
Parametricity Limitations
reverse :: [a] -> [a]
tail :: [a] -> [a]
Need automated checking to build confidence