Haskell 2: Types and Type Inference

Part 2 of Haskell from First Principles.

Every well-typed Haskell expression has a type, and the compiler can often infer it without an annotation. A type describes more than a storage format: it tells us which operations are available, which arguments a function accepts, and how different expressions can be connected.

This block develops function types, currying, polymorphism, and type inference. Definitions belong in a .hs source file; ghci> examples are interactive sessions. Where an example replaces an earlier type signature, use it as an alternative definition rather than keeping two signatures for the same name.

2.1 What is a type?

These are expressions with explicit type annotations, suitable for entering in GHCi:

42       :: Int
True     :: Bool
'A'      :: Char
"hello"  :: String

The symbol :: means “has type.” The annotation on 42 specifically chooses Int; the unannotated literal can be used at several numeric types.

Type	Meaning	Example expression
Int	Bounded integer	42 :: Int
Integer	Arbitrary-precision integer	12345678901234567890 :: Integer
Bool	Boolean	True, False
Char	Character	'A'
String	List of characters	"hello"
Double	Double-precision floating point	3.14 :: Double

Type constructors such as Int and Bool begin with uppercase letters. Quotes distinguish two different types:

ghci> :type 'A'
'A' :: Char
ghci> :type "A"
"A" :: String

Single quotes form a character; double quotes form a string, even when it contains only one character.

Types constrain operations. 3 + 5 is valid, because addition is available for numeric types. This deliberately invalid expression is rejected during type checking:

3 + True
-- Expected type error: Bool has no Num instance.

The compiler can identify this incompatibility without evaluating the expression. That is the central idea of static type checking.

2.2 Functions also have types

A source-file definition can specify its input and output types:

square :: Int -> Int
square x = x * x
 
positive :: Int -> Bool
positive x = x > 0

square takes an Int and returns an Int. positive takes an Int and returns a Bool:

ghci> positive 5
True
ghci> positive (-2)
False

The general shape is InputType -> OutputType. The mathematical analogy is a mapping from one collection of values to another. Keep two limitations in mind: Int has a bounded range, unlike $\mathbb{Z}$, and a Haskell function type alone does not promise that evaluation terminates for every input.

A function is itself a value. Function types can therefore occur wherever other types can: as the type of an argument, a result, or a named binding.

2.3 Understanding ->: functions with multiple arguments

Consider:

add :: Int -> Int -> Int
add x y = x + y

The arrow associates to the right:

Int -> Int -> Int
= Int -> (Int -> Int)

add takes one Int and produces a function of type Int -> Int. Giving that function another Int produces the final result. This representation is called currying.

Expression	Type	Meaning
add	Int -> Int -> Int	Original function
add 3	Int -> Int	A function that adds three
add 3 5	Int	The result 8

Supplying only some arguments is partial application. We can give the resulting function a name in a source file:

addThree :: Int -> Int
addThree = add 3

Then:

ghci> addThree 10
13
ghci> addThree 20
23
ghci> :type add 3
add 3 :: Int -> Int

Use :type to inspect a function-valued expression. Entering add 3 alone at the prompt generally produces an error about displaying a function: functions do not have a standard Show instance. The expression itself is still well-typed.

Function application associates to the left, so add 3 5 means (add 3) 5.

Syntax	Associativity	Interpretation
f x y	Left	(f x) y
A -> B -> C	Right	A -> (B -> C)

These two rules explain why multiple-argument definitions and partial application fit together so naturally.

2.4 Functions can take functions as arguments

Here is a function whose first argument is itself a function:

applyTwice :: (Int -> Int) -> Int -> Int
applyTwice f x = f (f x)
 
double :: Int -> Int
double x = x * 2

Read the type from its outer structure: applyTwice accepts an Int -> Int function, then an Int, and produces an Int.

applyTwice double 3
= double (double 3)
= double 6
= 12

The parentheses around the first argument’s type matter:

Type	Interpretation
(Int -> Int) -> Int	Accept a function and return an integer
Int -> Int -> Int	Accept an integer and return a function

A function that accepts another function is a higher-order function. Block 6 studies this idea in more depth.

2.5 Polymorphism: what does a -> a mean?

Some functions do not need a particular concrete type:

identity :: a -> a
identity x = x

It works at many types:

ghci> identity (3 :: Int)
3
ghci> identity True
True
ghci> identity "abc"
"abc"

Here a is a type variable. A caller can choose a type for it, but all occurrences of that variable within one use must agree. The same function works uniformly whether a is Int, Bool, String, or another type. This is parametric polymorphism.

Mathematically, read the signature as an implicitly universally quantified statement:

$$\mathrm{identity}:\forall a.a\to a.$$

The forall is implicit in an ordinary signature like a -> a; no extra syntax is necessary here.

Repeated and different type variables communicate different relationships:

Type	Relationship
a -> a	Input and output have the same type
a -> b	Input and output types are not required to agree
a -> b -> a	Two arguments may have different types; result has the first argument’s type

For the last type:

first :: a -> b -> a
first x y = x

Evaluating first (3 :: Int) True returns 3, with a instantiated to Int and b to Bool.

Type signatures constrain possible implementations. In a total, pure, terminating setting, a function that must work uniformly at every type has very little freedom at type a -> a: it has an a available and no type-specific way to manufacture another one. Actual Haskell also permits nontermination and exceptions, so the signature alone does not guarantee that a result will be returned.

2.6 Type inference: how Haskell determines types

Start with this definition, without a signature:

notTrue x = not x

The compiler knows not :: Bool -> Bool. Consequently x must be a Bool, and the result is a Bool too:

notTrue :: Bool -> Bool

Inference propagates constraints imposed by the operations in an expression.

Now remove the integer-specific signature from our earlier applyTwice:

