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 originally done by Bruce Hauman and is maintained by Sam Tobin-Hochstadt.) 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)
Figure 1 gives the full syntax for
|Figure 1: Pattern Syntax|
The next subsection describes the various patterns.
match-lambda* forms are convenient
lambda, and can be explained
where x is a unique variable. The
(match-lambda (pat expr ···1) ...)
(lambda (x) (match x (pat expr ···1) ...))
(match-lambda* (pat expr ···1) ...)
(lambda x (match x (pat expr ···1) ...))
match-lambdaform 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.
match-define forms generalize
expressions to allow
patterns in the binding position rather than just variables.
For example, the following expression:
(match-let ([(x y z) (
list1 2 3)]) body)
3 in the body.
These forms are convenient for destructuring the result
of a function that returns multiple values.
As usual for
pattern variables bound by
should not be used in computing the bound value.
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 ?, =, $, _,
kfor non-negative integers
k) -- matches anything, and binds a variable of this name to the matching value in the body.
_-- matches anything, without binding any variables.
s-expression-- constant patterns that match themselves (i.e., the corresponding value must be
to the pattern).
(matches a proper list of n elements that match
(generalizes the preceding pattern, where each
lvpcorresponds to a ``spliced'' list of greedy matches.
(matches a proper list of n or more elements, where each element past the nth matches
patn+1. Each pattern variable in
patn+1is bound to a list of the matching values. For example, the expression:binds
(match '(let ([x 1][y 2]) z) [('let ((binding vals) ...) exp) expr ···1])
bindingto the list
valsto the list
'(1 2), and
'zin the body of the
match-expression. For the special case where
patn+1is a pattern variable, the list bound to that variable may share with the matched value.
___(which are equivalent),
kcan be used to match a sequence that is at least
klong. The pattern keywords
(-- matches a (possibly improper) list of at least
nelements that ends in something matching
(-- generalizes the preceding pattern with greedy-sequence
#(-- matches a vector of length n, whose elements match pat1 through patn. The generalization to
lvps matches consecutive elements of the vector greedily.
#&-- matches a box containing something matching
(-- matches an instance of a structure type
struct-name, where the instance contains
struct-nameis defined with
define-struct. More generally,
struct-namemust be bound to expansion-time information for a structure type (see section 12.6.4 in PLT MzScheme: Language Manual), where the information includes at least a predicate binding and some field accessor bindings (and
patncorrespond to the provided accessors). In particular, a module import or a
unit/sigimport with a signature containing a
structdeclaration (see section 52.2) can provide the structure type information.
fieldto the object being matched and uses
patto match the extracted object. The
fieldsubexpression 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
xto the entire value that matches
(-- matches if any of the subpatterns match. At least one subpattern must be present. All subpatterns must bind the same set of pattern variables.
(-- matches if none of the subpatterns match. The subpatterns may not bind any pattern variables.
(-- In this pattern,
predicate-exprmust be an expression evaluating to a single argument function. This pattern matches if
predicate-exprapplied to the corresponding value is true, and the subpatterns
patnall match. The
predicate-exprshould not have side effects, as the code generated by the pattern matcher may invoke predicates repeatedly in any order. The
predicate-exprexpression is bound in the same scope as the match expression, so free variables in
predicate-exprare not bound by pattern variables.
(-- matches anything, and binds
identifierto 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:mutates the
(define x (
list2 3))) (match x [(_ (_ (set! setit))) (setit 4)])
cadadrof x to
4, so that
'(1 (2 4)).
(-- matches anything, and binds
identifierto a procedure of zero arguments that accesses the corresponding field of the matching value. This pattern is the complement to
set!. As with
set!, 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,
,@) escape back to normal patterns.
There are two ways to extend or alter the behavior of match.
parameter controls the behavior of
When a variable appears more than once in a pattern, the values
matched by each instance are constrained to be the same in the sense
of the runtime value of
. The default
value of this parameter is
define-match-expander form extends the syntax of match
id proc-expr proc-expr)
id proc-expr proc-expr proc-expr)
This form binds an identifier to a pattern transformer.
proc-expr subexpression must evaluate to a transformer
that produces a pattern in the syntax of Chapter 32.
id appears as the beginning of a pattern in a the
context of the pattern matching forms defined in Chapter 32, this
transformer is given, at expansion time, a syntax object
corresponding to the entire pattern (including
pattern is the replaced with the result of the transformer.
If a second
proc-expr subexpression is provided, it must produce
a similar transformer, but in the context of patterns written in the
syntax of the current chapter.
A transformer produced by a third
proc-expr subexpression is
used when the
id keyword is used in a traditional macro use
context. In this way,
id can be given meaning both inside and
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? (match-lambda [('lambda (f1) ('lambda (y1) ((('lambda (x1) (f2 ('lambda (z1) ((x2 x3) z2)))) ('lambda (a1) (f3 ('lambda (b1) ((a2 a3) b2))))) y2))) (and (
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 (match-lambda [(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 ...) (make-App (parse f) (
mapparse args))] [x (
error'syntax "invalid expression")])) (define repeats? (lambda (l) (and (
null?l)) (or (
cdrl)) (repeats? (
cdrl)))))) (define unparse (match-lambda [($ Var s) s] [($ Const n) n] [($ Lam args body) `(lambda ,args ,(unparse body))] [($ App f args) `(,(unparse f) ,@(
With pattern matching, it is easy to ensure that the parser rejects all incorrectly formed inputs with an error message.
match-define, it is easy to define several procedures
that share a hidden variable. The following code defines three
that manipulate a hidden counter variable:
(match-define (inc value reset) (let ([val 0]) (
list(lambda () (set! val (
add1val))) (lambda () val) (lambda () (set! val 0)))))
Although this example is not recursive,
the bodies could recursively refer to each other.
The following code illustrates the creation of a match-expander that
works for both
(lib "match.ss") and
(require (prefix plt: (lib "plt-match.ss"))) (define-struct point (x y)) (define-match-expander Point (lambda (stx) (syntax-case stx () ((Point a b) #'(struct point (a b))))) (lambda (stx) (syntax-case stx () ((Point a b) #'($ point a b)))) (lambda (stx) (syntax-case stx () ((Point a b) #'(make-point a b))))) (define p (Point 3 4)) (match p ((Point x y) (+ x y))) ;; => 7 (plt:match p ((Point x y) (* x y))) ;; => 12