Have you ever found yourself writing long, cumbersome if-else chains in your code, just to handle a few different cases? If so, you'll want to learn about pattern matching. In this post, we'll explore the basics of pattern matching and how it can help you write cleaner, more concise code. We'll also look at some examples of how pattern matching can be used to solve common problems in programming.
What is Pattern Matching?
Pattern matching is a mechanism for checking a value against a pattern and, based on the match, performing some kind of action. It is a fundamental feature of many programming languages, such as Haskell, Rust and ML languages including OCaml.
The basic idea behind pattern matching is simple: you define a pattern and provide some code to be executed if the pattern matches. All of the code examples in this post are in OCaml syntax because it is very readable and easy to understand. Consider the following example:
(* basic.ml *)
let greet name =
match name with
| "nexxel" -> print_string "Hi, nexxel!"
| "Ludwig" -> print_string "Crazy how you look exactly like Mogul Mail"
| _ -> print_string "Who are you?"
Here we have defined a function called greet
that takes a single argumentname
. The match
keyword is used to define a pattern match, and the with
keyword is used to specify the different patterns to be matched.
The first pattern is "nexxel" -> print_string "Hi, nexxel!"
, which means that if name
is equal to "nexxel"
, it will execute the print statement. Similarly, if name
is equal to "Ludwig"
it will execute the respective print statement. The last pattern is _ -> print_string "Who are you?"
, which means that if name
is anything other than "nexxel" or "Ludwig", it will print "Who are you?".
This is a very basic example of pattern matching, but it illustrates the core concept: you define a pattern and provide some code to be executed if the pattern matches. You might think how is this better than using an if-else statement? We'll see how pattern matching helps in simplifying complex conditional logic with less mental effort.
Why Use Pattern Matching?
Pattern matching allows you to express complex conditionals in a concise and declarative way. Let's look at another example which is a function to calculate the factorial of a number.
(* factorial.ml *)
let rec factorial n =
match n with
| 0 -> 1
| n -> n * factorial (n - 1)
This code uses a recursive function (rec
is used to define recursive functions) and pattern matching to calculate the factorial of a given number. The pattern 0
is matched if n
is equal to 0
, in which case the function returns 1
. Otherwise, the pattern n
is matched, and the function calls itself with n - 1
as the argument.
This code is much simpler and easier to understand than an equivalent implementation using an imperative loop. In addition, it is more declarative, as it specifies what should be done rather than how it should be done. Here's an imperative implementation of the same function in Python:
# factorial.py
def factorial(n):
def loop(i, acc):
if i > n:
return acc
else:
return loop(i + 1, acc * i)
return loop(1, 1)
The declarative way of doing things is much more concise and easier to reason. Let's explore some more examples to see how pattern matching is used in practice.
Pattern Matching in Practice
Conditionals
We already saw the factorial example, but let's take another example to calculate the nth term of the Fibonacci sequence.
(* fibonacci.ml *)
let rec fib n =
match n with
| 0 -> 0
| 1 -> 1
| n -> fib (n - 1) + fib (n - 2)
Here, the fib
function uses pattern matching to define three cases:
- If
n
is equal to0
, it returns0
. - If
n
is equal to1
, it returns1
. - If
n
is neither0
nor1
, the function calls itself withn - 1
andn - 2
as arguments and returns the sum of the two results.
Here's an imperative implementation of the same function in TypeScript:
// fibonacci.ts
const fib = (n: number): number => {
if (n === 0) {
return 0;
} else if (n === 1) {
return 1;
} else {
let a = 0;
let b = 1;
for (let i = 2; i <= n; i++) {
[a, b] = [b, a + b];
}
return b;
}
};
If you look at the code, you'll see that it is much more verbose than the declarative version. It also uses mutable variables, which can be error-prone. Moreover, it is not very easy to understand what the code is doing. Although this can be improved and be written in a declarative way using recursion.
// fibonacci.ts
const fib = (n: number): number => {
if (n === 0) {
return 0;
} else if (n === 1) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
};
This version is much more readable and concise, but it is still not as concise and satisfying to read and write as the pattern matching version.
Usage with Algebraic Data Types
Pattern matching is also used with algebraic data types, which are composite data types that are built up from simpler data types using a set of constructors.. Consider the following example to represent a binary tree:
(* binary_tree.ml *)
type tree =
| Leaf
| Node of int * tree * tree
let binary_tree = Node(1, Node(2, Leaf, Leaf), Node(3, Leaf, Leaf))
The tree
type is an ADT, where the value of type tree
can either be a Leaf
or Node
. This ADT has two constructors: Leaf
and Node
. The Leaf
constructor takes no arguments and represents a leaf node, i.e. a node with no subtrees. The Node
constructor takes three arguments: an integer value, and two subtrees.
Now that we have defined the tree
ADT, we can use it to create a binary tree. The binary_tree
variable is a tree
value that represents the following binary tree:
1
/ \
2 3
/ \ / \
Now we can use pattern matching to deconstruct the tree
value and perform different actions based on its structure. For example, we can write a function that sums the values of all leaf nodes in a tree:
(* binary_tree.ml *)
let rec sum_tree tree =
match tree with
| Leaf -> 0
| Node(value, left, right) -> value + sum_tree left + sum_tree right
(* let () = print_int (sum_tree binary_tree) *)
(* 6 *)
The sum_tree
function takes a tree
value as an argument and uses pattern matching to deconstruct it. If the tree is a Leaf
, it returns 0
. Otherwise, it returns the value of the node plus the sum of the values of the left and right subtrees.
You can see the benefits of using pattern matching here. The code is very concise and much easier to understand because it reads like what you would say in plain English.
Navigating Complex Data Structures
Pattern matching allows us to navigate complex data structures in a very flexbile and concise way without a lot of mental overhead. Consider the following variant type to represent a polynomial:
(* polynomial.ml *)
type 'a polynomial =
| Zero
| Const of 'a
| Var
| Sum of 'a polynomial * 'a polynomial
| Prod of 'a polynomial * 'a polynomial
| Power of 'a polynomial * int
The polynomial
type is a generic type that takes in a type parameter 'a
. It is a placeholder for a type that will be specified later when the type is used. polynomial
and has six variants. The Zero
variant represents the polynomial 0
, the Const
variant represents a constant polynomia, the Var
variant represents the polynomial x
. The Sum
variant represents the sum of two polynomials. The Prod
variant represents the product of two polynomials. The Power
variant represents the polynomial raised to a power.
We can now use pattern matching to define a function that evaluates a polynomial at a given value of x
:
(* polynomial.ml *)
(* `function` is just syntatic sugar for `match x with` *)
let rec eval x = function
| Zero -> 0
| Const c -> c
| Var -> x
| Sum (p1, p2) -> eval x p1 + eval x p2
| Prod (p1, p2) -> eval x p1 * eval x p2
| Power (p, n) -> int_of_float (float_of_int (eval x p) ** float_of_int n)
Here, eval
is a recursive function which uses pattern matching to define the cases for the different variants of the polynomial
type.
- If the polynomial is
Zero
, the function returns0
. - If the polynomial is
Const
, the function returns the constant value. - If the polynomial is
Var
, the function returns the value ofx
. - If the polynomial is an
Sum
, the function deconstructs the polynomial into its two operands and evaluates them using theeval
function. It then returns the sum of the two results. - If the polynomial is a
Prod
, the function again deconstructs the polynomial, evaluates them and returns the product of the two results. - If the polynomial is a
Power
, the function deconstructs the polynomial into its base and exponent, evaluates the base and returns the base raised to the power of the exponent.
This allows us to easily calculate the value of a polynomial of any complexity at a given value of x by destructuring it into its constituent parts and recursively evaluating each part. For example, here's how we can use the eval
function to evaluate the polynomial x^2 + 2x + 1
at x = 2
:
(* x^2 + 2x + 1 *)
let p = Sum(Power(Var, 2), Sum(Prod(Const 2, Var), Const 1))
let result = eval 2 p
(* let () = print_int result *)
(* 9 *)
Another benefit to use pattern matching in complex structures like this is that the compiler will make sure your pattern matching is exhaustive so you won't ever miss a case.
Handling Errors
Pattern matching can also be a useful technique for error handling. Consider the following to divide two integers:
let div x y =
if y = 0 then Error "Division by zero"
else Ok (x / y)
The div
function takes two integers as arguments and returns an int
value wrapped in an result type. If the second argument is 0
, the function returns an Error
. Otherwise, it returns Ok (x / y)
. Now we can use pattern matching to handle the result of the div
function:
let () =
let result = div 10 0 in
match result with
| Ok x -> print_endline (string_of_int x)
| Error msg -> print_endline msg
This is a pretty simple example. In OCaml there are also option types which have two variants: Some
and None
. The Some
variant is used to wrap a value and the None
variant is used to represent the absence of a values.
Conclusion
In conclusion, pattern matching is a versatile and useful technique that can simplify and improve many aspects of your code. Whether its a simple script or a complex application, pattern matching can help you write code that is more correct, concise, expressive, and maintainable.
Thanks for reading!
Credits
Thank you to the following people for proofreading and giving ideas for this article:
Top comments (2)
Amazing read @nexxeln
Thank you!