22 Pattern Matching with Lists

We've seen that pattern matching lets us:

• Match the shape of data
• Extract parts of data

What if we want to match with lists? Lists can only be two things

• nil
• the cons of an element onto another list

We can use pattern matching to access the list in one of those ways.

let empty lst =
	match lst with
	| [] -> true
	| h :: t -> false;;

val empty : 'a list -> bool = <fun>

Here, we have a function that determines if a list is empty. It determines if the list is nil, and if so, matches it to true, and if it is the cons of an element and a list, it matches it to false.

let rec sum lst =
	match lst with
	| [] -> 0
	| h :: t -> h + sum t;;

val sum : int list -> int = <fun>

Here, we recurse through the list using pattern matching to take the sum of a list.

h is an element in the list, and t is the rest of the list.

sum [];;

- : int = 0

sum [1;2;3;4];;

- : int = 10

We can actually see what's happening under the hood, thanks to utop (which powers this Jupyter Notebook)

#trace sum

sum is now traced.

sum [1;2;3];;

sum <-- [1; 2; 3]
sum <-- [2; 3]
sum <-- [3]
sum <-- []
sum --> 0
sum --> 3
sum --> 5
sum --> 6

- : int = 6

Every time you see sum <--, sum is being called with the values on the right side. Every time you see sum -->, sum is returning the value on the right side. We can actually see our values accumulate here!

Now that we're done with this cool demo, we can untrace sum.

#untrace sum

sum is no longer traced.

sum [1;2;3];;

- : int = 6

Let's write a function to find the length of a list now!

let rec length lst =
	match lst with
	| [] -> 0
	| h :: t -> 1 + length t;;

val length : 'a list -> int = <fun>

length [];;

- : int = 0

length [1, 2, 3];;

- : int = 1

Now let's write a function that appends to lists.

(** [append lst1 lst2] combines [lst1] and [lst2]

	example usage:
	| append [1; 2; 3] [4; 5; 6] is [1; 2; 3; 4; 5; 6;]
*)
let rec append lst1 lst2 =
	match lst1 with
	| [] -> lst2
	| h :: t -> h :: append t lst2;;

val append : 'a list -> 'a list -> 'a list = <fun>

append [1; 2; 3] [4; 5; 6]

- : int list = [1; 2; 3; 4; 5; 6]

By the way, most of these functions are built into the standard library, and append is even a built in operator (@). You can see the standard library implementation for OCaml 4.11 (the version we're using) here. This is the implementation:

let rec rev_append l1 l2 =
  match l1 with
    [] -> l2
  | a :: l -> rev_append l (a :: l2)

Notice it's the same implementation that we just wrote!