# What is parametric polymorphism?

I keep talking about this so i want to give a "rough not very technical" idea what it is.

A polymorphic data structure is basically data structure abstracted over one or more types. For example `array` and `list` are candidates. The requirement is that these work for any type. The definition of these things usually involves using a type parameter, which is universally quantified over all types .. hence "parametric".

You can have an array of int, an array of string, .. an array of absolutely any type at all!

A parametrically polymorphic function is similar. But this comes with very heavy constraints. For example, consider the function which reverses the elements of an array. You need to be able to swap and or copy elements of ANY type, that's generally considered a universal operation on all types. Given a purely functional singly linked list, you can produce a new list with the elements reversed easily.

NO. You can NOT sort an array with a just a function that accepts an array, because you need an ordering on the elements and not all types have such an ordering!

That's a bit restrictive, isn't it?

NO. It's not. It's completely general. What? You say? Aren't I contradicting myself?

Nope. I said "just a function that accepts an array". If you pass in to the function a comparison operator that works for ANY type, you can do it. I'm going to show a simpler example: "add up everything in an array":

``````fun addem[T] (a: varray[T], add: T * T -> T, var init:T) {
for v in a perform init = add(init, v);
return init;
}
``````

See? if you pass in the add function that works on the values stored in the array you can do it, no problem. You can type check this function so that ANY instantiation for ANY type and addition operator must work without further type checking which in particular means to call this function you ONLY need to know the interface, not the implementation. In particular the interface is just the name of the function and its type .. this is why types are so important:

``````fun addem[T] : varray[T] * (T * T -> T) * T -> T
``````

Now, parametric polymorphism has a problem. In complex algorithms, you may need to pass in a LOT of functions to do the work. On way to simplify this is to put all the functions into a record and just pass in the record.

Another way to simplify it is to pass in the record statically (at compile time). Which is what you do with type classes (Haskell) or interfaces (Chapel). Typically you have a type class and specify using it like:

``````fun default_addem[T where Addable[T]] (a: varray[T]) {
var init = zero();
This is the same function body, but we find the `add` function in Addable[T]. This again can be type checked AND every call is guaranteed to be type correct BUT later, the compiler may fail to find Addable for a particular T. This is not a type error. It's constraint failure, or, if you like an instantiation error, or, "the programmer forgot to define that instance".