Polymorphism

Haskell’s type system admits two principal forms of polymorphism. Parametric polymorphism — sometimes called universal polymorphism — admits a function to work for any type without inspection: a function with type variable a behaves the same regardless of what a is. Ad-hoc polymorphism — through type classes — admits a function to behave differently depending on the type, with the implementation supplied by an instance declaration. Together, the two forms cover the substantial majority of Haskell’s polymorphic surface, with extensions admitting higher-rank polymorphism (functions that admit polymorphic arguments) and higher-kinded polymorphism (type classes parameterised by type constructors).

This page covers parametric polymorphism, the relationship to type classes, higher-kinded types, and the principal extensions. Type classes are treated in Type classes; algebraic data types in Algebraic data types.

Parametric polymorphism

A function is parametrically polymorphic if its type contains type variables that range over all types:

identity :: a -> a
identity x = x

const :: a -> b -> a
const x _ = x

length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs

The type variables a and b are universally quantified — forall a. a -> a and forall a b. a -> b -> a — though the forall is implicit in standard Haskell. Each call site instantiates the variables:

identity 5         -- a = Int
identity "hello"   -- a = String
identity True      -- a = Bool
identity (Just 1)  -- a = Maybe Int

The compiler checks that every call has consistent instantiation; the mechanism is Hindley-Milner type inference.

Parametricity

A consequence of parametric polymorphism: a function whose type is a -> a cannot inspect its argument. The function is given an a of unknown type; the only thing it can do with the argument is return it (or ignore it and produce something else, but that would change the return type).

The principle is parametricity (the free theorem): a function’s type often determines its behaviour up to a small number of possibilities. For example:

• f :: a -> a must be id (or non-terminating).
• f :: a -> a -> a must return one of its arguments.
• f :: [a] -> [a] may rearrange elements but cannot invent new ones; the result is some subsequence/permutation of the input.

The principle is theoretical but has practical implications: the type signature documents what the function can do, and the inference of type from usage often pins down the behaviour.

Type variables and forall

Type variables are universally quantified by default. The forall is implicit:

identity :: a -> a              -- equivalent to:
identity :: forall a. a -> a

The ExplicitForAll extension (admitted by default in modern GHC) admits writing the forall:

