Recursive Skeletons and Pattern Matching

Summary

We develop techniques for implementing recursive functions starting with a simple skeleton for recursion over lists. We also introduce pattern matching as an elegant way of capturing case analysis on the shape of data.

So far we have studied a low-level, operational perspective on recursion. This perspective, powered by our mental model of computation, allows us to understand how recursion definitions operate. However, knowing how recursion work and being able to trace code execution is decidedly different from designing recursive functions which requires us to (a) solve a problem in a recursive manner and (b) translate that solution into a recursive function. We’ll tackle both these problems in this reading by developing a simple template or skeleton for recursive functions over lists.

The Components of a Recursive Function

Recall the code for recursively computing the sum of a list from the previous reading:

;;; (sum numbers) -> integer?
;;; numbers : listof integer?
;;;
;;; Returns the sum of the numbers.
(define sum
  (lambda (numbers)
    (if (null? numbers)
        0
        (+ (car numbers) (sum (cdr numbers))))))

In the reading, we gave a recursive definition of a list. A list is either:

• Empty (or null), or
• Non-empty, consisting of a head element (retrieved with car) and its tail, the rest of the list (retrieved with cdr).

Note that every list is covered by this definition because every list is either empty or non-empty. Furthermore, note that this definition is recursive because in the non-empty case, we have a (smaller) occurrence of a list, the thing that we are defining! Because of this, we call the empty case the base case since it contains no occurrences of lists. The non-empty case is called the recursive case precisely because it contains a recursive occurrence of a list.

Because we have defined our data, a list, to be drawn from a finite set of cases, operations over that data can be defined in terms of case analysis over these possibilities. In other words, the definition of sum mirrors the recursive definition of a list.

• In the case where the list is empty, there are no numbers to add, so the sum is 0.
• In the case where the list is non-empty, the sum of the numbers can be expressed as the result of adding (a) the head element and (b) the sum of the rest of the list.

The implementation of sum expresses this decomposition precisely:

• In the base case (numbers is null), we return 0.
• In the recursive case, the result is the head of the list ((car numbers)) plus the sum of the rest of the list ((sum (cdr numbers))).

How do we know that (sum (cdr numbers)) produces the sum of the rest of the list? We saw with our mental model of computation that the call indeed works, but checking it over and over again with our mental model is burdensome. Instead, from a design perspective, we’re going to assume that a recursive function call to the tail of the list produces the intended result. This is called our recursive assumption and is the cornerstone of our decomposition using recursive.

An Recursive Skeleton for Lists

In summary, when we perform recursive decomposition for a problem involving lists, we decompose the problem into two cases based on the recursive definition of lists:

• We solve the problem in the case where the list is empty, the base case.
• We solve the problem in the case where the list is non-empty, the recursive case.

In the non-empty case, we know that, by virtue of the non-emptiness of list, we can use car and cdr to retrieve the head and tail of the list, respectively. Furthermore, our recursive assumption tells us that we can call the recursive function on the tail of the list and get back a correct value.

Translating this pattern into Racket code is straightforward and gives us a basic recursive skeleton for lists to work with:

(define my-recursive-function
  (lambda (l)
    (if (null? l)
        ; The base case
        ; The recursive case
        )))

Because we frequently use the head and tail of the list extensively in the recursive case, we can also use let-bindings to avoid excessive nesting of function applications:

(define my-recursive-function
  (lambda (l)
    (if (null? l)
      ; The base case
      (let ([head (car l)]
            [tail (cdr l)])
           ; The recursive case
           ))))

Let’s apply this template to build a basic recursive function: recursively computing the length of the list. However, let’s not jump into code just yet. Let’s first write out the recursive decomposition and come up with an algorithm for recursively computing the length of a list. And then we’ll translate that algorithm into code.

Our recursive template tells us that we should proceed by case analysis on the list. So we have two sub-problems to solve:

• The base case: compute the length of a list that is empty.
• The recursive case: compute the length of a list that is non-empty.

The base case is straightforward: the length of a list is zero. In general, we will find the base case to be straightforward to solve.

In the recursive case, we know the list is non-empty. Therefore, there is a head element and a corresponding tail of the list. Furthermore, our recursive assumption tells us that we can compute the length of the tail of the list.

