Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 57 ยท Defining types

Parametric Polymorphism and Type Variables

Understand Haskell type variables, parametric polymorphism, what a signature like a -> a can and cannot do, and how class constraints narrow it.

Take the function length. It counts the elements of a list of numbers, a list of strings and a list of lists, and it never looks at the elements. Its type says so: length :: [a] -> Int (strictly, Foldable t => t a -> Int, but the list version is easiest to read). The lowercase a is a type variable, a placeholder that can be replaced by any concrete type.

Functions with type variables are called parametrically polymorphic. This lesson shows how to read them, why they are surprisingly restricted, and how class constraints let you do more when you need to. You should already know basic signatures from Basic Types and Type Signatures.

All Haskell blocks here are read-only because the site does not run a Haskell compiler. Comparisons with other languages are given in prose.

Type variables

Concrete types start with a capital letter (Int, Bool, Maybe). Type variables start with a lowercase letter and stand for "any type, the same one everywhere in this signature":

HASKELL
identity :: a -> a
identity x = x

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

firstOf :: [a] -> Maybe a
firstOf []      = Nothing
firstOf (x : _) = Just x

In swap, a and b are different variables, so they may be different types (or the same). Whenever you use the function, GHC works out a concrete type for each variable. For swap (1 :: Int, "hi") it picks a = Int and b = String. You never write the instantiation yourself.

Formally, signatures such as a -> a are shorthand for forall a. a -> a: the function works for all types a. You can turn that spelling on with an extension, but you rarely need to.

Reading a polymorphic type

Lowercase = variable a, b, t stand for any type.
Same letter, same type In a -> a the input and output match.
Picked per use GHC fills in the concrete types at each call.
1 / 2

The signature limits the code

Here is the part that surprises newcomers. Try to write a function of type a -> a. The function must work for every possible a, and it knows nothing about a: it cannot add, compare or print it. What can it do with a value of a completely unknown type? Only return it.

HASKELL
identity :: a -> a
identity x = x

(Ignoring tricks such as undefined or an infinite loop, this is the only total function with that type.) Similarly:

HASKELL
-- The only sensible total implementations:
f :: a -> b -> a
f x _ = x

g :: (a, b) -> a
g (x, _) = x

This is the seed of an idea called parametricity. Because a polymorphic function cannot inspect its values, it must treat all types uniformly. A consequence is that you can tell a lot about a function from its type alone.

Consider rearrange :: [a] -> [a]. It cannot invent new elements, since it has no way to make an a out of nothing. It also cannot look inside elements to decide what to do. So whatever it does, it only shuffles, drops or duplicates the elements it was given, and it makes the same structural choices no matter what the elements are. For that reason, applying map f before or after rearrange gives the same result:

HASKELL
rearrange (map f xs) == map f (rearrange xs)

