This library provides functions for patternmatching 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 ...) (matchlambda clause ...) (matchlambda* clause ...) (matchlet ((pat expr) ...) expr ···^{1}) (matchlet* ((pat expr) ...) expr ···^{1}) (matchletrec ((pat expr) ...) expr ···^{1}) (matchlet var ((pat expr) ...) expr ···^{1}) (matchdefine 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 matchlambda
and matchlambda*
forms are convenient
combinations of match
and lambda
, and can be explained
as follows:
where x is a unique variable. The
(matchlambda (pat expr ···^{1}) ...)
= (lambda (x) (match x (pat expr ···^{1}) ...))
(matchlambda* (pat expr ···^{1}) ...)
= (lambda x (match x (pat expr ···^{1}) ...))
matchlambda
form is convenient when defining a single argument
function that immediately destructures its argument.
The matchlambda*
form constructs a function that accepts any number
of arguments; the patterns of matchlambda*
should be lists.
The matchlet
, matchlet*
, matchletrec
,
and schemematchdefine 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:
(matchlet ([(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 matchletrec
and matchdefine
should not be used in computing the bound value.
The match
, matchlambda
, and matchlambda*
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.
Figure 1 gives the full syntax for patterns. Explanations of these patterns follow.
identifier
(excluding the reserved names
?, $, _, and
, or
, not
, set!
, get!
, ...
, and
..
k
for nonnegative integers k
) 
matches anything, and binds a variable of this name to
the matching value in the body.
_

matches anything, without binding any variables.
()
, #t
, #f
, string
, number
,
character
, '
sexpression

constant patterns that match themselves (i.e.,
the corresponding value must be
to the pattern).equal?
(
matches a proper list of n elements
that match pat_{1}
··· pat_{n}
)pat_{1}
through pat_{n}
.
(

matches a (possibly improper) list of at least pat_{1}
··· pat_{n}
. pat_{n+1}
)n
elements that ends in
something matching pat_{n} + 1
.
(

matches a proper list of n or more elements, where
each element of the tail matches pat_{1}
··· pat_{n}
pat_{n+1}
...
)pat_{n+1}
. Each pattern variable in
pat_{n+1}
is bound to a list of the matching values. For example,
the expression:
(match '(let ([x 1][y 2]) z) [('let ((binding vals) ...) exp) expr ···^{1}]) 
binding
to the list '(x y)
,
vals
to the list '(1 2)
,
and exp
to 'z
in the body of the match
expression.
For the special case where pat_{n+1}
is a pattern variable, the list
bound to that variable may share with the matched value.
(

similar to the previous pattern, but the tail must be
at least pat_{1}
··· pat_{n}
pat_{n+1}
..
k
)k
elements long.
The pattern keywords ..0
and ...
are equivalent.
#(

matches a vector of length n, whose elements match
pat_{1} through pat_{n}.pat_{1}
··· pat_{n}
)
The other vector matching patterns are similar to their list counterparts, described above.
#&

matches a box containing something matching pat
pat
.
(
 matches an instance of a
structure type $
structname
pat_{1}
··· pat_{n}
)structname
, where the instance contains n
fields.
Usually, structname
is defined with definestruct
.
More generally, structname
must be bound to expansiontime
information for a structure type (see section 12.6.3 in PLT MzScheme: Language Manual), where
the information includes at least a predicate binding and some field
accessor bindings (and pat_{1}
through pat_{n}
correspond
to the provided accessors). In particular, a module import or a
unit/sig
import with a signature containing a
struct
declaration (see section 37.2) can provide the
structure type information.
(

applies =
field
pat
)field
to the object being matched and
uses pat
to match the extracted
object. The field
subexpression may be any
expression, but is often useful as a struct selector.
(

matches if all of the subpatterns match.
This pattern is often used as and
pat_{1}
··· pat_{n}
)(
to bind and
x
pat
)x
to
to the entire value that matches pat
.
(

matches if any of the subpatterns match. At least
one subpattern must be present.
All subpatterns must bind the same set of pattern variables.or
pat_{1}
··· pat_{n}
)
(

matches if none of the subpatterns match.
The subpatterns may not bind any pattern variables.not
pat_{1}
··· pat_{n}
)
(

In this pattern,
?
predicateexpr
pat_{1}
··· pat_{n}
)predicateexpr
must be an expression evaluating to a single argument
function.
This pattern matches if predicateexpr
applied to the corresponding value
is true, and the subpatterns pat_{1}
through pat_{n}
all match.
The predicateexpr
should not have side effects, as
the code generated by the pattern matcher may invoke predicates repeatedly
in any order.
The predicateexpr
expression is bound in the same scope as the
match expression, so
free variables in predicateexpr
are not bound by pattern variables.
(

matches anything, and binds set!
identifier
)identifier
to a procedure of one argument that mutates the corresponding field of
the matching value.
This pattern must be nested within a pair, vector, box, or structure
pattern. For example, the expression:
(define x ( 
cadadr
of x to 4
, so that x
is
'(1 (2 4))
.
(

matches anything, and binds get!
identifier
)identifier
to a procedure of zero arguments that accesses the corresponding field of
the matching value. This pattern is the complement to set!
.
As with scmkset!,
this pattern must be nested within a pair, vector, box, or structure
pattern.
`

introduces a quasipattern, in which identifiers are considered
to be symbolic constants. Like Scheme's quasiquote for data,
quasipattern
unquote
(,
) and unquotesplicing
(,@
) escape back to
normal patterns.
If no clause matches the value, the reult is void.
This section illustrates the convenience of pattern matching with some examples. The following function recognizes some sexpressions that represent the standard Y operator:
(define Y? (matchlambda [('lambda (f1) ('lambda (y1) ((('lambda (x1) (f2 ('lambda (z1) ((x2 x3) z2)))) ('lambda (a1) (f3 ('lambda (b1) ((a2 a3) b2))))) y2))) (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.
(definestruct Lam (args body)) (definestruct Var (s)) (definestruct Const (n)) (definestruct App (fun args)) (define parse (matchlambda [(and s (?
symbol?
) (not
'lambda)) (makeVar s)] [(?
number?
n) (makeConst n)] [('lambda (and args ((?
symbol?
) ...) (not
(?
repeats?))) body) (makeLam args (parse body))] [(f args ...) (makeApp (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 (matchlambda [($
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 matchdefine
, 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:
(matchdefine (inc value reset) (let ([val 0]) (list
(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.