Haskell 4: Lists, Pattern Matching, and Recursion

Part 4 of Haskell from First Principles.

Examples are small expressions or definitions to try independently in GHCi or a source file. Later versions of a function replace earlier versions; do not paste every alternative into the same module.

Parts 1–3 established functions, types, and conditional logic. This article builds collection processing from that foundation.

Three central ideas now fit together:

1. Lists: How to represent collections of values.
2. Pattern matching: How to decompose data structures.
3. Recursion: How to process data without using imperative loops.

A particularly important insight is that these three ideas fit together naturally. In Haskell, a list is a recursively defined data structure, and recursion follows directly from that structure.

The grammar leads directly to the programming techniques.

---

4.1 Lists: the basic syntax

A list is a collection of values of the same type.

For example:

[1, 2, 3]
 
[True, False, True]
 
["apple", "banana", "orange"]

These are valid type annotations:

[1, 2, 3]                   :: [Int]
[True, False, True]         :: [Bool]
["apple", "banana", "orange"] :: [String]

The notation [Int] means “a list of machine-sized integers.” The annotation chooses Int; without it, a numeric list such as [1,2,3] can have a more general type, Num a => [a], before interactive defaulting.

More generally:

[a]

means “a list whose elements have type a.”

Recall from Block 2 that a is a type variable.

Lists are homogeneous

In Python, we can write:

[1, True, "hello"]

But in Haskell, this is invalid:

[1, True, "hello"]

All list elements must have the same type.

This is a consequence of Haskell’s static type system.

The empty list

Haskell uses:

[]

to denote the empty list.

Interestingly, its type is polymorphic:

[] :: [a]

The empty list can be used as a list of any element type.

For example:

[] :: [Int]
[] :: [Bool]
[] :: [String]

All of these are valid.

This makes sense: an empty list contains no elements that could violate an element-type requirement.

---

4.2 The fundamental list constructor: :

The notation:

[1, 2, 3]

is convenient, but there is a more fundamental way to construct lists.

Haskell has a constructor called : (pronounced cons).

For example:

1 : [2, 3]

produces:

[1, 2, 3]

The expression x : xs constructs a new list by placing the element x in front of the existing list xs.

Its type is:

(:) :: a -> [a] -> [a]

Let us interpret this using the type-system concepts from Block 2.

The constructor takes an element of type a and a list of elements of type a, and returns another list of elements of type a.

Every finite list can be built using : and []

For example:

[1]       = 1 : []
 
[1, 2]    = 1 : (2 : [])
 
[1, 2, 3] = 1 : (2 : (3 : []))

The constructor : is right-associative.

Therefore:

1 : 2 : 3 : []

means:

1 : (2 : (3 : []))

and evaluates to:

[1, 2, 3]

head 1 -> head 2 -> head 3 -> []
  :         :         :

Each cons constructor contains a head element and a tail list; the final tail is empty.

This suggests an important structural observation:

A list is either empty, or consists of a head element and another list (its tail).

There are exactly two possibilities:

$$\mathrm{List}(a)=\mathrm{Empty}\text{or}\mathrm{Cons}(a,\mathrm{List}(a)).$$

This is the recursive structure underlying Haskell lists.

The same structure appears in the custom algebraic data types in Part 5.

: versus ++

These operators have different meanings:

1 : [2, 3]       -- [1, 2, 3]
 
[1] ++ [2, 3]    -- [1, 2, 3]

These are valid type annotations:

(:)  :: a -> [a] -> [a]
 
(++) :: [a] -> [a] -> [a]

The first prepends a single element. The second concatenates two lists.

For example:

[1, 2] ++ [3, 4]   -- [1, 2, 3, 4]

The following is invalid:

1 ++ [2, 3]

because ++ expects a list as its first argument.

---

4.3 Pattern matching: decomposing a list

Now suppose we want to write a function that extracts the first element of a list.

A natural implementation is:

first (x:xs) = x

This introduces one of Haskell’s most distinctive syntactic features: pattern matching.

Let us examine the definition carefully.

The expression:

x:xs

appears in the parameter position of the function definition.

It is therefore a pattern, not an expression that constructs a new list.

The pattern says:

Match a nonempty list, bind its first element to x, and bind the remaining list to xs.

For example:

first [10, 20, 30]

matches:

x  = 10
xs = [20, 30]

Therefore, the result is 10.

Pattern syntax

Some common list patterns are:

Pattern	What it matches
[]	Empty list
x:xs	Nonempty list
[x]	List with exactly one element
[x,y]	List with exactly two elements
x:y:xs	List with at least two elements
_	Anything, without binding a name

A pattern can bind values to names or constrain the shape of the data.

