Some notes on Immutability, Type Inference and Polymorphism

A Word About Immutability

Because Haskell is pure, it also means that functions can’t mutate (change) their inputs. Mutation is a side effect, and Haskell functions are only allowed output via their return value. This means that Haskell list functions always return a new list. In practice:

Prelude> list = [1,2,3,4]
Prelude> reverse list
[4,3,2,1]
Prelude> list
[1,2,3,4]
Prelude> drop 2 list
[3,4]
Prelude> list
[1,2,3,4]

This might seem very inefficient but it turns out it can be both performant and quite useful. We’ll get back to how Haskell data structures work in a later lecture.

A Word About Type Inference and Polymorphism

So what does a type like head :: [a] -> a mean? It means given a list that contains elements of any type a, the return value will be of the same type a.

In this type, a is a type variable. Type variables are types that start with a small letter, e.g. a, b, thisIsATypeVariable. A type variable means a type that is not yet known, or in other words a type that could be anything. Type variables can turn into concrete types (e.g. Bool) by the process of type inference (also called unification).

Let’s have a look at some examples. If we apply head to a list of booleans, type inference will compare the type of head’s argument, [a], with the type of the actual argument, [Bool] and deduce that a must be Bool. This means that the return type of head will in this case also be Bool.

head :: [a] -> a
head [True,False] :: Bool

The function tail takes a list, and returns a list of the same type. If we apply tail to a list of booleans, the return value will also be a list of booleans.

tail :: [a] -> [a]
tail [True,False] :: [Bool]

If types don’t match, we get a type error. Consider the operator ++ which takes two lists of the same type, as we can see from its type [a] -> [a] -> [a]. If we try to apply ++ to a list of booleans and a list of characters we get an error. This is what happens in GHCi:

Prelude> [True,False] ++ "Moi"

<interactive>:1:16:
    Couldn't match expected type `Bool' against inferred type `Char'
        Expected type: [Bool]
        Inferred type: [Char]
    In the second argument of `(++)', namely `"Moi"'
    In the expression: [True, False] ++ "Moi"

Type inference is really powerful. It uses the simple process of unification to get us types for practically any Haskell expression. Consider these two functions:

f xs ys = [head xs, head ys]
g zs = f "Moi" zs

We can ask GHCi for their types, and we will see that type inference has figured out that the two arguments to f must have the same type, since their heads get put into the same list.

Prelude> :t f
f :: [a] -> [a] -> [a]

The function g, which fixed one of the arguments of f to a string (i.e. [Char]) gets a narrower type. Type inference has decided that the argument zs to g must also have type [Char], since otherwise the type of f would not match the call to f.

Prelude> :t g
g :: [Char] -> [Char]

Sidenote: Some Terminology

In a type like [Char] we call Char a type parameter. A type like the list type that needs a type parameter is called a parameterized type.

The fact that a function like head can be used with many different types of arguments is called polymorphism. The head function is said to be polymorphic. There are many forms of polymorphism, and this Haskell form that uses type variables is called parametric polymorphism.

Sidenote: Type Annotations

Since Haskell has type inference, you don’t need to give any type annotations. However even though type annotations aren’t required, there are multiple reasons to add them:

1. They act as documentation
2. They act as assertions that the compiler checks: help you spot mistakes
3. You can use type annotations to give a function a narrower type than Haskell infers

A good rule of thumb is to give top-level definitions type annotations.

You can check your current points from the blue blob in the bottom-right corner of the page.