Is parametric polymorphism the same as dispatching on arity?

Question

Parametric Polymorphism

The idea behind parametric polymorphism is that you don't dispatch—a parametrically polymorphic function is one that behaves in the same way for all input types. Let's consider a very simple example (I'm going to use Haskell¹):

id x = x

This defines a function named id which takes one argument, x, and returns it. This is the identity function; it doesn't do anything. Now, what type should id have? It's definitely a function, so it will have the type input -> output for some input and output. We could say that id has type Int -> Int; then id 3 would evaluate to 3, but id True wouldn't typecheck, which seems silly. Saying id :: Bool -> Bool is no better; the problem is reversed. We know that for id, it doesn't matter what type the input is; id ignores that structure and just passes the value around. So for any type a, id has type a -> a, and we can write this explicitly:

id :: a -> a
id x = x

In Haskell, lowercase identifiers in types are are universally quantified variables—the above signature is the same as if I'd written id :: forall a. a -> a, except that writing the forall explicitly is only valid with some language extensions.

The identity function is the simplest example of a parametrically polymorphic function, and it highlights the idea that parametric functions simply pass data around. They can't examine the data to do anything with it.

Let's consider a slightly more interesting function: list reversal. In Haskell, lists of some type a are written [a], so the reverse function is

reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]
  -- `x:xs` is the list whose first element is `x` and whose second element is
  -- `xs`; `++` is the list-append operator.

The reverse function shuffles the elements of the list around, but it never manipulates them (and hence never "dispatches" on them). Hence, reverse knows it must take and return lists of something—but it doesn't care what that something is.

One last example of parametric polymorphism is the map function. This function takes a function f and a list, and applies that function to each element in the list. This description tells us that we don't care about the input or output types of the function, and nor do we care about the type of the input list—but they must match up appropriately. Thus, we have

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs
  -- In Haskell, function application is whitespace, so `map f xs` is like
  -- `map(f,xs)` in a C-like language.

Note that the input (respectively output) type of the passed-in function and the type of the elements of the input (respectively output) list must match; however, the input and output types can be distinct from each other or not, we don't care.

Parametric Polymorphism and Subtyping

You ask, in a comment, if parametric functions just accept values of the top type. The answer is no: subtyping is completely independent of parametric polymorphism. Haskell doesn't have any notion of subtyping at all: an Int is an Int, and a Bool is a Bool, and never the twain shall meet. In Java, you have both generics and subtyping, but the two features are semantically unrelated (unless you use bounded polymorphism of the form <T extends Super>, but this is more like a form of ad-hoc polymorphism, which I discuss below). Parametric polymorphism really is what it says: functions that accept any type. This is not the same as functions that accept a top type and rely on subsumption/implicit upcasting. One way to think about it is that parametric functions take an additional argument: the type of the parameter. So instead of id 3, you would have id Int 3; instead of id True, you would have id Bool True. In Haskell, you never need to do this explicitly, so there's no syntax for it. On the other hand, in Java, you sometimes need to, and so there's syntax which reflects this, as in Collections.<String>emptyList().

Ad-hoc Polymorphism

Parametric polymorphism often contrasts with various forms of ad-hoc polymorphism: polymorphism that allows one function to behave in different ways at different types. This is where "dispatch" shows up; where parametric polymorphism is about uniformity, ad-hoc polymorphism is about differences. Sometimes you don't want a function to act the same way at every type!

Standard Java-like object-oriented subtype polymorphism, which is formally called nominal subtyping, is an example of this; in Java, for instance, the boolean Object.equals(Object) method uses subtype polymorphism to dispatch on its first argument and return the appropriate result. It's clear that you wouldn't want equality to be parametric; you can't write one function that accurately compares both strings and integers for equality! Note, however, that .equals also uses instanceof to perform a "typecase" check of the run-time type of the argument; the int Object.hashCode() method is an example of a purely subtype-polymorphic method.

Haskell uses a different approach, called type-class polymorphism, to handle this. Here's a whirlwind tour of how that works. First, we say what it means to be comparable for equality (note that Haskell lets you define function names which are arbitrary operators, and then use them infix):

class Eq a where -- To say that a type `a` is comparable for equality, implement
                 -- these functions:
  (==) :: a -> a -> Bool -- Equality
  (/=) :: a -> a -> Bool -- Inequality

  -- We can also define default implementations for those functions:
  x == y = not (x /= y)
  x /= y = not (x == y)

Then, we instantiate the type class; for instance, here we say how to compare booleans for equality.

instance Eq Bool where
  True  == True  = True
  False == False = True
  _     == _     = False
    -- `_` means "don't care".

And when we want to compare elements for equality, we specify that we must have a type which satisfies the appropriate constraint. For instance, the elem function which checks if an element occurs in a list has type Eq a => a -> [a] -> Bool; we can read this as "for any a which is an instance of Eq, elem expects an a and a list of as, and returns a boolean":

elem :: Eq a => a -> [a] -> Bool
elem _ []     = False
elem y (x:xs) = x == y || elem y xs
  -- Haskell supports an infix syntax that would have allowed us to write
  -- `y `elem` xs`, with the backticks around `elem`.

Here, the elem function is not parametrically polymorphic, because we have some information about the type a—we know that we can compare its elements for equality. Consequently, elem will not behave in the same way for every input type (and there are some types we can't even compare for equality, such as functions), and so there's a form of type-based dispatch going on here, too.

¹ In case you're more familiar with languages like Java, the same function in Java would be (ignoring the containing class)

public static <T> T id(T t) { return t; }

Note that Java, unlike Haskell, allows you to violate parametricity by using the instanceof operator or calling methods like .toString() that are always available, but our id function doesn't do that.