applyTwice f x = f (f x)

We can derive its most general type step by step:

1. Give x an unknown type a.
2. Because f is applied to x, give f the tentative type a -> b.
3. The inner f x therefore has type b.
4. The outer f takes that result as its argument. It is the same function, so its input type is still a.
5. The constraints require a and b to be equal.

Thus f :: a -> a, and the complete signature is:

applyTwice :: (a -> a) -> a -> a

This is more general than (Int -> Int) -> Int -> Int. For example, it also permits applyTwice not True, which evaluates to True.

Introducing unknown types and solving their equality constraints is the basic idea. The process of making types agree is called unification.

2.7 Understanding Num a => a -> a

An unannotated arithmetic function is usually more general than an Int function:

ghci> let square x = x * x
ghci> :type square
square :: Num a => a -> a

Break the signature into two pieces:

Piece	Meaning
a -> a	Input and output have the same type
Num a =>	That type must have a Num instance

A type class describes operations available for types that implement its interface. Num supplies numeric operations including multiplication. Standard Int, Integer, and Double types have Num instances:

ghci> square (3 :: Int)
9
ghci> square (3 :: Integer)
9
ghci> square (3.5 :: Double)
12.25

This deliberately invalid expression is rejected because Bool has no Num instance:

square True
-- Expected type error.

Some useful classes are:

Class	Available behavior	Example operation
Num	Numeric operations	+, *, -
Eq	Equality testing	==, /=
Ord	Ordering comparisons	<, >, <=
Show	Convert a value to a display string	show

For example, these are types to inspect, not definitions to copy into a source file:

(+)  :: Num a => a -> a -> a
(==) :: Eq a => a -> a -> Bool

Equality takes two values of the same type, requires an Eq instance for that type, and returns Bool. Arithmetic operators written in parentheses, such as (+), can be treated as ordinary function names.

Num a => a -> a is less general than a -> a: it only promises to work for numeric types. This introduction is enough to read inferred types; Block 7 develops type classes fully.

2.8 Why numeric literals are polymorphic

Even an integer literal does not intrinsically mean Int:

ghci> :type 3
3 :: Num a => a

All of these annotations are valid GHCi expressions:

3 :: Int
3 :: Integer
3 :: Double

The surrounding expression can choose the numeric type. This is part of why square x = x * x does not require an integer-specific signature.

Fractional literals have a different constraint:

ghci> :type 3.5
3.5 :: Fractional a => a

Fractional supplies operations such as /; Int and Integer are not instances of it. Hence 3.5 :: Int is invalid even though 3 :: Double is valid. Numeric literal overloading is specified in the Haskell Report.

When an expression must be evaluated at a concrete type and the context has not selected one, numeric defaulting rules may choose a suitable type. This lets GHCi display 3 + 5 without requiring an explicit annotation. An inferred polymorphic type and the concrete type selected for displaying one result are different things.

2.9 Type checking versus evaluation

Consider square (3 + 5) using the unannotated numeric square above.

Type checking asks whether the expression fits together. The literals can use the same numeric type, addition returns that type, and square accepts it. Evaluation asks what happens when a result is demanded:

square (3 + 5)
= square 8
= 64

These questions are separate. An expression may be well-typed and still fail during evaluation:

1 `div` 0 :: Int

This is a validly typed GHCi expression, but evaluating it raises a division-by-zero exception. A well-typed expression can also run forever.

In contrast, this example is rejected before evaluation:

not 3
-- Expected type error: not requires Bool, and Bool is not numeric.

There is no wrong Boolean answer to inspect; the arguments do not satisfy the operation’s type.

2.10 The grammar of Haskell types

Here is a simplified grammar for the types seen so far:

Type :=
    TypeName
  | TypeVariable
  | Type -> Type
  | (Type)
 
QualifiedType :=
    Type
  | Constraint => Type

Examples of type expressions include:

Int
Bool
Int -> Bool
a -> a
(a -> b) -> a -> b
Num a => a -> a
Eq a => a -> a -> Bool
(Eq a, Show a) => a -> String

The last example requires both equality testing and conversion to a display string. It shows the syntax for several constraints; an implementation need not use every permitted operation.

Remember the naming and grouping conventions: type constructors such as Int begin with uppercase letters, type variables such as a begin with lowercase letters, -> groups to the right, => separates constraints from the rest of the type, and parentheses override the default grouping.

2.11 Exercises

Infer each type before opening the answer. Definitions shown here are independent source-file examples.

Exercise 1: return the argument

f x = x

Show solution

f :: a -> a

No operation constrains the argument’s type, and the result is that same argument.

Exercise 2: return the first argument

f x y = x

Show solution

f :: a -> b -> a

The arguments can have unrelated types. The result shares the first argument’s type.

Exercise 3: add one

f x = x + 1

Show solution

f :: Num a => a -> a

Addition requires Num a. Both operands and the result have the same numeric type.

Exercise 4: supply one argument

Given:

add :: Int -> Int -> Int
add x y = x + y

What is the type of the expression add 3?

Show solution

add 3 :: Int -> Int

The first argument has been supplied; the resulting function accepts the second Int.

Exercise 5: compose two functions

compose f g x = f (g x)

Show solution

compose :: (b -> c) -> (a -> b) -> a -> c

g accepts an a and returns a b. That result becomes the input to f, which returns a c. The complete calculation therefore maps an a to a c.

Functions are ordinary values, and their types can describe other functions as inputs or outputs. Type inference reveals those relationships by solving constraints rather than by running the program. Next we will use expressions to make decisions and introduce local names.

Adapted from Block 2 of the original GPT-produced Haskell tutorial.

Previous: Haskell 1: Expressions and Functions. Next: Haskell 3: Conditionals, Local Bindings, and Guards.