{-# LANGUAGE ExplicitForAll #-}

identity :: forall a. a -> a
identity x = x

The explicit form is necessary for some advanced types (rank-N polymorphism, treated below).

The ScopedTypeVariables extension brings the type variable into scope in the function body:

{-# LANGUAGE ScopedTypeVariables #-}

identity :: forall a. a -> a
identity x = (x :: a)           -- a is in scope here

The mechanism is occasionally needed for type ascriptions in the body. The extension is widely used in modern code.

Constraint context

A type variable may be constrained to belong to a type class:

sort :: Ord a => [a] -> [a]
elem :: Eq a => a -> [a] -> Bool
show :: Show a => a -> String

The Ord a => is a context: it asserts that a must be an Ord instance for the function to be called. The context is part of the type, but conventionally written before the => separator.

A function with constraint context is not fully parametric — the body may use the operations the constraint admits:

sort :: Ord a => [a] -> [a]
sort []     = []
sort (x:xs) = sort smaller ++ [x] ++ sort larger
  where
    smaller = [y | y <- xs, y <= x]    -- uses <= from Ord
    larger  = [y | y <- xs, y >  x]    -- uses > from Ord

The treatment of constraints and instance dispatch is in Type classes.

Higher-kinded polymorphism

Beyond polymorphism over types, Haskell admits polymorphism over type constructors — types parameterised by other types. A type constructor like [] (the list) takes a type argument and produces a type:

[]    :: * -> *           -- takes a type, produces a type
Maybe :: * -> *
Either :: * -> * -> *      -- takes two types
IO    :: * -> *

The * (or Type) is the kind of types that have values. Higher-kinded polymorphism admits type classes that abstract over type constructors:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

The f here is a type variable of kind * -> *. Instances of Functor are type constructors:

instance Functor Maybe where
    fmap f Nothing  = Nothing
    fmap f (Just x) = Just (f x)

instance Functor [] where
    fmap = map

instance Functor (Either e) where
    fmap _ (Left e)  = Left e
    fmap f (Right x) = Right (f x)

The Either e notation declares an instance for the partial application of Either to a type e — the result is a type constructor of kind * -> *, which admits a Functor instance.

The mechanism — type variables that range over type constructors — is the foundation of the Functor/Applicative/Monad hierarchy and a substantial part of what makes Haskell distinctive.

Rank-N polymorphism

By default, polymorphic functions admit one rank of polymorphism: the function is polymorphic, but its arguments are not.

The RankNTypes extension admits rank-N polymorphism: a function may take a polymorphic function as an argument:

{-# LANGUAGE RankNTypes #-}

applyToBoth :: (forall a. a -> a) -> (Int, String) -> (Int, String)
applyToBoth f (n, s) = (f n, f s)

main = print $ applyToBoth id (42, "hello")

The forall a. a -> a inside the argument’s type is a rank-2 type — the function takes an argument that is itself polymorphic.

Without RankNTypes, the function above would not type-check because Haskell’s default is rank-1 (the polymorphism appears only at the outer level).

The mechanism admits substantial advanced patterns (the ST monad’s runST, lens libraries, generic representations) but is rare in routine code.

Existential types vs universal types

The two quantifiers are dual:

• Universal (forall a. ...) — the caller chooses the type; the function works for any.
• Existential (exists a. ...) — the function chooses the type; the caller works with an unknown.

Haskell does not directly support exists, but the same effect is achieved through data:

{-# LANGUAGE ExistentialQuantification #-}

data Some f = forall a. Some (f a)

Construction admits any f a; consumption sees only the existential a:

package :: Some []
package = Some [1, 2, 3]      -- the Int is hidden

unpackage :: Some [] -> Int
unpackage (Some xs) = length xs  -- can't see the element type

Existential types are rare in routine code; they are useful for heterogeneous collections and certain plugin-style architectures.

Subtype polymorphism (does not exist)

Haskell does not have subtyping. A class hierarchy in OOP — Dog <: Animal <: Object — is not directly representable. The conventional Haskell substitutes:

• Sum types: data Animal = Dog | Cat | ...
• Type classes: class Animal a where speak :: a -> String

The choice depends on whether the set of variants is closed (data admits enumeration; new variants require modifying the type) or open (class admits new instances anywhere; the set grows).

The lack of subtyping is one of Haskell’s distinguishing features. It admits substantial type inference (the compiler does not need to consider the most-general supertype) but produces some patterns — for example, polymorphism over a bounded set of types — that require type classes rather than inheritance.

The dictionary-passing implementation revisited

Type-class polymorphism is implemented through dictionary passing: each constraint is a hidden parameter the caller supplies. The mechanism distinguishes type-class polymorphism from parametric polymorphism at the runtime level:

• Parametric polymorphism is erased — the runtime sees no type variable, and the compiled code is monomorphic with appropriate generality.
• Type-class polymorphism passes a dictionary (the set of methods for the relevant type) at runtime — every constrained call has dictionary access overhead.

GHC’s optimiser eliminates the dictionary passing in many cases through specialisation: when the type is known at the call site, the compiler generates a monomorphic version. The INLINABLE and SPECIALIZE pragmas control this.

Common patterns

Polymorphic data constructors

data List a = Nil | Cons a (List a)

singleton :: a -> List a
singleton x = Cons x Nil

map :: (a -> b) -> List a -> List b
map _ Nil = Nil
map f (Cons x xs) = Cons (f x) (map f xs)

The List type is parametric in a; map is parametric in both a and b. The combination admits arbitrary list contents.

Constrained polymorphism

sortBy :: (a -> a -> Ordering) -> [a] -> [a]
nub    :: Eq a => [a] -> [a]
sum    :: Num a => [a] -> a

The constraint specifies the operations needed; the function is otherwise polymorphic.

Type-class-driven design

class Container c where
    empty  :: c a
    insert :: a -> c a -> c a
    toList :: c a -> [a]

instance Container [] where
    empty  = []
    insert = (:)
    toList = id

instance Container Set where
    empty  = Set.empty
    insert = Set.insert
    toList = Set.toList

The class abstracts over the container; instances admit specific types.

Higher-kinded abstraction

class Functor f where
    fmap :: (a -> b) -> f a -> f b

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

class Applicative m => Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

The hierarchy admits writing functions that work for any functor, applicative, or monad — fmap, liftA2, >>= are polymorphic over the type constructor.

A note on type inference and decidability

Haskell’s type inference is complete and decidable for the rank-1 fragment (the standard language without extensions). Adding extensions can introduce undecidable inference:

• GADTs — inference becomes harder; GHC sometimes fails to infer types where a more capable system might succeed.
• RankNTypes — inference is decidable but requires explicit signatures in many places.
• ImpredicativeTypes (deprecated) — inference is undecidable.

The conventional advice: write type signatures for top-level functions, especially when using advanced features. The cost is a small amount of redundancy; the benefit is errors caught at the right place and clearer code.

A note on what Haskell’s polymorphism is and is not

Haskell’s polymorphism story is one of the language’s most distinctive features:

• Parametric polymorphism is fully inferred and the conventional foundation.
• Ad-hoc polymorphism through type classes admits behaviour that depends on type without sacrificing inference.
• Higher-kinded polymorphism admits abstracting over type constructors — the foundation of Functor/Monad/Applicative and a substantial part of what makes Haskell idioms distinctive.
• Rank-N polymorphism (with extensions) admits more elaborate patterns than mainstream alternatives admit.

The combination is more powerful than Java/C# generics or C++ templates; the trade-off is a steeper learning curve and more elaborate type errors. Reading non-trivial Haskell requires fluency with each form; writing it requires the discipline of recognising when each is appropriate.