What is 'Pattern Matching' in functional languages?

Question

I'm reading about functional programming and I've noticed that Pattern Matching is mentioned in many articles as one of the core features of functional languages.

Can someone explain for a Java/C++/JavaScript developer what does it mean?

Altarpiece

possible duplicate of Haskell pattern matching - what is it? – Dygall

Answer 1

Understanding pattern matching requires explaining three parts:

1. Algebraic data types.
2. What pattern matching is
3. Why its awesome.

Algebraic data types in a nutshell

ML-like functional languages allow you define simple data types called "disjoint unions" or "algebraic data types". These data structures are simple containers, and can be recursively defined. For example:

type 'a list =
    | Nil
    | Cons of 'a * 'a list

defines a stack-like data structure. Think of it as equivalent to this C#:

public abstract class List<T>
{
    public class Nil : List<T> { }
    public class Cons : List<T>
    {
        public readonly T Item1;
        public readonly List<T> Item2;
        public Cons(T item1, List<T> item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }
}

So, the Cons and Nil identifiers define simple a simple class, where the of x * y * z * ... defines a constructor and some data types. The parameters to the constructor are unnamed, they're identified by position and data type.

You create instances of your a list class as such:

let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))

Which is the same as:

Stack<int> x = new Cons(1, new Cons(2, new Cons(3, new Cons(4, new Nil()))));

Pattern matching in a nutshell

Pattern matching is a kind of type-testing. So let's say we created a stack object like the one above, we can implement methods to peek and pop the stack as follows:

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

let pop s =
    match s with
    | Cons(hd, tl) -> tl
    | Nil -> failwith "Empty stack"

The methods above are equivalent (although not implemented as such) to the following C#:

public static T Peek<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return hd;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

public static Stack<T> Pop<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return tl;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

(Almost always, ML languages implement pattern matching without run-time type-tests or casts, so the C# code is somewhat deceptive. Let's brush implementation details aside with some hand-waving please :) )

Data structure decomposition in a nutshell

Ok, let's go back to the peek method:

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

The trick is understanding that the hd and tl identifiers are variables (errm... since they're immutable, they're not really "variables", but "values" ;) ). If s has the type Cons, then we're going to pull out its values out of the constructor and bind them to variables named hd and tl.

Pattern matching is useful because it lets us decompose a data structure by its shape instead of its contents. So imagine if we define a binary tree as follows:

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

We can define some tree rotations as follows:

let rotateLeft = function
    | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
    | x -> x

let rotateRight = function
    | Node(Node(a, p, b), q, c) -> Node(a, p, Node(b, q, c))
    | x -> x

(The let rotateRight = function constructor is syntax sugar for let rotateRight s = match s with ....)

So in addition to binding data structure to variables, we can also drill down into it. Let's say we have a node let x = Node(Nil, 1, Nil). If we call rotateLeft x, we test x against the first pattern, which fails to match because the right child has type Nil instead of Node. It'll move to the next pattern, x -> x, which will match any input and return it unmodified.

For comparison, we'd write the methods above in C# as:

public abstract class Tree<T>
{
    public abstract U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc);

    public class Nil : Tree<T>
    {
        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nilFunc();
        }
    }

    public class Node : Tree<T>
    {
        readonly Tree<T> Left;
        readonly T Value;
        readonly Tree<T> Right;

        public Node(Tree<T> left, T value, Tree<T> right)
        {
            this.Left = left;
            this.Value = value;
            this.Right = right;
        }

        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nodeFunc(Left, Value, Right);
        }
    }

    public static Tree<T> RotateLeft(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => r.Match(
                () => t,
                (rl, rx, rr) => new Node(new Node(l, x, rl), rx, rr))));
    }

    public static Tree<T> RotateRight(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => l.Match(
                () => t,
                (ll, lx, lr) => new Node(ll, lx, new Node(lr, x, r))));
    }
}

For seriously.

Pattern matching is awesome

You can implement something similar to pattern matching in C# using the visitor pattern, but its not nearly as flexible because you can't effectively decompose complex data structures. Moreover, if you are using pattern matching, the compiler will tell you if you left out a case. How awesome is that?

Think about how you'd implement similar functionality in C# or languages without pattern matching. Think about how you'd do it without test-tests and casts at runtime. Its certainly not hard, just cumbersome and bulky. And you don't have the compiler checking to make sure you've covered every case.

