For Development HEAD DRAFTSearch (procedure/syntax/module):

Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]

12.89 util.match - Pattern matching

Module: util.match

This module is a port of Andrew Wright’s pattern matching macro library. It is widely used in the Scheme world, and ported to various Scheme implementations, including Chez Scheme, PLT Scheme, Scheme48, Chicken, and SLIB. It is similar to, but more powerful than Common Lisp’s destructuring-bind.

This version retains compatibility of the original Wright’s macro, except (1) box is not supported since Gauche doesn’t have one, and (2) structure matching is integrated to Gauche’s object system.

We show a list of APIs first, then the table of complete syntax of patterns, followed by examples.

Pattern matching API

Macro: match expr clause …

{util.match} Each clause is either one of the followings:

(pat body …)
(pat (=> identifier) body …)

First, the expr is matched against pat of each clauses. The detailed syntax of the pattern is explained below.

If a matching pat is found, the pattern variables in pat are bound to the corresponding elements in expr, then body … are evaluated. Then match returns the value(s) of the last expression of body ….

If the clause is the second form, identifier is also bound to the failure continuation of the clause. It is a procedure with no arguments, and when called, it jumps back to the matcher as if the matching of pat is failed, and match continues to try the rest of clauses. So you can perform extra tests within body … and if you’re not satisfied you can reject the match by calling (identifier). See the examples below for more details.

If no pat matches, match reports an error.

Macro: match-lambda clause …

{util.match} Creates a function that takes one argument and performs match on it, using clause …. It’s functionally equivalent to the following expression:

(lambda (expr) (match expr clause …))


(map (match-lambda
       ((item price-per-lb (quantity 'lbs))
        (cons item (* price-per-lb quantity)))
       ((item price-per-lb (quantity 'kg))
        (cons item (* price-per-lb quantity 2.204))))
     '((apple      1.23 (1.1 lbs))
       (orange     0.68 (1.4 lbs))
       (cantaloupe 0.53 (2.1 kg))))
 ⇒ ((apple . 1.353) (orange . 0.952)
            (cantaloupe . 2.4530520000000005))
Macro: match-lambda* clause …

{util.match} Like match-lambda, but performs match on the list of whole arguments. It’s functionally equivalent to the following expression:

(lambda expr (match expr clause …))
Macro: match-let ((pat expr) …) body-expr …
Macro: match-let name ((pat expr) …) body-expr …
Macro: match-let* ((pat expr) …) body-expr …
Macro: match-letrec ((pat expr) …) body-expr …

{util.match} Generalize let, let*, and letrec to allow patterns in the binding position rather than just variables. Each expr is evaluated, and then matched to pat, and the bound pattern variables are visible in body-expr ….

(match-let (
             (((ca . cd) ...)   '((a . 0) (b . 1) (c . 2)))
  (list ca cd))
 ⇒ ((a b c) (0 1 2))

If you’re sick of parenthesis, try match-let1 below.

Macro: match-let1 pat expr body-expr …

{util.match} This is a Gauche extension and isn’t found in the original Wright’s code. This one is equivalent to the following code:

(match-let ((pat expr)) body-expr …)

Syntactically, match-let1 is very close to the Common Lisp’s destructuring-bind.

(match-let1 ('let ((var val) ...) body ...)
            '(let ((a b) (c d)) foo bar baz)
  (list var val body))
 ⇒ ((a c) (b d) (foo bar baz))
Macro: match-define pat expr

{util.match} Like toplevel define, but allows a pattern instead of variables.

(match-define (x . xs) (list 1 2 3))

x  ⇒ 1
xs ⇒ (2 3)

Pattern syntax

Here’s a summary of pattern syntax. The asterisk (*) after explanation means Gauche’s extension which does not present in the original Wright’s code.

pat : patvar                       ;; anything, and binds pattern var
    | _                            ;; anything
    | ()                           ;; the empty list
    | #t                           ;; #t
    | #f                           ;; #f
    | string                       ;; a string
    | number                       ;; a number
    | character                    ;; a character
    | 'sexp                        ;; an s-expression
    | 'symbol                      ;; a symbol (special case of s-expr)
    | (pat1 ... patN)              ;; list of n elements
    | (pat1 ... patN . patN+1)     ;; list of n or more
    | (pat1 ... patN patN+1 ooo)   ;; list of n or more, each element
                                   ;;   of remainder must match patN+1
    | #(pat1 ... patN)             ;; vector of n elements
    | #(pat1 ... patN patN+1 ooo)  ;; vector of n or more, each element
                                   ;;   of remainder must match patN+1
    | ($ class pat1 ... patN)      ;; an object (patK matches in slot order)
    | (struct class pat1 ... patN) ;; ditto (*)
    | (@ class (slot1 pat1) ...)   ;; an object (using slot names) (*)
    | (object class (slot1 pat1) ...) ;; ditto (*)
    | (= proc pat)                 ;; apply proc, match the result to pat
    | (and pat ...)                ;; if all of pats match
    | (or pat ...)                 ;; if any of pats match
    | (not pat ...)                ;; if all pats don't match at all
    | (? predicate pat ...)        ;; if predicate true and all pats match
    | (set! patvar)                ;; anything, and binds setter
    | (get! patvar)                ;; anything, and binds getter
    | `qp                          ;; a quasi-pattern

patvar : a symbol except _, quote, $, struct, @, object, =, and, or,
         not, ?, set!, get!, quasiquote, ..., ___, ..k, __k.

ooo : ...                          ;; zero or more
    | ___                          ;; zero or more
    | ..k                          ;; k or more, where k is an integer.
                                   ;;   Example: ..1, ..2 ...
    | __k                          ;; k or more, where k is an integer.
                                   ;;   Example: __1, __2 ...

Pattern examples

A simple structure decomposition:

(match '(0 (1 2) (3 4 5))
  [(a (b c) (d e f))
   (list a b c d e f)])
 ⇒ (0 1 2 3 4 5)

Using predicate patterns:

(match 123
  [(? string? x) (list 'string x)]
  [(? number? x) (list 'number x)])
 ⇒ (number 123)

Extracting variables and expressions from let. Uses repetition and predicate patterns:

(define let-analyzer
    [('let (? symbol?)
           ((var expr) ...)
       body ...)
     (format "named let, vars=~s exprs=~s" var expr)]
    [('let ((var expr) ...)
       body ...)
     (format "normal let, vars=~s exprs=~s" var expr)]
     (format "malformed let")]))

(let-analyzer '(let ((a b) (c d)) e f g))
 ⇒ "normal let, vars=(a c) exprs=(b d)"

(let-analyzer '(let foo ((x (f a b)) (y (f c d))) e f g))
 ⇒ "named let, vars=(x y) exprs=((f a b) (f c d))"

(let-analyzer '(let (a) b c d))
 ⇒ "malformed let"

Using = function application. The pattern variable m is matched to the result of application of the regular expression.

(match "gauche-ref.texi"
  ((? string? (= #/(.*)\.([^.]+)$/ m))
   (format "base=~a suffix=~a" (m 1) (m 2))))
 ⇒ "base=gauche-ref suffix=texi"

An example of quasipattern. In the first expression, the pattern except value is quoted, so the symbols the, answer, and is are not pattern variables but literal symbols. The second expression shows that; input symbol was does not match the literal symbol is in the pattern. If we don’t use quasiquote, all symbols in the pattern are pattern variables, so any four-element list matches as the third expression shows.

(match '(the answer is 42)
  [`(the answer is ,value) value]
  [_ #f])
 ⇒ 42

(match '(the answer was 42)
  [`(the answer is ,value) value]
  [_ #f])
 ⇒ #f

(match '(a b c d)
  [(the answer is value) value]
  [_ #f])
 ⇒ d

An example of matching records. The following code implements “rotation” operation to balance a red-black tree.

(define-record-type T #t #t
  color left value right)

(define (rbtree-rotate t)
  (match t
    [(or ($ T 'B ($ T 'R ($ T 'R a x b) y c) z d)
         ($ T 'B ($ T 'R a x ($ T 'R b y c)) z d)
         ($ T 'B a x ($ T 'R ($ T 'R b y c) z d))
         ($ T 'B a x ($ T 'R b y ($ T 'R c z d))))
     (make-T 'R (make-T 'B a x b) y (make-T 'B c z d))]
    [_ t]))

Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]

For Development HEAD DRAFTSearch (procedure/syntax/module):