7.7 Pattern Matching

The (ice-9 match) module provides a pattern matcher, written by Alex Shinn, and compatible with Andrew K. Wright’s pattern matcher found in many Scheme implementations.

A pattern matcher can match an object against several patterns and extract the elements that make it up. Patterns can represent any Scheme object: lists, strings, symbols, records, etc. They can optionally contain pattern variables. When a matching pattern is found, an expression associated with the pattern is evaluated, optionally with all pattern variables bound to the corresponding elements of the object:

(let ((l '(hello (world))))
  (match l           ;; <- the input object
    (('hello (who))  ;; <- the pattern
     who)))          ;; <- the expression evaluated upon matching
⇒ world

In this example, list l matches the pattern ('hello (who)), because it is a two-element list whose first element is the symbol hello and whose second element is a one-element list. Here who is a pattern variable. match, the pattern matcher, locally binds who to the value contained in this one-element list—i.e., the symbol world.

The same object can be matched against a simpler pattern:

(let ((l '(hello (world))))
  (match l
    ((x y)
     (values x y))))
⇒ hello
⇒ (world)

Here pattern (x y) matches any two-element list, regardless of the types of these elements. Pattern variables x and y are bound to, respectively, the first and second element of l.

The pattern matcher is defined as follows:

Scheme Syntax: match exp clause ...

Match object exp against the patterns in the given clauses, in the order in which they appear. Return the value produced by the first matching clause. If no clause matches, throw an exception with key match-error.

Each clause has the form (pattern body). Each pattern must follow the syntax described below. Each body is an arbitrary Scheme expression, possibly referring to pattern variables of pattern.

The syntax and interpretation of patterns is as follows:

        patterns:                       matches:

pat ::= identifier                      anything, and binds identifier
      | _                               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)
      | (pat_1 ... pat_n)               list of n elements
      | (pat_1 ... pat_n . pat_{n+1})   list of n or more
      | (pat_1 ... pat_n pat_n+1 ooo)   list of n or more, each element
                                          of remainder must match pat_n+1
      | #(pat_1 ... pat_n)              vector of n elements
      | #(pat_1 ... pat_n pat_n+1 ooo)  vector of n or more, each element
                                          of remainder must match pat_n+1
      | #&pat                           box
      | ($ record-name pat_1 ... pat_n) a record
      | (= field pat)                   a ``field'' of an object
      | (and pat_1 ... pat_n)           if all of pat_1 thru pat_n match
      | (or pat_1 ... pat_n)            if any of pat_1 thru pat_n match
      | (not pat_1 ... pat_n)           if all pat_1 thru pat_n don't match
      | (? predicate pat_1 ... pat_n)   if predicate true and all of
                                          pat_1 thru pat_n match
      | (set! identifier)               anything, and binds setter
      | (get! identifier)               anything, and binds getter
      | `qp                             a quasi-pattern
      | (identifier *** pat)            matches pat in a tree and binds
                                        identifier to the path leading
                                        to the object that matches pat

ooo ::= ...                             zero or more
      | ___                             zero or more
      | ..1                             1 or more

        quasi-patterns:                 matches:

qp  ::= ()                              the empty list
      | #t                              #t
      | #f                              #f
      | string                          a string
      | number                          a number
      | character                       a character
      | identifier                      a symbol
      | (qp_1 ... qp_n)                 list of n elements
      | (qp_1 ... qp_n . qp_{n+1})      list of n or more
      | (qp_1 ... qp_n qp_n+1 ooo)      list of n or more, each element
                                          of remainder must match qp_n+1
      | #(qp_1 ... qp_n)                vector of n elements
      | #(qp_1 ... qp_n qp_n+1 ooo)     vector of n or more, each element
                                          of remainder must match qp_n+1
      | #&qp                            box
      | ,pat                            a pattern
      | ,@pat                           a pattern

The names quote, quasiquote, unquote, unquote-splicing, ?, _, $, and, or, not, set!, get!, ..., and ___ cannot be used as pattern variables.

Here is a more complex example:

(use-modules (srfi srfi-9))

(let ()
  (define-record-type person
    (make-person name friends)
    person?
    (name    person-name)
    (friends person-friends))

  (letrec ((alice (make-person "Alice" (delay (list bob))))
           (bob   (make-person "Bob" (delay (list alice)))))
    (match alice
      (($ person name (= force (($ person "Bob"))))
       (list 'friend-of-bob name))
      (_ #f))))

⇒ (friend-of-bob "Alice")

Here the $ pattern is used to match a SRFI-9 record of type person containing two or more slots. The value of the first slot is bound to name. The = pattern is used to apply force on the second slot, and then checking that the result matches the given pattern. In other words, the complete pattern matches any person whose second slot is a promise that evaluates to a one-element list containing a person whose first slot is "Bob".

Please refer to the ice-9/match.upstream.scm file in your Guile installation for more details.

Guile also comes with a pattern matcher specifically tailored to SXML trees, See section sxml-match: Pattern Matching of SXML.

This document was generated on February 3, 2012 using texi2html 5.0.