match

Pattern matching

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

match(expression, pattern, options)

Description

match(expression, pattern) checks whether the syntactical structure of expression matches pattern. If so, the call returns a set of replacement equations transforming pattern into expression.

match computes a set of replacement equations S for the identifiers occurring in pattern, such that subs(pattern, S) and expression coincide up to associativity, commutativity, and neutral elements.

Without additional options, a purely syntactical matching is performed; associativity, commutativity, or neutral elements are taken into account only for the builtin operators + and *, and and or, and union and intersect. In this case, subs(pattern, S) = expression holds for the set S of replacement equations returned by match if the matching was successful. Cf. Example 1. You can declare these properties for operators via the options Associative, Commutative, and Null (see below). Then subs(pattern, S) and expression need no longer be equal in MuPAD®, but they can be transformed into each other by application of the rules implied by the options.

Both expression and pattern may be arbitrary MuPAD expressions, i.e., both atomic expressions such as numbers, Boolean constants, and identifiers, and compositeexpressions.

Each identifier without a value that occurs in pattern, including the 0th operands, is regarded as a pattern variable, in the sense that it may be replaced by some expression in order to transform pattern into expression. Use the option Const (see below) to declare identifiers as non-replaceable.

With the exception of some automatic simplifications performed by the MuPAD kernel, distributivity is not taken into account. Cf. Example 5.

    Note:   match evaluates its arguments, as usual. This evaluation usually encompasses a certain amount of simplification, which may change the syntactical structure of both expression and pattern in an unexpected way. Cf. Example 6.

Even if there are several possible matches, match returns at most one of them. Cf. Example 7.

If the structure of expression does not match pattern, match returns FAIL.

If expression and pattern are equal, the empty set is returned.

Otherwise, if a match is found and expression and pattern are different, then a set S of replacement equations is returned. For each pattern variable x occurring in pattern that is not declared constant via the option Const, S contains exactly one replacement equation of the form x = y, and y is the expression to be substituted for x in order to transform pattern into expression.

Examples

Example 1

All identifiers of the following pattern are pattern variables:

match(f(a, b), f(X, Y))

The function f is declared non-replaceable:

match(f(a, b), f(X, Y), Const = {f})

Example 2

The following call contains a condition for the pattern variable X:

match(f(a, b), f(X, Y), Const = {f}, Cond = {X -> not has(X, a)})

If the function f is declared commutative, the expression matches the given pattern—in contrast to the preceding example:

match(f(a, b), f(X, Y), Const = {f}, Commutative = {f},
                        Cond = {X -> not has(X, a)})

Example 3

The following expression cannot be matched since the number of arguments of the expression and the pattern are different:

match(f(a, b, c), f(X, Y), Const = {f})

We declare the function f associative with the option Associative. In this case the pattern matches the given expression:

match(f(a, b, c), f(X, Y), Const = {f}, Associative = {f})

Example 4

If, however, the function call in the pattern has more arguments than the corresponding function call in the expression, no match is found:

match(f(a, b), f(X, Y, Z), Const = {f}, Associative = {f})

If the neutral element with respect to the operator f is known, additional matches are possible by substituting it for some of the pattern variables:

match(f(a, b), f(X, Y, Z), Const = {f},
     Associative = {f}, Null = {f = 0})

Example 5

Distributivity is not taken into account in general:

match(a*x + a*y, a*(X + Y), Const = {a})

The next call finds a match, but not the expected one:

match(a*(x + y), X + Y)

The following declarations and conditions do not lead to the expected result, either:

match(a*(x + y), a*X + a*Y, Const = {a},
                            Cond = {X -> X <> 0, Y -> Y <> 0})

Example 6

Automatic simplifications can "destroy" the structure of the given expression or pattern:

match(sin(-2), sin(X))

The result is FAIL, because the first argument sin(-2) is evaluated and rewritten to -sin(2):

sin(-2)

You can circumvent this problem by using hold:

match(hold(sin(-2)), sin(X))

Example 7

match returns only one possible match:

match(a + b + c + 1, X + Y)

To obtain other solutions, use conditions to exclude the solutions that you already have:

match(a + b + c + 1, X + Y, Cond = {X <> a})

match(a + b + c + 1, X + Y, Cond = {X <> a and Y <> a})

match(a + b + c + 1, X + Y,
      Cond = {X <> a and X <> b and Y <> a})

Example 8

Every pattern variable can have at most one condition procedure. Simple conditions can be given by anonymous procedures (->):

match(a + b, X + Y, Cond = {X -> X <> a, Y -> Y <> b})

Several conditions on a pattern variable can be combined in one procedure:

Xcond := proc(X) begin
  if domtype(X) = DOM_IDENT then
    X <> a and X <> b
  else
    X <> 0
  end_if
end_proc:
match(sin(a*b), sin(X*Y), Cond = {Xcond})

match(sin(a*c), sin(X*Y), Cond = {Xcond})

delete Xcond:

Parameters

expression

A MuPAD expression

pattern

The pattern: a MuPAD expression

option1, option2, …

Optional arguments as listed below

Options

Associative

Option, specified as Associative = {f1, f2, …}

It is assumed that identifiers f1, f2, ... represent associative operators and may take an arbitrary number of arguments, i.e., expressions such as f1(f1(a, b), c), f1(a, f1(b, c)), and f1(a, b, c) are considered equal.

No special rules for associative operators with less than two arguments apply. In particular, f1(a) and a are not considered equal.

Commutative

Option, specified as Commutative = {g1, g2, …}

It is assumed that the identifiers g1, g2, ... represent commutative operators, i.e., expressions such as g1(a, b) and g1(b, a) are considered equal.

Cond

Option, specified as Cond = {p1, p2, …}

Only matches satisfying the conditions specified by the procedures p1, p2, ... are considered. Each procedure must take exactly one argument and represents a condition on exactly one pattern variable. The name of the procedure's formal argument must be equal to the name of a pattern variable occurring in pattern that is not declared constant via the option Const. Each condition procedure must return an expression that the function bool can evaluate to one of the Boolean values TRUE or FALSE.

Anonymous procedures created via -> can be used to express simple conditions. Cf. Example 8.

If a possible match is found, given by a set of replacement equations S, then match checks whether all specified conditions are satisfied by calling bool(p1(y1) and p2(y2) and ...), where y1 is the expression to be substituted for the pattern variable x1 that agrees with the formal argument of the procedure p1, etc. If the return value of the call is TRUE, then match returns S. Otherwise, the next possible match is tried.

For example, if p1 is a procedure with formal argument x1, where x1 is a pattern variable occurring in pattern, then a match S = {..., x1 = y1, ...} is considered valid only if bool(p1(y1)) returns TRUE.

There can be at most one condition procedure for each pattern variable. If necessary, use the logical operators and and or as well as the control structures if and case to combine several conditions for the same pattern variable in one condition procedure. Cf. Example 8.

Const

Option, specified as Const = {c1, c2, …}

The identifiers c1, c2, ... are regarded as constants, i.e., they must match literally and must not be replaced in order to transform pattern into expression.

Null

Option, specified as Null = {h1 = e1, h2 = e2, …}

It is assumed that e1, e2, ... are the neutral elements with respect to the associative operations h1, h2, ... i.e., expressions such as h1(a, e1), h1(e1, a), and h1(a) are considered equal.

This declaration affects only operators that are declared associative via the option Associative. Moreover, the neutral elements are not implicitly assumed to be constants.

Return Values

Set of replacement equations, or FAIL.

See Also

MuPAD Functions

Was this topic helpful?