Shoubhit Dash

Posted on Dec 29, 2022 • Edited on Jan 5, 2023

Expressive Code with Pattern Matching

#programming #functional #ocaml

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

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

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!