Expressive Code with Pattern Matching
Tags: programming, functional, ocaml
Published: 2022-12-29 18:31:34

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.

<br />

## What is Pattern Matching?

<br />

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.

<br />

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:

```ocaml
(* 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 argument`name`. The `match` keyword is used to define a pattern match, and the `with` keyword is used to specify the different patterns to be matched.

<br />

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?".

<br />

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.

<br />

## Why Use Pattern Matching?

<br />

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](https://en.wikipedia.org/wiki/Factorial) of a number.

```ocaml
(* 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.

<br />

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:

```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.

<br />

## Pattern Matching in Practice

<br />

### Conditionals

<br />

We already saw the factorial example, but let's take another example to calculate the nth term of the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number).

```ocaml
(* 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 to `0`, it returns `0`.
- If `n` is equal to `1`, it returns `1`.
- If `n` is neither `0` nor `1`, the function calls itself with `n - 1` and `n - 2` as arguments and returns the sum of the two results.

<br />

Here's an imperative implementation of the same function in TypeScript:

```ts
// 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.

```ts
// 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.

<br />

### Usage with Algebraic Data Types

<br />

Pattern matching is also used with [algebraic data types](https://en.wikipedia.org/wiki/Algebraic_data_type), 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](https://en.wikipedia.org/wiki/Binary_tree):

```ocaml
(* 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.

<br />

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:

```ocaml
(* 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.

<br />

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.

<br />

### Navigating Complex Data Structures

<br />

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](https://en.wikipedia.org/wiki/Tagged_union) to represent a [polynomial](https://en.wikipedia.org/wiki/Polynomial):

```ocaml
(* 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.

<br />

We can now use pattern matching to define a function that evaluates a polynomial at a given value of `x`:

```ocaml
(* 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.

<br />

- If the polynomial is `Zero`, the function returns `0`.
- If the polynomial is `Const`, the function returns the constant value.
- If the polynomial is `Var`, the function returns the value of `x`.
- If the polynomial is an `Sum`, the function deconstructs the polynomial into its two operands and evaluates them using the `eval` 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.

<br />

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`:

```ocaml
(* 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.

![Compiler making sure pattern matching is exhaustive](<https://us-east-1.tixte.net/uploads/this-vegetable.is-from.space/Alacritty-v0.10.0-portable_(1)_KQtv19ft64.gif>)

### Handling Errors

<br />

Pattern matching can also be a useful technique for error handling. Consider the following to divide two integers:

```ocaml
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:

```ocaml
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.

<br />

## Conclusion

<br />

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.

<br />

Thanks for reading!

<br />

## Credits

<br />

Thank you to the following people for proofreading and giving ideas for this article:

<br />

- [Zain Wania](https://twitter.com/Zain_Wania)
- [Brendan Allan](https://www.brendonovich.dev/)
- [Yash](https://github.com/yxshv)
- [Néstor](https://github.com/nsttt)

<br />

## Resources

<br />

- [Pattern Matching - Wikipedia](https://en.wikipedia.org/wiki/Pattern_matching)
- [Algebraic Data Types - Wikipedia](https://en.wikipedia.org/wiki/Algebraic_data_type)