Chapter 21 Pattern Matching

This library provides functions for pattern-matching Scheme values. (This chapter adapted from Andrew K. Wright and Bruce Duba's original manual, entitled Pattern Matching for Scheme. The PLT Scheme port was contributed by Bruce Hauman.) The following forms are provided:

(match expr clause ...)
(match-lambda clause ...)
(match-lambda* clause ...)
(match-let ((pat expr) ...) expr ···1)
(match-let* ((pat expr) ...) expr ···1)
(match-letrec ((pat expr) ...) expr ···1)
(match-let var ((pat expr) ...) expr ···1)
(match-define pat expr)

clause is one of
 (pat expr ···1)
 (pat (=> identifier) expr ···1)

Figures 1 and 2 give the full syntax for pat patterns.


Figure 1:  Pattern Syntax

Figure 2:  Quasipattern Syntax

The next subsection describes the various patterns.

The match-lambda and match-lambda* forms are convenient combinations of match and lambda, and can be explained as follows:

(match-lambda (pat expr ···1) ...) =(lambda (x) (match x (pat expr ···1) ...))
(match-lambda* (pat expr ···1) ...) =(lambda x (match x (pat expr ···1) ...))
where x is a unique variable. The match-lambda form is convenient when defining a single argument function that immediately destructures its argument. The match-lambda* form constructs a function that accepts any number of arguments; the patterns of match-lambda* should be lists.

The match-let, match-let*, match-letrec, and schemematch-define forms generalize Scheme's let, let*, letrec, and define expressions to allow patterns in the binding position rather than just variables. For example, the following expression:

(match-let ([(x y z) (list 1 2 3)]) body)

binds x to 1, y to 2, and z to 3 in the body. These forms are convenient for destructuring the result of a function that returns multiple values. As usual for letrec and define, pattern variables bound by match-letrec and match-define should not be used in computing the bound value.

The match, match-lambda, and match-lambda* forms allow the optional syntax (=> identifier) between the pattern and the body of a clause. When the pattern match for such a clause succeeds, the identifier is bound to a failure procedure of zero arguments within the body. If this procedure is invoked, it jumps back to the pattern matching expression, and resumes the matching process as if the pattern had failed to match. The body must not mutate the object being matched, otherwise unpredictable behavior may result.

21.1  Patterns

Figure 1 gives the full syntax for patterns. Explanations of these patterns follow.

If no clause matches the value, the reult is void.

21.2  Examples

This section illustrates the convenience of pattern matching with some examples. The following function recognizes some s-expressions that represent the standard Y operator:

(define Y?
    [('lambda (f1)
       ('lambda (y1)
         ((('lambda (x1) (f2 ('lambda (z1) ((x2 x3) z2))))
           ('lambda (a1) (f3 ('lambda (b1) ((a2 a3) b2)))))
     (and (symbol? f1) (symbol? y1) (symbol? x1) (symbol? z1) (symbol? a1) (symbol? b1)
          (eq? f1 f2) (eq? f1 f3) (eq? y1 y2)
          (eq? x1 x2) (eq? x1 x3) (eq? z1 z2)
          (eq? a1 a2) (eq? a1 a3) (eq? b1 b2))]
    [_ #f]))

Writing an equivalent piece of code in raw Scheme is tedious.

The following code defines abstract syntax for a subset of Scheme, a parser into this abstract syntax, and an unparser.

(define-struct Lam (args body))
(define-struct Var (s))
(define-struct Const (n))
(define-struct App (fun args))

(define parse
    [(and s (? symbol?) (not 'lambda))
     (make-Var s)]
    [(? number? n)
     (make-Const n)]
    [('lambda (and args ((? symbol?) ...) (not (? repeats?))) body)
     (make-Lam args (parse body))]
    [(f args ...)
       (parse f)
       (map parse args))]
    [x (error 'syntax "invalid expression")]))

(define repeats?
  (lambda (l)
    (and (not (null? l))
         (or (memq (car l) (cdr l)) (repeats? (cdr l))))))

(define unparse
    [($ Var s) s]
    [($ Const n) n]
    [($ Lam args body) `(lambda ,args ,(unparse body))]
    [($ App f args) `(,(unparse f) ,@(map unparse args))]))

With pattern matching, it is easy to ensure that the parser rejects all incorrectly formed inputs with an error message.

With match-define, it is easy to define several procedures that share a hidden variable. The following code defines three procedures, inc, value, and reset, that manipulate a hidden counter variable:

(match-define (inc value reset)
  (let ([val 0])
      (lambda () (set! val (add1 val)))
      (lambda () val)
      (lambda () (set! val 0)))))

Although this example is not recursive, the bodies could recursively refer to each other.