match
-- pattern matchingmatch(
expression, pattern)
checks whether
the syntactical structure of expression
matches
pattern
, and if so, returns a set of replacement equations
transforming pattern
into expression
.
match(expression, pattern <, option1, option2,
...>)
expression |
- | a MuPAD expression |
pattern |
- | the pattern: a MuPAD expression |
option1, option2, ... |
- | optional arguments (see below) |
Ass = {f1, f2,
...} |
- | assume that the identifiers f1, f2, ... represent
associative operators |
Comm = {g1, g2,
...} |
- | assume that the identifiers g1, g2, ... represent
commutative operators |
Cond = {p1, p2,
...} |
- | conditional matching: consider only matches for which
the conditions specified by the procedures
p1, p2, ... are satisfied |
Const = {c1, c2,
...} |
- | assume that the identifiers c1, c2, ... represent
constants |
Null = {h1 = e1, h2 = e2,
...} |
- | assume that the identifiers e1, e2, ... represent the
neutral elements with respect to the operators h1, h2,
... , respectively |
a set of replacement equations or FAIL
.
matchlib::analyze
, simplify
, subs
, subsex
, subsop
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.Most of the functionality of match
is
available via additional options. However, match
is still
in an experimental state, and some features may not work properly,
yet.
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 Ass, Comm, 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.expression
and pattern
may be
arbitrary MuPAD expressions, i.e., both atomic expressions such
as numbers, Boolean constants, and identifiers, and composite expressions.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.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.
match
returns at most one of them. Cf. example 7.expression
does not match
pattern
, match
returns FAIL
.expression
and pattern
are equal, the
empty set is returned.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
.f1, f2, ...
are
associative 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.f1(a)
and a
are not considered equal.g1, g2, ...
are assumed to be
commutative, i.e., expressions such as g1(a, b)
and
g1(b, a)
are considered equal.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.
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
.
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.c1, c2, ...
are regarded as constants,
i.e., they must match literally and must not be replaced in order to
transform pattern
into expression
.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.All identifiers of the following pattern are pattern variables:
>> match(f(a, b), f(X, Y))
{X = a, Y = b, f = f}
The function f
is declared
non-replaceable:
>> match(f(a, b), f(X, Y), Const = {f})
{X = a, Y = b}
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)})
FAIL
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}, Comm = {f}, Cond = {X -> not has(X, a)})
{X = b, Y = a}
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})
FAIL
We declare the function f
associative with
the option Ass. In this case the pattern matches
the given expression:
>> match(f(a, b, c), f(X, Y), Const = {f}, Ass = {f})
{X = a, Y = f(b, c)}
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}, Ass = {f})
FAIL
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}, Ass = {f}, Null = {f = 0})
{X = a, Z = b, Y = 0}
Distributivity is not taken into account in general:
>> match(a*x + a*y, a*(X + Y), Const = {a})
FAIL
The next call finds a match, but not the expected one:
>> match(a*(x + y), X + Y)
{Y = a (x + y), X = 0}
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})
FAIL
Automatic simplifications can ``destroy'' the structure of the given expression or pattern:
>> match(sin(-2), sin(X))
FAIL
The result is FAIL
, because the first argument
sin(-2)
is evaluated:
>> sin(-2)
-sin(2)
You can circumvent this problem by using hold
:
>> match(hold(sin(-2)), sin(X))
{X = -2}
match
returns only one possible match:
>> match(a + b + c + 1, X + Y)
{X = a, Y = b + c + 1}
To obtain other solutions, use conditions to exclude the solutions that you already have:
>> match(a + b + c + 1, X + Y, Cond = {X -> X <> a})
{X = b, Y = a + c + 1}
>> match(a + b + c + 1, X + Y, Cond = {X -> X <> a and X <> b})
{X = c, Y = a + b + 1}
>> match(a + b + c + 1, X + Y, Cond = {X -> not X in {a, b, c}})
{Y = a + b + c, X = 1}
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})
{X = b, Y = a}
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})
{Y = a b, X = 1}
>> match(sin(a*c), sin(X*Y), Cond = {Xcond})
{Y = a, X = c}
>> delete Xcond: