A portable hygienic pattern matcher.
This is a full superset of the popular match
package by Andrew Wright, written in fully portable
and thus preserving hygiene.
The most notable extensions are the ability to use non-linear
patterns - patterns in which the same identifier occurs multiple
times, tail patterns after ellipsis, and the experimental tree patterns.
(match expr (pat body ...) ...)where the result of
expris matched against each pattern in turn, and the corresponding body is evaluated for the first to succeed. Thus, a list of three elements matches a list of three elements.
(let ((ls (list 1 2 3))) (match ls ((1 2 3) #t)))
(match (list 1 2 3) ((a b c) b))
equal?to the first.
(match (list 1 2 1) ((a a b) 1) ((a b a) 2))
_matches anything, no matter how many times it is used, and does not bind the result in the body.
(match (list 1 2 1) ((_ _ b) 1) ((a b a) 2))
(match 'a ('b 1) ('a 2))
quasiquotecan be used to quote a mostly literally matching object with selected parts unquoted.
(match (list 1 2 3) (`(1 ,b ,c) (list b c)))
=> (2 3)
...after an element to match zero or more of that pattern (like a regexp Kleene star).
(match (list 1 2) ((1 2 3 ...) #t))
(match (list 1 2 3) ((1 2 3 ...) #t))
(match (list 1 2 3 3 3) ((1 2 3 ...) #t))
(match (list 1 2) ((a b c ...) c))
(match (list 1 2 3) ((a b c ...) c))
(match (list 1 2 3 4 5) ((a b c ...) c))
=> (3 4 5)
...may not be used in the same list, since this would require exponential backtracking in the general case. However,
...need not be the final element in the list, and may be succeeded by a fixed number of patterns.
(match (list 1 2 3 4) ((a b c ... d e) c))
(match (list 1 2 3 4 5) ((a b c ... d e) c))
(match (list 1 2 3 4 5 6 7) ((a b c ... d e) c))
=> (3 4 5)
___is provided as an alias for
...when it is inconvenient to use the ellipsis (as in a syntax-rules template). The
..1syntax is exactly like the
...except that it matches one or more repetitions (like a regexp "+").
(match (list 1 2) ((a b c ..1) c))
ERROR: match: "no matching pattern"
(match (list 1 2 3) ((a b c ..1) c))
notcan be used to group and negate patterns analogously to their Scheme counterparts. The
andoperator ensures that all subpatterns match. This operator is often used with the idiom
(and x pat)to bind
xto the entire value that matches
pat(c.f. "as-patterns" in ML or Haskell). Another common use is in conjunction with
notpatterns to match a general case with certain exceptions.
(match 1 ((and) #t))
(match 1 ((and x) x))
(match 1 ((and x 1) x))
oroperator ensures that at least one subpattern matches. If the same identifier occurs in different subpatterns, it is matched independently. All identifiers from all subpatterns are bound if the
oroperator matches, but the binding is only defined for identifiers from the subpattern which matched.
(match 1 ((or) #t) (else #f))
(match 1 ((or x) x))
(match 1 ((or x 2) x))
notoperator succeeds if the given pattern doesn't match. None of the identifiers used are available in the body.
(match 1 ((not 2) #t))
?can be used to provide a predicate. The usage is
(? predicate pat ...)where
predicateis a Scheme expression evaluating to a predicate called on the value to match, and any optional patterns after the predicate are then matched as in an
(match 1 ((? odd? x) x))
=is used to extract an arbitrary field and match against it. It is useful for more complex or conditional destructuring that can't be more directly expressed in the pattern syntax. The usage is
(= field pat), where
fieldcan be any expression, and should result in a procedure of one argument, which is applied to the value to match to generate a new value to match against
pat. Thus the pattern
(and (= car x) (= cdr y))is equivalent to
(x . y), except it will result in an immediate error if the value isn't a pair.
(match '(1 . 2) ((= car x) x))
(match 4 ((= square x) x))
$is used as a concise way to match records defined by SRFI-9 (or SRFI-99). The usage is
($ rtd field ...), where
rtdshould be the record type descriptor specified as the first argument to
define-record-type, and each
fieldis a subpattern matched against the fields of the record in order. Not all fields must be present.
(let () (define-record-type employee (make-employee name title) employee? (name get-name) (title get-title)) (match (make-employee "Bob" "Doctor") (($ employee n t) (list t n))))
=> ("Doctor" "Bob")
@operator, originally a Gauche extension:
(let () (define-record-type employee (make-employee name title) employee? (name get-name) (title get-title)) (match (make-employee "Bob" "Doctor") ((@ employee (title t) (name n)) (list t n))))
=> ("Doctor" "Bob")
get!operators are used to bind an identifier to the setter and getter of a field, respectively. The setter is a procedure of one argument, which mutates the field to that argument. The getter is a procedure of no arguments which returns the current value of the field.
(let ((x (cons 1 2))) (match x ((1 . (set! s)) (s 3) x)))
=> (1 . 3)
(match '(1 . 2) ((1 . (get! g)) (g)))
***can be used to search a tree for subpatterns. A pattern of the form
(x *** y)represents the subpattern
ylocated somewhere in a tree where the path from the current object to
ycan be seen as a list of the form
ycan immediately match the current object in which case the path is the empty list. In a sense it's a 2-dimensional version of the
...pattern. As a common case the pattern
(_ *** y)can be used to search for
yanywhere in a tree, regardless of the path used.
(match '(a (a (a b))) ((x *** 'b) x))
=> (a a a)
(match '(a (b) (c (d e) (f g))) ((x *** 'g) x))
=> (a c f)
expris matched against each
patternin turn, according to the pattern rules described in the previous section, until the the first
patternmatches. When a match is found, the corresponding
bodys are evaluated in order, and the result of the last expression is returned as the result of the entire
match. If a
failureis provided, then it is bound to a procedure of no arguments which continues, processing at the next
pattern. If no
patternmatches, an error is signalled.
match. Creates a procedure of one argument, and matches that argument against each clause.
match-lambda. Creates a procedure of any number of arguments, and matches the argument list against each clause.
match-let, but analogously to
letrecmatches and binds the variables with all match variables in scope.
match-let, but analogously to
let*matches and binds the variables in sequence, with preceding match variables in scope.