How do we proceed from here? A picture is very helpful for understanding our options. In the recursive case, we know the list has the following shape:

The list has been decomposed into a head element and a tail that represents the unknown part of the list. What is the length of this list? From the physical layout of the list, we can further decompose the problem into two parts:

• The contribution of head to the list’s length: each element contributes 1 to the overall length, so this value is 1.
• The contribution of tail to the list’s length: this is precisely what we assumed we could compute with our recursive assumption!

And our intuition about length tells us that the length of the overall list is the sum of these two expressions. Graphically, this would look as follows:

With our algorithm complete, we can now translate it into Racket code. We’ll use the let version of the skeleton to illustrate its usage:

;;; (length lst) -> exact-nonnegative-integer?
;;; lst : list?
;;;
;;; Returns the length of lst.
(define length
  (lambda (lst)
    (if (null? lst)
        0
        (let ([head (car lst)]
              [tail (cdr lst)])
             (+ 1 (length tail))))))

Pattern Matching

Recall that one of our design goals is to write programs that are correct from inspection. In particular, when we have a recursive design, we want our code to look like that design. Let’s see how our definition of length fares in this respect Below, we have replicated the definition of length with the recursive design in-lined in comments:

(define length
  (lambda (lst)
    (if (null? lst)                   ; A list is either empty or non-empty.
        0                             ; + The empty list has zero length.
        (let ([head (car lst)]        ; + A non-empty list has a head and tail
              [tail (cdr lst)])       ; element.
             (+ 1 (length tail))))))  ;   The length of a non-empty list is one
                                      ;   plus the length of the tail.

Not too bad! Like our design, the code is clearly conditioned on whether lst is empty or non-empty. Furthermore, the results of the cases clearly implement the cases of our design, so we can believe our implementation is correct as long as we believe our design is correct.

Is there anything we can improve here? Yes—some subtle, yet important things, in fact:

• We need to make sure that the guard of our conditional accurately reflects the cases of our data structure. Here, our list is either empty or non-empty which is captured by a null? check.
• We know that in the recursive case that our non-empty list is made up of a head and tail which we need to manually access using car and cdr, respectively. Let-bindings name these individual pieces so that we don’t interchange car and cdr in our code, but the let-binding adds a significant layer of complexity.

To fix these issues, we’ll use the pattern matching facilities of Racket to express our recursive design directly without the need for a guard expression or let-binding. Note that when we talk about pattern matching here, we don’t mean regular expressions but instead a separate library of Racket for writing code that looks at the shape of a data type.

First, we’ll revise our list definition slightly based on the functions we use to construct lists.

A list is either:

• '(), the empty list (null is a more readable alternative to '()).
• (cons v l), a non-empty list constructed with cons that consists of a head element v and a list l.

Remember that a list is ultimately composed of repeated cons calls ending in '(). For example:

