Pattern Matching in Elm

One of the great things about some functional programming languages is pattern matching. At its core, it is a way to deconstruct the elements of your program and to do something meaningful with said deconstruction. In this blog post, I'm going to demonstrate how to create a singly linked list and a few functions that operate on it using the language, Elm.

If you're new to Elm, I highly recommend going over the Getting Started Guide. However, I hope to be able to explain the concepts presented in a simple enough fashion so you can follow along if you have no experience in Elm or ML style languages.

First, let's go ahead and define our list as a type in Elm:

type MyList a
  = EmptyList
  | ListOf a (MyList a)

Here we've defined our own list type called MyList which can be a singly linked list of any type a. For example, we can have a MyList String, MyList number, MyList List etc - it doesn't matter as long as all elements in the list are of the same type.

As we continue, it's important to note here that we could have called this type and its possible patterns anything, all we are doing is defining the structure or pattern of our MyList data.

Next, we say that our MyList can either be one of two things, an EmptyList or a ListOf. Again, these aren't keywords, we could have called these two variants of MyList anything. For example, it may be more familiar to see this as:

type MyList a
  = Nil
  | Cons a (MyList a)

where we represent an empty node in a Singly Linked List as Nil and a non empty node as the cons of some value and another list. Even more familiar to some would be if I were to describe these two representations in JavaScript:

const EmptyList = () => null
const ListOf = a => ({ value: a, next: EmptyList() });

Continuing on, lets break down EmptyList and ListOf. EmptyList is just that; it's a value that represents an EmptyList. ListOf is a value that represents a list that has a head of some value a, and a tail that is some MyList (keep in mind, EmptyList is a valid MyList, so a MyList with a single element of value 1 will be ListOf 1 EmptyList).

Great, so we've defined the structure of our MyList data structure, but what can we do with this? This is where pattern matching comes in. Let's use pattern matching to define a few key functions on our MyList type: append, map, reduce, filter.

Let's start with append. Append should take two MyLists of type a and join and return a new MyList of type a:

append : MyList a -> MyList a -> MyList a
append list1 list2 =
  let
    lists = (list1, list2)
  in
    case lists of
      (list1, EmptyList) ->
        list1
      (EmptyList, list2) ->
        list2
      (ListOf h t, list2) ->
        ListOf h (append t list2)

Ok lets break this down line by line. First, we are supplying the type signature for our append function. Here all we are saying is append takes two MyLists of type a and returns a MyList of type a. I won't go over currying here, but there are plenty of articles out there to get you up to speed. All you need to know for this is that the value of the right most arrow is the return, and everything to the left of that are the parameters.

Next, we define the actual append function. list1 and list2 are the supplied lists, which we combine into a tuple and define as lists to do our pattern match against. Next, we set up our pattern match. Our first case says: "In the case that list2 is an EmptyList, return list1". This makes sense as we wouldn't append an EmptyList to our list. Likewise, we do the same in the case of list1 being the empty list. Where this gets interesting is for the case where we do append. We destructure our tuple, as well as the values of the tuple. In this case, we've destructured list1 into ListOf h representing head (a value of type a) and t representing tail (a MyList of type a). With this destructure, we are able to return a new ListOf h and the result of appending list2 to t. This means that append is a recursive function, as it makes a call to itself to iterate over list1 until it reaches the end of its tail, at which point it appends list2. Let's break the evaluation down to get a better understanding of what's happening:

x = ListOf 1 (ListOf 2 EmptyList)
y = ListOf 3 EmptyList

append x y
{-
evaluates as follows:
append x y =
  (ListOf 1 t, y) ->
    ListOf 1 (append t y)
             (ListOf 2 t, y) ->
               (ListOf 2 (append t y)
                         (EmptyList, y) -> y
             (ListOf 2 y)
    ListOf 1 (ListOf 2 y)
returns:
  ListOf 1 (ListOf 2 (ListOf 3 EmptyList))
-}

Neat! So as you can see from this, appends to Singly Linked Lists are more time efficient than concats on arrays, as arrays take n computations where n is the length of array1 + array2, whereas append takes n computations where n is the length of List1.

Let's continue on with map. Map takes a function that takes a value of type a and returns a value of type b, a MyList of type a and returns a MyList of type b:

map: (a -> b) -> MyList a -> MyList b
map f list =
    case list of
      EmptyList ->
        EmptyList
      ListOf h t ->
        ListOf (f h) (map f t)

Hopefully the evaluation here is a little more straight forward after going through append. Here, we destructure a ListOf into its head and tail, and return a new ListOf with a head of the result of applying the functions supplied to map, and a recursive build up of doing the same.

Finally, reduce. Reduce takes a function that takes an accumulator of type b, a value of type a and returns a type b, an initial value of type b, a MyList of type a and returns a type b:

reduce : (b -> a -> b) -> b -> MyList a -> b
reduce f acc list =
  case list of
    EmptyList ->
      acc
    ListOf h t ->
      reduce f (f acc h) t

Again, we are able to utilize pattern matching and recursion to succinctly describe the shape of our data and behavior of our programs.