This kind of law, obtained from the type with no code in sight, is called a free theorem (Philip Wadler's phrase "theorems for free"). It is why reverse, take 3 and tail all commute with map. You do not need the proof to benefit: just remember that a more general type means fewer possible behaviours, and that makes code easier to trust.

Adding constraints

Sometimes you do need to compare or print. Then the signature must say so with a class constraint, written before =>:

HASKELL
largest :: Ord a => [a] -> a
largest = foldr1 max

describe :: Show a => a -> String
describe x = "Value: " ++ show x

sumAndCount :: (Num a) => [a] -> (a, Int)
sumAndCount xs = (sum xs, length xs)

Ord a => ... reads "for any type a that has an Ord instance". Inside the function you may use only what the constraint grants: <, max and friends for Ord; show for Show; arithmetic for Num. Using + without a Num a constraint is a type error: GHC reports "No instance for (Num a) arising from a use of '+'" and suggests the missing constraint.

Constraints do not break the uniformity idea; they just widen the toolbox in a controlled way. You can list several with a tuple, (Ord a, Show a) => .... The classes themselves are introduced in Type Classes: Eq, Ord, Show, Read, Num, and you will write your own in Defining Your Own Type Classes and Instances.

Prefer the most general signature that still compiles. If your function only needs Eq, don't ask for Ord; if it works on any list, don't fix the element type to Int. A general type documents what the function cannot do.

Polymorphic data types

Data types take type variables too. Maybe a, Either e a, [a] and your own Tree a from Recursive Data Types and Trees are all polymorphic. Type constructors such as Maybe and [] are themselves functions from types to types, which is why Maybe alone, without an argument, is not a complete type. That idea returns when you meet Functor in Functors.

HASKELL
data Pair a b = Pair a b

mapFirst :: (a -> c) -> Pair a b -> Pair c b
mapFirst f (Pair x y) = Pair (f x) y

Polymorphism you will see elsewhere

Other languages have related features, but Haskell's flavor is the one above. In Java you would reach for generics and in C++ for templates. Those are similar in spirit, though a Java generic method can still call equals on anything because every object has it, while Haskell gives you nothing unless the constraint says so.

There is also ad hoc polymorphism, where the behaviour does differ per type (show 1 and show True run different code). That is what type classes provide. Parametric polymorphism means one body for all types; ad hoc polymorphism means one name with a different body per instance.

Try the idea in a stand-in

JavaScript has no static types here, so this stand-in can only imitate the behaviour: a function that never inspects its elements commutes with map, while one that does (like sorting by a comparison) does not. Real Haskell proves the first case from the type alone.

JS Free theorem check (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The last line prints false: sort is allowed to look at the elements (its type has Ord a), and a function like f changes how they compare. Functions with no constraint cannot be fooled that way.

JS Constraints as passed-in capabilities (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

GHC does pass such "dictionaries" for you when it compiles a constrained function, though the details are an implementation matter and optimisation often removes them.

Higher-rank types (a quick mention)

Normally the forall sits at the far left, so the caller chooses a. With the RankNTypes extension, you can ask for an argument that is itself polymorphic:

HASKELL
# LANGUAGE RankNTypes #

applyToBoth :: (forall x. [x] -> Int) -> ([Int], String) -> (Int, Int)
applyToBoth f (xs, s) = (f xs, f s)

Here the caller must pass a function that works for every x, such as length, and applyToBoth uses it at two different types. Without RankNTypes, a lambda argument gets one fixed type per call. Higher-rank types appear in library internals such as ST; as a beginner you can skip them.

Common stumbling blocks

  • Rigid type variable errors. If your signature says a -> a but your code returns an Int, GHC complains that it "couldn't match expected type a with actual type Int" and calls a a rigid type variable. The signature promised any type, so the body must deliver it.
  • Ambiguous types. If a constrained variable never appears in the result or arguments, GHC cannot pick it. show (read "5") is the standard example; add an annotation such as read "5" :: Int.
  • Overly narrow signatures. Writing Int where a would do blocks reuse, but don't over-generalise either: when a constraint is missing, the error message tells you which one to add.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the signature swap :: (a, b) -> (b, a), what do the lowercase letters mean?

    Lowercase names in a type are type variables; a and b may be different types, and GHC infers them at each use.
  2. 2. Why can a total function of type a -> a only return its argument?

    With no constraint, the function can do nothing with an unknown type except pass the value along.
  3. 3. What does Ord a => [a] -> a promise and require?

    The constraint limits the types to those with an Ord instance and allows comparison operations inside the body.
  4. 4. What is the difference between parametric and ad hoc polymorphism?

    length uses one body for every element type, while show picks a different implementation per instance.

Summary

  • A lowercase name in a type is a type variable; GHC picks concrete types at each use.
  • a -> a means "for all a"; a function that knows nothing about its input can only pass it along.
  • The more general the type, the fewer behaviours are possible, which gives free theorems such as commuting with map.
  • Class constraints like Ord a => or Show a => allow specific operations on the variable.
  • Parametric polymorphism uses one body for all types; type classes give ad hoc polymorphism.
  • Rigid type variable and ambiguous type errors usually mean a signature promises more or less than the code delivers.

Next: Defining Your Own Type Classes and Instances.