Consider:

describe :: [Int] -> String
 
describe [] = "empty"
describe [x] = "one element"
describe (x:y:xs) = "at least two elements"

Examples:

describe []          -- "empty"
describe [5]         -- "one element"
describe [5, 8]      -- "at least two elements"
describe [5, 8, 10]  -- "at least two elements"

Notice that different equations of the same function can have different patterns.

The equations are tried from top to bottom until one matches.

What does [x] mean as a pattern?

Recall:

[x] = x : []

The same equivalence holds for patterns.

Thus:

first [x] = x

only matches singleton lists.

But:

first (x:xs) = x

matches every nonempty list.

This distinction is important.

A potential problem

What happens when we evaluate:

first []

The pattern x:xs cannot match the empty list.

Therefore, evaluation fails with a non-exhaustive pattern-match error.

We can avoid this by defining a fallback value:

firstOr :: a -> [a] -> a
 
firstOr fallback [] = fallback
firstOr fallback (x:xs) = x

For example:

firstOr 0 []          -- 0
firstOr 0 [5, 6, 7]   -- 5

This function handles both possible list shapes.

That is the basic idea of exhaustive pattern matching: covering every possible constructor of the input type.

---

4.4 The wildcard pattern _

Sometimes a function doesn’t need every part of the input.

Consider:

isEmpty :: [a] -> Bool
 
isEmpty [] = True
isEmpty (x:xs) = False

This is valid, but the variables x and xs are never used.

We can instead write:

isEmpty :: [a] -> Bool
 
isEmpty [] = True
isEmpty (_:_) = False

The underscore _ is a wildcard pattern.

It means “match any value, but don’t give it a name.”

For example:

second :: [a] -> a
 
second (_:x:_) = x

This extracts the second element of lists having at least two elements.

second [10, 20, 30]   -- 20

It is undefined for shorter lists and causes a pattern-match failure.

A useful observation: x:xs is a pattern over a structure, while x alone is a variable pattern that matches any value.

---

4.5 Recursion: processing a list without loops

We now have all the ingredients for recursion.

Suppose we want to sum a list of numbers:

[1, 2, 3, 4]

In Python, we might write:

total = 0
for x in xs:
    total += x

This algorithm uses a mutable accumulator and a loop.

In Haskell, we can instead define the sum mathematically.

Let $S(xs)$ denote the sum of list xs.

We have:

$$S([])=0.$$

For a nonempty list:

$$S(x:xs)=x+S(xs).$$

These two equations completely define summation over finite lists.

The Haskell implementation is almost identical:

sumList :: Num a => [a] -> a
 
sumList [] = 0
sumList (x:xs) = x + sumList xs

Let us understand this in detail.

The first equation:

sumList [] = 0

is the base case.

The second equation:

sumList (x:xs) = x + sumList xs

is the recursive case.

It reduces the problem to a smaller list.

Step-by-step evaluation

Consider:

sumList [1, 2, 3]

Since [1,2,3] = 1 : [2,3], the second equation applies.

$$\begin{array}{rl}S([1,2,3])& =1+S([2,3])\\ & =1+(2+S([3]))\\ & =1+(2+(3+S([])))\\ & =1+(2+(3+0))\\ & =6.\end{array}$$

sumList [1,2,3]
1 + sumList [2,3]
1 + (2 + sumList [3])
1 + (2 + (3 + sumList []))
1 + (2 + (3 + 0))

Why does recursion terminate?

For a finite list, every recursive call removes one element:

[1,2,3]
[2,3]
[3]
[]

Eventually the function reaches the base case.

This is called structural recursion: recursion follows the structure of the input data.

It’s especially useful in functional programming because we can often prove program correctness using mathematical induction on the data structure.

For infinite lists, sumList generally does not terminate because it never reaches [].

---

4.6 Another example: computing list length

Let us write a function that returns the length of a list.

Mathematically:

$$L([])=0$$

and

$$L(x:xs)=1+L(xs).$$

In Haskell:

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

For example:

lengthList []           -- 0
lengthList [5]          -- 1
lengthList [5, 8, 10]   -- 3

Why does lengthList have type:

[a] -> Int

rather than:

[Int] -> Int

Because the function doesn’t care about the type of list elements.

It only inspects the structure of the list.

This is another example of parametric polymorphism from Block 2.

Comparing sum and length

Function	Base case	Recursive case
sumList	0	x + sumList xs
lengthList	0	1 + lengthList xs

Notice how similar they are.

Both traverse the recursive structure of a finite list. The only difference is how they combine the current element with the recursively computed result.

This recurring pattern is captured by foldr, studied in Part 6.

---

