Working with pattern matching

In this section, we will examine pattern matching in Clojure. Typically, functions that use conditional logic can be defined using the if, when, or cond forms. Pattern matching allows us to define such functions by declaring patterns of the literal values of their parameters. While this idea may appear quite rudimentary, it is a very useful and powerful one, as we shall see in the upcoming examples. Pattern matching is also a foundational programming construct in other functional programming languages.

In Clojure, there is no pattern matching support for functions and forms in the core language. However, it is a common notion among Lisp programmers that we can easily modify or extend the language using macros. Clojure takes this approach as well, and thus pattern matching is made possible using the match and defun macros. These macros are implemented in the core.match (https://github.com/clojure/core.match) and defun (https://github.com/killme2008/defun) community libraries. Both of these libraries are also supported on ClojureScript.

Note

The following library dependencies are required for the upcoming examples:

[org.clojure/core.match "0.2.2"
 :exclusions [org.clojure/tools.analyzer.jvm]]
[defun "0.2.0-RC"]

Also, the following namespaces must be included in your namespace declaration:

(ns my-namespace
  (:require [clojure.core.match :as m]
            [defun :as f]))

The following examples can be found in src/m_clj/c1/match.clj of the book's source code.

Let's consider a simple example that we can model using pattern matching. The XOR logic function returns a true value only when its arguments are exclusive of each other, that is, when they have differing values. In other words, the XOR function will return false when both of its arguments have the same values. We can easily define such a function using the match macro, as shown in Example 1.11:

(defn xor [x y]
  (m/match [x y]
           [true true] false
           [false true] true
           [true false] true
           [false false] false))

Example 1.11: Pattern matching using the match macro

The xor function from Example 1.11 simply matches its arguments, x and y, against a given set of patterns, such as [true true] and [true false]. If both the arguments are true or false, then the function returns false, or else it returns true. It's a concise definition that relies on the values of the supplied arguments, rather than the use of conditional forms such as if and when. The xor function can be defined alternatively, and even more concisely, by the defun macro, as shown in Example 1.12:

(f/defun xor
  ([true true] false)
  ([false true] true)
  ([true false] true)
  ([false false] false))

Example 1.12: Pattern match using the defun macro

The definition of the xor function that uses the defun macro simply declares the actual values as its arguments. The expression to be returned is thus determined by the values of its inputs. Note that the defun macro rewrites the definition of the xor function to use the match macro. Hence, all patterns supported by the match macro can also be used with the defun macro. Both the definitions of the xor function, from Example 1.11 and Example 1.12, work as expected, as shown here:

user> (xor true true)
false
user> (xor true false)
true
user> (xor false true)
true
user> (xor false false)
false

The xor function will throw an exception if we try to pass values that have not been declared as a pattern:

user> (xor 0 0)
IllegalArgumentException No matching clause: [0 0] user/xor ...

We can define a simple function to compute the n^th number of the Fibonacci sequence using the defun macro, as shown in Example 1.13:

(f/defun fibo
  ([0] 0N)
  ([1] 1N)
  ([n] (+ (fibo (- n 1))
          (fibo (- n 2)))))

Note the use of the variable n in the function's pattern rules. This signifies that any value other than 0 and 1 will match with the pattern definition that uses n. The fibo function defined in Example 1.13 does indeed calculate the n^th Fibonacci sequence, as shown here:

user> (fibo 0)
0N
user> (fibo 1)
1N
user> (fibo 10)
55N

However, the definition of fibo, shown in Example 1.13, cannot be optimized by tail call elimination. This is due to the fact that the definition of fibo is tree recursive. By this, we mean to say that the expression (+ (fibo ...) (fibo ...)) requires two recursive calls in order to be evaluated completely. In fact, if we replace the recursive calls to the fibo function with recur expressions, the resulting function won't compile. It is fairly simple to convert tree recursion into linear recursion, as shown in Example 1.14:

(f/defun fibo-recur
  ([a b 0] a)
  ([a b n] (recur b (+ a b) (dec n)))
  ([n] (recur 0N 1N n)))

Example 1.14: A tail recursive function with pattern matching

It is fairly obvious from the definition of the fibo-recur function, from Example 1.14, that it is indeed tail recursive. This function does not consume any stack space, and can be safely called with large values of n, as shown here:

user> (fibo-recur 0)
0N
user> (fibo-recur 1)
1N
user> (fibo-recur 10)
55N
user> (fibo-recur 9999)
207936...230626N

As the preceding examples show us, pattern matching is a powerful tool in functional programming. Functions that are defined using pattern matching are not only correct and expressive, but can also achieve good performance. In this respect, the core.match and defun libraries are indispensible tools in the Clojure ecosystem.