So pattern matching helps you decompose and navigate data structures in a very convenient, compact syntax, it enables the compiler to check the logic of your code, at least a little bit. It really is a killer feature.

Cantilever

+1 but don't forget about other languages with pattern matching like Mathematica. – Rosariarosario

"errm... since they're immutable, they're not really "variables", but "values" ;)" They are variables; it's the mutable variety that's mislabeled. Nevertheless, excellent answer! – Splenectomy

"Almost always, ML languages implement pattern matching without run-time type-tests or casts" <- How does this work? Can you point me to a primer? – Dromond

@DavidMoles: The type system makes it possible to elide all run-time checks by proving pattern matches to be exhaustive and not redundant. If you try to feed a language like SML, OCaml or F# a pattern match that is not exhaustive or contains redundancy then the compiler will warn you at compile time. This is an extremely powerful feature because it allows you to eliminate run-time checks by rearranging your code, i.e. you can have aspects of your code proven correct. Furthermore, it is easy to understand! – Rosariarosario

@JonHarrop I can see how that would work (effectively it's similar to dynamic message dispatch) but I can't see how at run-time you select a branch without a type test. – Dromond

@DavidMoles: I see what you mean. The difference is terminology: the parts of a union type are called type constructors and they are not regarded as types as they would be in other languages so that isn't technically testing types at runtime. The point here is that there is no implicit run time test for errors during dispatch. Static checking of errors but still dynamic dispatch. – Rosariarosario

I wouldn't say you absolutely need ADTs to talk about pattern matching - you can pattern match on primitive types and e.g. structs in rust, with no ADT in sight afaik – Ignacioignacius

Lets update this a little bit: C# now has pattern matching and C# 8 will expand it further: learn.microsoft.com/en-us/archive/msdn-magazine/2019/may/… – Deserted

Answer 2

Short answer: Pattern matching arises because functional languages treat the equals sign as an assertion of equivalence instead of assignment.

Long answer: Pattern matching is a form of dispatch based on the “shape” of the value that it's given. In a functional language, the datatypes that you define are usually what are known as discriminated unions or algebraic data types. For instance, what's a (linked) list? A linked list List of things of some type a is either the empty list Nil or some element of type a Consed onto a List a (a list of as). In Haskell (the functional language I'm most familiar with), we write this

data List a = Nil
            | Cons a (List a)

All discriminated unions are defined this way: a single type has a fixed number of different ways to create it; the creators, like Nil and Cons here, are called constructors. This means that a value of the type List a could have been created with two different constructors—it could have two different shapes. So suppose we want to write a head function to get the first element of the list. In Haskell, we would write this as

-- `head` is a function from a `List a` to an `a`.
head :: List a -> a
-- An empty list has no first item, so we raise an error.
head Nil        = error "empty list"
-- If we are given a `Cons`, we only want the first part; that's the list's head.
head (Cons h _) = h

Since List a values can be of two different kinds, we need to handle each one separately; this is the pattern matching. In head x, if x matches the pattern Nil, then we run the first case; if it matches the pattern Cons h _, we run the second.

Short answer, explained: I think one of the best ways to think about this behavior is by changing how you think of the equals sign. In the curly-bracket languages, by and large, = denotes assignment: a = b means “make a into b.” In a lot of functional languages, however, = denotes an assertion of equality: let Cons a (Cons b Nil) = frob x asserts that the thing on the left, Cons a (Cons b Nil), is equivalent to the thing on the right, frob x; in addition, all variables used on the left become visible. This is also what's happening with function arguments: we assert that the first argument looks like Nil, and if it doesn't, we keep checking.

Ditty

What an interesting way of thinking about the equals sign. Thanks for sharing that! – Dropsical

What does Cons mean? – Trimester

@Roymunson: Cons is the constructor that builds a (linked) list out of a head (the a) and a tail (the List a). The name comes from Lisp. In Haskell, for the built-in list type, it's the : operator (which is still pronounced "cons"). – Ditty

Answer 3

It means that instead of writing

double f(int x, int y) {
  if (y == 0) {
    if (x == 0)
      return NaN;
    else if (x > 0)
      return Infinity;
    else
      return -Infinity;
  } else
     return (double)x / y;
}

You can write

f(0, 0) = NaN;
f(x, 0) | x > 0 = Infinity;
        | else  = -Infinity;
f(x, y) = (double)x / y;

---

Hey, C++ supports pattern matching too.

static const int PositiveInfinity = -1;
static const int NegativeInfinity = -2;
static const int NaN = -3;

template <int x, int y> struct Divide {
  enum { value = x / y };
};
template <bool x_gt_0> struct aux { enum { value = PositiveInfinity }; };
template <> struct aux<false> { enum { value = NegativeInfinity }; };
template <int x> struct Divide<x, 0> {
  enum { value = aux<(x>0)>::value };
};
template <> struct Divide<0, 0> {
  enum { value = NaN };
};

#include <cstdio>

int main () {
    printf("%d %d %d %d\n", Divide<7,2>::value, Divide<1,0>::value, Divide<0,0>::value, Divide<-1,0>::value);
    return 0;
};

Micheal

In Scala: import Double._ def divide = { values: (Double, Double) => values match { case (0,0) => NaN case (x,0) => if (x > 0) PositiveInfinity else NegativeInfinity case (x,y) => x / y } } – Koehn

Answer 4

Pattern matching is sort of like overloaded methods on steroids. The simplest case would be the same roughly the same as what you seen in java, arguments are a list of types with names. The correct method to call is based on the arguments passed in, and it doubles as an assignment of those arguments to the parameter name.

Patterns just go a step further, and can destructure the arguments passed in even further. It can also potentially use guards to actually match based on the value of the argument. To demonstrate, I'll pretend like JavaScript had pattern matching.

function foo(a,b,c){} //no pattern matching, just a list of arguments

function foo2([a],{prop1:d,prop2:e}, 35){} //invented pattern matching in JavaScript

In foo2, it expects a to be an array, it breaks apart the second argument, expecting an object with two props (prop1,prop2) and assigns the values of those properties to variables d and e, and then expects the third argument to be 35.

Unlike in JavaScript, languages with pattern matching usually allow multiple functions with the same name, but different patterns. In this way it is like method overloading. I'll give an example in erlang:

fibo(0) -> 0 ;
fibo(1) -> 1 ;
fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .

Blur your eyes a little and you can imagine this in javascript. Something like this maybe:

function fibo(0){return 0;}
function fibo(1){return 1;}
function fibo(N) when N > 0 {return fibo(N-1) + fibo(N-2);}

Point being that when you call fibo, the implementation it uses is based on the arguments, but where Java is limited to types as the only means of overloading, pattern matching can do more.

Beyond function overloading as shown here, the same principle can be applied other places, such as case statements or destructuring assingments. JavaScript even has this in 1.7.

Gurley

Answer 5

Pattern matching allows you to match a value (or an object) against some patterns to select a branch of the code. From the C++ point of view, it may sound a bit similar to the switch statement. In functional languages, pattern matching can be used for matching on standard primitive values such as integers. However, it is more useful for composed types.

First, let's demonstrate pattern matching on primitive values (using extended pseudo-C++ switch):

switch(num) {
  case 1: 
    // runs this when num == 1
  case n when n > 10: 
    // runs this when num > 10
  case _: 
    // runs this for all other cases (underscore means 'match all')
}

The second use deals with functional data types such as tuples (which allow you to store multiple objects in a single value) and discriminated unions which allow you to create a type that can contain one of several options. This sounds a bit like enum except that each label can also carry some values. In a pseudo-C++ syntax:

enum Shape { 
  Rectangle of { int left, int top, int width, int height }
  Circle of { int x, int y, int radius }
}

A value of type Shape can now contain either Rectangle with all the coordinates or a Circle with the center and the radius. Pattern matching allows you to write a function for working with the Shape type:

switch(shape) { 
  case Rectangle(l, t, w, h): 
    // declares variables l, t, w, h and assigns properties
    // of the rectangle value to the new variables
  case Circle(x, y, r):
    // this branch is run for circles (properties are assigned to variables)
}

Finally, you can also use nested patterns that combine both of the features. For example, you could use Circle(0, 0, radius) to match for all shapes that have the center in the point [0, 0] and have any radius (the value of the radius will be assigned to the new variable radius).

This may sound a bit unfamiliar from the C++ point of view, but I hope that my pseudo-C++ make the explanation clear. Functional programming is based on quite different concepts, so it makes better sense in a functional language!

Dilorenzo

Answer 6

Pattern matching is where the interpreter for your language will pick a particular function based on the structure and content of the arguments you give it.

It is not only a functional language feature but is available for many different languages.

The first time I came across the idea was when I learned prolog where it is really central to the language.

e.g.

last([LastItem], LastItem).

last([Head|Tail], LastItem) :- last(Tail, LastItem).

The above code will give the last item of a list. The input arg is the first and the result is the second.

If there is only one item in the list the interpreter will pick the first version and the second argument will be set to equal the first i.e. a value will be assigned to the result.

If the list has both a head and a tail the interpreter will pick the second version and recurse until it there is only one item left in the list.

Rafaelle

Also as you can see from the example the interpreter can also break up a single argument into several variables automatically (e.g. [Head|Tail]) – Rafaelle

Answer 7

For many people, picking up a new concept is easier if some easy examples are provided, so here we go:

Let's say you have a list of three integers, and wanted to add the first and the third element. Without pattern matching, you could do it like this (examples in Haskell):

Prelude> let is = [1,2,3]
Prelude> head is + is !! 2
4

Now, although this is a toy example, imagine we would like to bind the first and third integer to variables and sum them:

addFirstAndThird is =
    let first = head is
        third = is !! 3
    in first + third

This extraction of values from a data structure is what pattern matching does. You basically "mirror" the structure of something, giving variables to bind for the places of interest:

addFirstAndThird [first,_,third] = first + third

When you call this function with [1,2,3] as its argument, [1,2,3] will be unified with [first,_,third], binding first to 1, third to 3 and discarding 2 (_ is a placeholder for things you don't care about).

Now, if you only wanted to match lists with 2 as the second element, you can do it like this:

addFirstAndThird [first,2,third] = first + third

This will only work for lists with 2 as their second element and throw an exception otherwise, because no definition for addFirstAndThird is given for non-matching lists.

Until now, we used pattern matching only for destructuring binding. Above that, you can give multiple definitions of the same function, where the first matching definition is used, thus, pattern matching is a little like "a switch statement on stereoids":

addFirstAndThird [first,2,third] = first + third
addFirstAndThird _ = 0

addFirstAndThird will happily add the first and third element of lists with 2 as their second element, and otherwise "fall through" and "return" 0. This "switch-like" functionality can not only be used in function definitions, e.g.:

Prelude> case [1,3,3] of [a,2,c] -> a+c; _ -> 0
0
Prelude> case [1,2,3] of [a,2,c] -> a+c; _ -> 0
4

Further, it is not restricted to lists, but can be used with other types as well, for example matching the Just and Nothing value constructors of the Maybe type in order to "unwrap" the value:

Prelude> case (Just 1) of (Just x) -> succ x; Nothing -> 0
2
Prelude> case Nothing of (Just x) -> succ x; Nothing -> 0
0

Sure, those were mere toy examples, and I did not even try to give a formal or exhaustive explanation, but they should suffice to grasp the basic concept.

Rosalinarosalind

Answer 8

You should start with the Wikipedia page that gives a pretty good explanation. Then, read the relevant chapter of the Haskell wikibook.

This is a nice definition from the above wikibook:

So pattern matching is a way of assigning names to things (or binding those names to those things), and possibly breaking down expressions into subexpressions at the same time (as we did with the list in the definition of map).

Gunzburg

Next time I'll mention in question that I've already read wikipedia and it gives very bad explaination. – Altarpiece

Answer 9

Here is a really short example that shows pattern matching usefulness:

Let's say you want to sort up an element in a list:

["Venice","Paris","New York","Amsterdam"] 

to (I've sorted up "New York")

["Venice","New York","Paris","Amsterdam"] 

in an more imperative language you would write:

function up(city, cities){  
    for(var i = 0; i < cities.length; i++){
        if(cities[i] === city && i > 0){
            var prev = cities[i-1];
            cities[i-1] = city;
            cities[i] = prev;
        }
    }
    return cities;
}

In a functional language you would instead write:

let up list value =  
    match list with
        | [] -> []
        | previous::current::tail when current = value ->  current::previous::tail
        | current::tail -> current::(up tail value)

As you can see the pattern matched solution has less noise, you can clearly see what are the different cases and how easy it's to travel and de-structure our list.

I've written a more detailed blog post about it here.

Extortionate

Answer 10

The other answers are good but require too much background knowledge. I will illustrate the concept of pattern matching with very simple Java code.

See this example:

public class HelloWorld{

  public static void match(Number x, Number... y){
    if (y.length == 0){
      if (x instanceof Integer){
        System.out.println("There is one integer.");
      }
      if (x instanceof Double){
        System.out.println("There is one double.");
      }
    }
    if (y.length == 1){
      if ((x instanceof Integer) && (y[0] instanceof Integer)){
        System.out.println("There are two integers.");
      }
      if ((x instanceof Double) && (y[0] instanceof Double)){
        System.out.println("There are two doubles.");
      }
    }
  }

  public static void main (String[] args){
    match(1);
    match(2,3);
    match(2.0);
    match(2.0,3.0);
  }
}

It should be easy to understand how this program works. But we cannot be happy with it, because the if clauses are some kind of duplicated and not all cases are covered. See an alternative example, that does nearly the same thing:

public class HelloWorld{

  public static void match(int x){
    System.out.println("There is one integer.");
  }
  public static void match(int x, int y){
    System.out.println("There are two integers.");
  }
  public static void match(double y){
    System.out.println("There is one double.");
  }
  public static void match(double x, double y){
    System.out.println("There are two doubles.");
  }

  public static void main (String[] args){
    match(1);
    match(2,3);
    match(2.0);
    match(2.0,3.0);
  }
}

This example is clearly much easier to write and read. Instead of hand-written if-clauses, this example uses a feature of the programming language (function overloading). This makes many things simpler.

Pattern matching is a generalization of this concept. You can imagine it as function overloading, but more.

To see what the "more" is, we must understand how function overloading works. Function overloading works with types and it works only statically. That means it must be already known at compile time what function will be used. With this restriction the benefit of function overloading is limited. You can always achieve the same result when implementing a small dispatching function.

public class HelloWorld{
  public static void match_one_int(int x){
    System.out.println("There is one integer.");
  }
  public static void match_two_ints(int x, int y){
    System.out.println("There are two integers.");
  }
  public static void match_one_double(double y){
    System.out.println("There is one double.");
  }
  public static void match_two_doubles(double x, double y){
    System.out.println("There are two doubles.");
  }
  
  public static void match(Number x, Number... y){
    if (y.length == 0){
      if (x instanceof Integer){
        match_one_int((int)x);
      }
      if (x instanceof Double){
        match_one_double((double)x);
      }
    }
    if (y.length == 1){
      if ((x instanceof Integer) && (y[0] instanceof Integer)){
        match_two_ints((int)x, (int)y[0]);
      }
      if ((x instanceof Double) && (y[0] instanceof Double)){
        match_two_doubles((double)x, (double)y[0]);
      }
    }
  }

  public static void main (String[] args){
    match(1);
    match(2,3);
    match(2.0);
    match(2.0,3.0);
  }
}

This shows that function overloading is not really an enabling feature of a programming language. Many programming languages do not provide a mechanism for function overloading. See how the lack of this language features requires from you to write so much extra code. In this case it is very simple. In languages with a macro mechanism (e.g. C++, Lisp) this can even be done at compile time. This explains why the C++ macro mechanism for many people is so attractive. It enables you to write the dispatcher in the example purely as a macro.

Back to Pattern Matching. As seen in the example, in practice it is very helpful if a programming languages provides a dispatching mechanism that uses more than just the function name and that also works at runtime.

Let's try to calculate the faculty of a number n. It shall be n * n-1 * n-2* ... 1. In Java it looks like this:

  public static int faculty(int n){
    int result = 1;
    for (int i = 1;i<n;i++){
      result *= i;
    }
    return result;
  }

Alternatively you can write it in a functional style:

  public static int faculty(int n){
    if (n==1)
      return 1;
    return n * faculty(n-1);
  }

The functional approach is often easier, because when reading this you don't have to bother what result and i are. You don't add so much technical extra stuff to the code, that have nothing to do with your problem.

And now let's go beyond this and try to use pattern matching:

  public static int faculty(int 1){
    return 1;
  }
  public static int faculty(int n > 1){  // This is illegal in Java
    return n * faculty(n-1);
  }

This is Pattern Matching. It is named so because the dispatcher looks at the pattern of the arguments. "Unfortunately in Java this does not work. But there are programming languages where this is possible. This is what the other answers illustrate.

Androgyne