4.7 Recursion can also construct new lists

So far, recursion has reduced lists to numbers.

But we can also use recursion to build a new list.

Suppose we want to double every element:

doubleAll :: Num a => [a] -> [a]
 
doubleAll [] = []
doubleAll (x:xs) = (2*x) : doubleAll xs

For example:

doubleAll [1,2,3]

evaluates to:

[2,4,6]

Why?

$$\begin{array}{rl}D([1,2,3])& =2:D([2,3])\\ & =2:(4:D([3]))\\ & =2:(4:(6:D([])))\\ & =2:(4:(6:[]))\\ & =[2,4,6].\end{array}$$

Notice that : is used in the output.

This function does not modify the original list. It constructs a new list.

Another example: filtering positive values

positives :: (Num a, Ord a) => [a] -> [a]
 
positives [] = []
 
positives (x:xs)
  | x > 0     = x : positives xs
  | otherwise = positives xs

For example:

positives [-3, 5, 0, 8, -2]

returns:

[5,8]

Here we have combined three concepts:

• Pattern matching: x:xs
• Guards: x > 0
• Recursion: positives xs

This is a common style of functional programming.

---

4.8 The case ... of ... expression

So far, we’ve used pattern matching in function definitions.

But Haskell also supports pattern matching directly inside expressions through case.

The general syntax is:

case expression of
  pattern1 -> expression1
  pattern2 -> expression2
  ...

For example:

describe :: [Int] -> String
 
describe xs =
  case xs of
    []      -> "empty"
    [_]     -> "one element"
    (_:_:_) -> "two or more elements"

Here, case xs of ... is an expression whose value depends on which pattern matches xs.

Notice the syntax difference:

In a function equation:

describe [] = "empty"

In a case expression:

[] -> "empty"

The arrow -> separates the pattern from its result expression.

Why do we need case?

Consider:

f x =
  let ys = computeSomething x
  in case ys of
       []     -> 0
       (z:_)  -> z

Assume computeSomething :: Int -> [Int] is a function defined elsewhere.

We first construct a value ys, then inspect its structure with case.

Unlike pattern matching in function parameters, case can inspect an arbitrary expression.

An important semantic detail

Haskell pattern matching is generally top-down and left-to-right.

The first matching alternative is selected.

For example:

f xs =
  case xs of
    (_:_) -> "nonempty"
    [x]   -> "singleton"
    []    -> "empty"

The singleton alternative is unreachable: a singleton list already matches (_:_).

Haskell compilers often warn about redundant patterns.

Constructor matching evaluates only as much of the input as needed to distinguish its outer structure. It need not evaluate every element: isEmpty [undefined] is False, because the outer (:) constructor is available even though its element is undefined.

---

4.9 List comprehensions

Haskell also has concise syntax for building lists, called list comprehensions.

Suppose we want the squares of the integers from 1 to 5.

We can write:

[x*x | x <- [1..5]]

The result is:

[1,4,9,16,25]

Let us break this down.

[ result | variable <- source ]

The expression before | specifies what to produce.

The expression after <- specifies the list from which values are drawn.

The notation:

[1..5]

is list enumeration syntax, denoting:

[1,2,3,4,5]

Adding a filter

For example:

[x*x | x <- [1..5], odd x]

returns:

[1,9,25]

Here odd x is a Boolean condition filtering the values.

This is similar to Python’s:

[x*x for x in range(1,6) if x % 2 == 1]

But in Haskell, the result is an ordinary list expression.

List comprehensions can have multiple generators:

[(x,y) | x <- [1,2], y <- [3,4]]

which evaluates to:

[(1,3),(1,4),(2,3),(2,4)]

The values (1,3) and so on are tuples, which are different from lists because their components can have different types. We will study tuples more carefully in the next block.

List comprehensions are convenient syntax, but recursion and higher-order functions can express the same computations.

---

4.10 A glimpse of infinite lists and laziness

Here’s something unusual about Haskell.

We can define an infinite list:

ones :: [Int]
ones = 1 : ones

This is a recursive definition.

Mathematically, the list has the structure:

$$[1,1,1,1,\dots ].$$

The surprising fact is that Haskell can work with this list:

take 5 ones

returns:

[1,1,1,1,1]

The built-in take function extracts a prefix of a list.

Why doesn’t constructing ones immediately cause infinite recursion?

Because Haskell uses lazy evaluation. It does not have to construct every element before we begin using the list.

Instead, it can evaluate only the portion needed to compute the requested result.

But:

sumList ones

does not terminate because summing all elements requires traversing the entire infinite list.

Laziness means that demand, rather than the written order alone, controls evaluation.

