How does Haskell’s type system handle polymorphism?

Haskell’s type system handles polymorphism using two main concepts: parametric polymorphism and ad-hoc polymorphism (also known as type classes). Let’s discuss them one by one.

Parametric Polymorphism

Parametric polymorphism allows you to write functions and data structures that are generic over any type, without having to commit to a specific type. Let’s see an example of a polymorphic function:

identity :: a -> a
identity x = x

Here, the identity function takes an argument of a generic type ’a’ and returns a value of the same type. We don’t have to specify a concrete type for ’a’; it can be any type the caller chooses.

Similarly, you can define polymorphic data structures. For example:

data Pair a b = Pair a b

Here, the $\verb|Pair|$ data type is polymorphic in two type variables, ’a’ and ’b’. This allows us to create a pair of any two types, such as $\verb|Pair Int String|$, $\verb|Pair Bool Char|$, etc.

Ad-hoc Polymorphism (Type Classes)

While parametric polymorphism is useful, sometimes we need more fine-grained control over what types a function can accept. Haskell’s type classes allow us to define a set of functions that must be implemented by any type that wants to be an instance of the type class. This is somewhat similar to interfaces in object-oriented programming.

For example, let’s define a simple type class for a mathematical group structure:

class Group g where
  gempty :: g
  gappend :: g -> g -> g
  ginvert :: g -> g

Here, we define a type class Group with three functions: gempty (identity element), gappend (group operation), and ginvert (inverse operation). Any type that wants to be an instance of the Group type class must provide implementations for these three functions.

Let’s create an instance of the Group type class for integers under addition:

instance Group Integer where
  gempty = 0
  gappend a b = a + b
  ginvert a = -a

Now, we can use the functions from the Group type class for any type that provides an instance. We can define other instances for different types as well.

This way, Haskell’s type system can handle polymorphism by allowing you to write generic functions and data structures using parametric polymorphism, and at the same time giving you fine-grained control over the types a function can accept using ad-hoc polymorphism (type classes).