cl-match compares the structure of a value with a pattern and binds variables to parts of the structure. This can be done with either of two macros: MATCH and IFMATCH. IFMATCH takes three arguments and a body of code. The arguments are a pattern, an expression whose value will be compared with the pattern, and a form to be evaluated on a match. The body is evaluated if the pattern doesn't match.

A value can be tested against multiple patterns with MATCH, which is related to IFMATCH in the same way that COND is related to IF[1]. New patterns can be defined by the user with DEFPATTERN.

All patterns are written as s-expressions. A pattern can be either an atom or a list. A literal atom generates an EQL test. A symbol generates a variable binding on its first occurance in the pattern, and an EQL test on each subsequent occurance. The wildcard symbol _ matches anything.

Lists are used to represent compound patterns, which usually take one or more arguments. Most arguments either are or contain patterns to be matched by subsections of the value being matched by the overall pattern. These patterns are currently implemented: ACSRS, AND, ARRAY, AS, CONS, LIST, LIST*, OR, QUOTE, SLOTS, STRUCT, TYPE, VALS, and VEC. Each OR pattern creates branches for alternative patterns, and a VALS pattern at the top level of the overall pattern will bind multiple values.

Guards are written as WHEN forms, where the first argument is the guard test, and the second argument is the pattern. The second argument is optional, and defaults to _. If one or more OR patterns are present, branch-specific guards can be included immediately inside the corresponding ORs. Otherwise, only the outermost form can be a guard.

New patterns can be defined with the DEFPATTERN macro. Built-in patterns can be overridden, and overridden built-in patterns can be accessed by specifying their names as strings instead of symbols.

(macro)
defpattern name args &body body

Defines a new pattern. The pattern will be a list whose first element is the symbol name and whose remainder is specified by args. The macro is expected to return a valid pattern.

(macro)
ifmatch pattern expr onmatch &rest on-mismatch

Evaluates expr, and compares it to pattern, binding names in pattern as they're encountered. Evaluates onmatch if the pattern matches, otherwise evaluates on-mismatch.

(macro)
letmatch pattern expr &rest onmatch

Same as ifmatch, except there are no on-mismatch forms, the onmatch forms are inlined, and an error is signaled on mismatch.

(macro)
match expr {(pattern &rest body)}*

Evaluates expr, then compares the resulting value to each pattern in succession until a pattern matches, then evaluates the body immediately following the successful pattern.

acsrs &rest forms
Each specified accessor must be defined for the value. Each form can be either a two-element list, where the first element is the name of the accessor and the second element is a pattern, or a symbol (the accessor), which always matches as long as the accessor exists and can be applied to the value.

and &rest patterns
The value must match all the patterns.

array spec patrn-tree
The value must be an array whose rank rank is specified by spec. If spec is an integer, it represents rank. If spec is a list, the first element is rank and the optional second element is a type specifier. The array's dimensions must match the dimensions of patrn-tree down to depth rank, and its elements must match the corresponding patterns in patrn-tree at depth rank. If the type is specified, each element in the array must have that type.

as name pattern
Binds the symbol name to the value (or compares the value to the current value if name is already bound) before testing the value against pattern.

cons p-car p-cdr
The value must be a cons. The car and cdr of the value are matched against the patterns p-car and p-cdr. Equivalent to (list* p-car p-cdr).

list &rest patterns
The value must be a list whose length is equal to that of patterns, and whose elements match the corresponding elements of patterns.

list* &rest patterns
Same as LIST, except the last argument is the remainder of the list.

or &rest patterns
Allows alternative patterns. Each pattern can have a WHEN guard in its outermost form, and the guard will apply only to that branch.
The outermost OR can contain VALS patterns, as long as they all have the same number of patterns (and bind the same variables).
Branches are searched in left-to-right, depth-first order.

quote value
Generates an EQL test with the quoted value.

slots &rest slot-forms
The value must be a standard object containing the slots specified in slot-forms. Each slot form can be either a symbol, or a list with one or two elements. If the slot form is a symbol, it binds the slot to a variable of the same name. If it's a list, the first element is the slot name, and the optional second element is a pattern, which defaults to _.

struct prefix &rest field-forms
The value must be a structure, and each field must be accessible with a function whose name begins with prefix. Each field form can be either a two-element list, where the first element is the field name and the second element is a pattern, or a symbol (the field's name), which always matches.

type type &optional pattern
The value must have type type and must match the pattern pattern, which defaults to _.

vals &rest patterns
Binds and analyzes multiple values. VALS is allowed only at the top level of a pattern.

vec patrn-list &optional elt-type
The value must be a vector whose length and elements match those of patrn-list. Equivalent to (array (1 elt-type) patrn-list).

when test &optional pattern
If the current branch of the pattern's OR tree matches, then the guard expression test and all other guards applicable to pattern are evaluated as a final boolean test for that branch. pattern defaults to _.

Here's a function that flattens a list by recursively looking at the structure of its parts. Empty sublists (NILs) are retained in the result.

(defun flatten (x)
  (match x ((type atom) (list x))
           ((list car) (flatten car)) ;only one element
           ((cons car cdr) (append (flatten car)
                                   (flatten cdr)))))

NOT patterns would be nice if they didn't mess with OR patterns and variable bindings. But they have some tricky interactions, so they're not implemented yet.

Custom structure predicates aren't supported yet.