For now, the important point is that recursive data structures can be defined independently of how much of them is evaluated.

---

4.11 The grammar we have learned

We can now extend our simplified Haskell grammar.

List expressions

Expression :=
    ...
  | []
  | [Expression, ..., Expression]
  | Expression : Expression
  | Expression ++ Expression

For example:

[]
[1,2,3]
1 : [2,3]
[1,2] ++ [3,4]

Patterns

Pattern :=
    variable
  | _
  | []
  | Pattern : Pattern
  | [Pattern, ..., Pattern]

For example:

x
_
[]
x:xs
[x]
[x,y]

The distinction between an expression and a pattern is important.

In:

1 : [2,3]

we are constructing a value.

In:

f (x:xs) = ...

we are destructuring a value.

Function equations

FunctionEquation :=
    name Pattern ... Pattern = Expression

A function can have multiple equations:

f [] = ...
f (x:xs) = ...

Case expressions

Expression :=
    ...
  | case Expression of
      Pattern -> Expression
      Pattern -> Expression
      ...

Actual Haskell syntax also has precedence, layout, and additional pattern forms. But these simplified rules cover the key ideas in this block.

---

4.12 Exercises

These exercises emphasize understanding the grammar and deriving programs from the recursive list structure.

Try each exercise before opening its solution. The undefined expressions in skeletons mark code to replace; evaluating an unfinished skeleton raises an error.

Exercise 4.1

Evaluate the list expression.

1 : 2 : [3,4]

Solution

[1,2,3,4]

The colon is right-associative: 1 : (2 : [3,4]). Each colon prepends one element.

Exercise 4.2

Find the result.

lengthList [10,20,30,40]

Solution

4

Each recursive step removes one element and contributes 1. The empty list contributes 0.

Exercise 4.3

Apply this function to [1,2,3].

f [] = []
f (x:xs) = (x+1) : f xs

Solution

f [1,2,3]  -- [2,3,4]

The function adds 1 to each element and recursively processes the tail.

Exercise 4.4

Explain the type error.

[1,2] : [3,4]

Solution

[1,2] ++ [3,4]  -- [1,2,3,4]
[1,2] : [[3,4]] -- [[1,2],[3,4]]

In the ordinary Prelude, this expression is ill-typed. If the left operand of (:) is a list of numbers, its right operand must be a list of lists of numbers. Concatenation and prepending a nested list are different operations.

Exercise 4.5

Write a function that computes the product of a list.

productList :: Num a => [a] -> a
productList [] = undefined
productList (x:xs) = undefined

Solution

productList [] = 1
productList (x:xs) = x * productList xs

The empty product is 1; a nonempty list contributes its head multiplied by the product of its tail.

Exercise 4.6

Reverse a list using recursion.

reverseList :: [a] -> [a]
reverseList [] = undefined
reverseList (x:xs) = undefined

Solution

reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]

Reverse the tail, then append the original head. For a finite list of length n, repeatedly traversing the left operand of (++) makes this version take quadratic time. An accumulator-based implementation can reverse a list in linear time.

---

4.13 A deeper mathematical perspective

Structural recursion also gives a way to reason about correctness.

The definition:

sumList [] = 0
sumList (x:xs) = x + sumList xs

is not merely a programming trick.

It follows directly from the recursive definition of a list.

Every finite list is constructed using two possibilities:

$$L=[]\text{or}L=x:xs.$$

Therefore, to define a function on lists, we can specify its behavior on these two constructors.

This is exactly the same structure that appears in mathematical induction:

• Base case: Prove the property for the empty list.
• Inductive step: Assuming the property holds for xs, prove it for x:xs.

For example, suppose we want to prove that lengthList returns the number of elements of every finite list. We prove correctness by induction on the list’s structure.

This connection between data construction, recursive computation, and inductive proof is one of the most elegant aspects of functional programming.

The same principle applies to trees, syntax expressions, and other recursively defined structures.

4.14 Summary

Concept	Syntax	Meaning
List	[1,2,3]	A homogeneous collection
Empty list	[]	Base constructor
Cons	x:xs	Construct a list
Pattern matching	f (x:xs) = ...	Decompose a list
Wildcard	_	Match without binding
Recursion	f (x:xs) = ... f xs	Compute over recursive structure
Case expression	case xs of ...	Pattern matching inside an expression
Comprehension	[f x | x <- xs]	Construct lists declaratively

The central insight of this block is:

The recursive structure of data naturally determines the recursive structure of functions that process it.

Part 5 applies the same reasoning to custom data structures.

---

← Part 3 · Series index · Part 5 →

Adapted from Block 4 of the GPT-produced Haskell tutorial, with editorial and technical corrections.