I'm using the term "depth-agnostic" in this post to describe structural patterns featuring a "target" sub-pattern that can occur "at any depth" relative to one or more "context" sub-patterns.
As a simple example of a "depth-agnostic" pattern, consider the following rewrite rule:
RR1
replace with the expression
WRAP[X]
any expressionX_TGT
contained somewhere within some expression_CTX
.1
Here the target and context sub-patterns are X_TGT
and _CTX
, respectively. The depth-agnostic bit comes in as the phrase "somewhere within".
In other words, RR1 says to find expressions that look like
… CTX[ … y0[ … y1[ … … yk[ … TGT[ … ] … ] … … ] … ] … ] …
...(where the number of nested subexpressions y0
, y1
, ..., yk
is indeterminate), and rewrite them as
… CTX[ … y0[ … y1[ … … yk[ … WRAP[TGT[ … ]] … ] … … ] … ] … ] …
Thus, if we defined
ping = foo[{1, CTX[bar[2, 3, {TGT[0], 4} ]]}];
ding = foo[{1, CTX[bar[2, {3, {TGT[0], 4}}]]}];
pong = foo[{1, baz[bar[2, 3, {TGT[0], 4} ]]}];
then, according to RR1, ping
would be changed to
foo[{1, CTX[bar[2, 3, {WRAP[TGT[0]], 4} ]]}]
...and ding
would be changed to
foo[{1, CTX[bar[2, {3, {WRAP[TGT[0]], 4}}]]}]
On the other hand, pong
would be unaffected by RR1, even though it contains an expression _TGT
, because this expression does not occur "somewhere within an expression _CTX
".
The problem is
how to implement a rewrite rule that features such a "depth-agnostic" pattern in Mathematica?
To see why "depth-agnosticity" is an issue, consider rewrite rule RR2 below, identical in every way to RR1, except that it specifies a single, unambiguous depth for the target relative to the context sub-pattern (IOW, it is not "depth-agnostic"):
RR2
replace with the expression
WRAP[X]
any expressionX_TGT
contained at a depth of 3 within some expression_CTX
.
As shown below, implementing RR2 in Mathematica is straightforward (though, admittedly, a bit tedious), but unfortunately, it is nowhere as general as RR1 (e.g. RR2 affects only ping
, not ding
).
Here's one (rather uninspired) implementation of RR2 in action:
{ping, ding, pong} /.
CTX[a1___, h1_[a2___, h2_[a3___, X_TGT, z3___], z2___], z1___] ->
CTX[a1, h1[a2, h2[a3, WRAP[X], z3], z2], z1] // TableForm
foo[{1, CTX[bar[2, 3, {WRAP[TGT[0]], 4}]]}]
foo[{1, CTX[bar[2, {3, {TGT[0], 4}}]]}]
foo[{1, baz[bar[2, 3, {TGT[0], 4}]]}]
This implementation fulfills the earlier assertions about RR2: it like RR1 with respect to ping
(affects it) and pong
(does not affect it), but not with respect to ding
(RR1 affects ding
but RR2 doesn't).
There are at least two important generalizations of the ideas described above. The first one is the situation in which there are multiple context sub-patterns that are themselves at indeterminate depths relative to each other. For example:
RR3
replace with the expression
WRAP[X]
any expressionX_TGT
and being contained somewhere within some expression_CTX
that is itself contained somewhere within some expression_List
.
The second generalization could be expressed as allowing "negative depths", or in other words, patterns in which the context sub-pattern is contained within the target subpattern. For example:
RR4
replace with the expression
WRAP[X]
any expressionX_TGT
containing somewhere within it some expression_CTX
.
1In this post I will resort to Mathematica's notation for patterns. Namely, _H
denotes a pattern matching any expression having head H
, and X_H
denotes a pattern matching any expression (henceforth referred to as X
) having head H
. I will abuse this notation slightly, writing "an expression _H
" as shorthand for "an expression matching the pattern _H
", and "an expression X_H
" as shorthand for "an expression (henceforth referred to as X
) matching the pattern _H
.)