> (list 1 2 3 4 5)
'(1 2 3 4 5)
> (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '())))))
'(1 2 3 4 5)

Because of this, we know that our constructive definition of a list covers all possible lists. Now, we’ll use pattern matching to directly express length in terms of this constructive definition:

(require racket/match)

(define length
  (lambda (l)
    (match l
      ['() 0]
      [(cons head tail) (+ 1 (length tail))])))

This version of length behaves identically to the previous version of the code but is more concise, directly reflecting our constructive definition of a list. By doing so, we no longer need a let-expression to bind names to the components of the non-empty list—the match construct of Racket does this for us automatically!

Pattern Matching In Detail

Pattern matching is available by including the racket/match package via (require racket/match). This package exposes a special form match that is syntactically similarly to a cond expression:

(match <expr>
  [<pat1> <expr1>]
  [<pat2> <expr2>]
  ...)

Following the match is an expression that evaluates to the value that is the scrutinee of the pattern match, i.e., it is the value that we are analyzing. Following the scrutinee are a collection of branches. With cond, these branches had the form:

[<guard> <expr>]

Where <guard> is a boolean expression and <expr> is the expression that the overall cond evaluates to if <guard> evaluates to true. Each of the guards of the branches are evaluated in top-down order until one returns true.

match behaves similarly except we attempt to match each branch in top-down order. However, the branches of the match does not have guards; they have patterns instead! A pattern describes a potential shape of the scrutinee. If the scrutinee has that shape, then that branch is selected.

In the case of the empty list, this amounts to a simplified equality check. The pattern '() means “is l equal to '()”? So whenever l is the empty list, i.e., '(), the match evaluates to 0.

The non-empty list case is more interesting. Recall that a non-empty list is formed by the cons function. The pattern (cons head tail) checks to see if l is such a list. However, on top of this check, if successful, the match also binds the two arguments of the cons to the variables head and tail respectively. For example, we know that if l is '(1 2 3 4 5), we can think of this as the following sequence of cons calls: (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '()))))). Then the pattern (cons head tail) will bind head to 1 and tail to (cons 2 (cons 3 (cons 4 (cons 5 '())))).

We can visualize how a pattern will bind values by overlaying the pattern on top of the value:

(cons head tail)
(cons  1   (cons 2 (cons 3 (cons 4 (cons 5 '())))))

head = 1
tail = (cons 2 (cons 3 (cons 4 (cons 5 '()))))

Here, we see that head lines up with 1 and ` tail lines up with (cons 2 …). In contrast, if l was (cons 8 ‘())`, then we would have:

(cons head tail)
(cons   8   '())

head = 8
tail = '()

As another example, here is the sum function rewritten to use pattern matching:

(define sum
  (lambda (numbers)
    (match numbers
      ['() 0]
      [(cons head tail) (+ head (sum tail))])))

Again, note how the code is more concise and better reflects our recursive definition for list summation.

Nesting Patterns

We gain immediate benefits of readability and conciseness with pattern matching. But pattern matching is more powerful than what we’ve used so far: we can specify arbitrary patterns of values by nesting our patterns. For example, suppose we want to write a pattern to bind the first two values of a list rather than just the top one. With lists, we would need to chain car and cdr calls which is tedious and error-prone. Instead, we can write the pattern (cons x (cons y lst)) which matches a list with at least two elements and binds the first two elements to x and y, respectively, and lst to the remainder of the list.

(cons x (cons y lst))
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '())))))

x = 1
y = 2
lst = (cons 3 (cons 4 (cons 5 '())))

We won’t immediately use nested patterns in our recursive functions, but there will be a few cases where we will want to employ nested patterns for more complicated recursive designs.

A Note on Bindings with Pattern Matching

In the non-empty case of sum, the branch:

[(cons head tail) (+ head (sum tail))]

Binds head to the head of the list and tail to the tail of the list. This pattern binds the same variable as the following let-expression fragment:

(let ([head (car l)]
      [tail (cdr l)])
  (+ head (sum tail)))

As such, note that the names head and tail are arbitrary in our pattern and can be anything! Frequently, you’ll see me take the convention of naming the variables of the cons pattern as:

[(cons x xs) (+ x (sum xs))]

x is the head of the list, a single value. xs is the tail of the list or, how I think of it: the rest of the xs. However, you can choose whatever names make sense to you. Another valid choice is to shadow the original parameter name:

[(cons x l) (+ x (sum l))]

In this branch, l no longer refers to the parameter of sum but it instead refers to the more-local binding of l as the tail of the list. Recall that we say that this local binding of l shadows or hides the parameter l of the function.

Finally, note that sometimes we don’t use all of the bindings introduced by a pattern. For example, in length, we don’t care about the head element of the list (we always add 1 to the result irrespective of what the head is):

[(cons x xs) (+ 1 (length xs))]

It is useful to avoid binding unnecessary identifier in our code as it isn’t clear whether we should have incorporated x or if we intentionally didn’t use it in our computation. To capture the fact that x is unused, we can instead use an underscore _ which matches anything but doesn’t bind that value to a variable.

[(cons _ xs) (+ 1 (length xs))]

Self Checks

Check 1: Try On A Skeleton (‡)

Apply this recursive template for lists to begin writing a recursive implementation for (list-contains v l) that takes a value v and a list l and returns #t if and only if v is an element of l. In a comment, explicitly write out your recursive decomposition of this function similarly to how we derived length above. Remember to solve the problem for both the base case and recursive case!

Finally, take your recursive implementation and then implement it using pattern matching.