# How to match a pattern with a pattern?

UPDATED

This question is about: "What is the pattern to match a pattern-definition, exactly as it is written?"

My original question is now split according to Mr.Wizards insightful answer below. This question is about simple cases which can be solved with Verbatim. The other question (here) is what I should have asked originally: how to generally match and unify patterns and how to find their most general unifier. Therefore the following examples contain cases for both this and the other question. I won't modify these as it would ruin the understandability of the answers.

Consider the following pattern comparisons, which intuitively suggest a matching, though all returning False:

MatchQ[a | b, b | a]
MatchQ[{a ..}, {a ..}]
MatchQ[{a ..}, {a ...}]


The output I would like to have is True. The idea is that the first argument specifies an object that can either be a or b. I scan through a lot of these objects looking for those that can stand in for either a or b, see toy example:

rules = {a -> 1, b -> 2, c -> 3, a | b -> 4, c | d -> 5, d | b | c -> 6};
Cases[rules, _?(MatchQ[First@#, a | b] &)]


{a -> 1, b -> 2}

Instead, I need the output to be:

{a -> 1, b -> 2, a | b -> 4, d | b | c -> 6}

-

Use Verbatim. It was explicitly designed as an escaping mechanism for patterns. In this particular case:

Cases[rules,
_?(MatchQ[First@#,
b | a | (Verbatim[Alternatives][elems___] /; MemberQ[{elems}, a | b])] &
)
]


will do the trick.

-

It seems to me that there are these implicit questions in your post:

1. What is the pattern to match a pattern-definition, exactly as it is written?

2. How can I test if a given pattern intersects with, or is a subset of another pattern?

The second, the heart of your question I believe, is both good and challenging.
I shall answer the first one now, with the hope of answering the second one at a later time.

## Point 1: Matching an explicit pattern

The function Verbatim tells Mathematica to match the enclosed code itself rather than using it as a pattern definition. Example:

Cases[{1, 2, _, _, 5}, Verbatim[_]]

{_, _}


There is a related function that bears mentioning in this context: HoldPattern. This is somewhat similar to Verbatim but instead of telling Mathematica to not use the enclosed expression as a pattern, it tells Mathematica not to evaluate the expression.

{a, b, c} = {3, 4, 5};

Cases[Hold[1, 2, a, b, c], HoldPattern[b]]

{4}


On the other hand Verbatim evaluates its contents:

pat = _ ;

Cases[{1, 2, _, _, 5}, Verbatim[pat]]

{_, _}


These functions can be used on parts of an expression, not merely on a complete expression. To use these effectively you must become familiar with the FullForm of pattern expressions. Suppose we want to match expressions such as x_ or y_. The expression x_ can be written Pattern[x, _] but if we try to match the pattern Pattern[_, _] we get an error because Pattern tries to evaluate. We can use either HoldPattern or Verbatim to prevent this, the latter because Pattern by itself does not evaluate:

Cases[{1, 2, x_, y_, 5}, HoldPattern[Pattern][_, _]]
Cases[{1, 2, x_, y_, 5}, Verbatim[Pattern][_, _]]

{x_, y_}

{x_, y_}


It is not clear from the example above, but these patterns also match q__, r_Real, s___ because these are also of the form Pattern[name, type]:

Cases[{1, 2, x_, q__, r_Real, s___, 5}, HoldPattern[Pattern][_, _]]

{x_, q__, r_Real, s___}


If we want only expressions of the form name_ then we need to be more specific. We need Verbatim because it is not an issue of evaluation but rather one of recognition as a pattern construct.

 Cases[{1, 2, x_, q__, r_Real, s___, 5}, HoldPattern[Pattern][_, Verbatim[_]]]

{x_}

-
Nice classification of the problem, I definitely aimed for the second one. I think it would be reasonable to split my original question, and this thread could be for the first problem (Verbatim) while I pose a new question to answer the second. Should I do it, or should I just clarify this one? – István Zachar Mar 13 '12 at 11:15
@IstvánZachar I favor your posting a new question. None of the answers here really address that, and a new question will get more attention. I think it is a very interesting question and I intend to spend some time on it in the next few days, assuming that it is not quickly solved in a robust way by someone else. Please be quite specific regarding the behavior(s) that you want as I foresee defining those behaviors as a major aspect of the problem. Also, I think there will be unavoidable ambiguity in places, and it would be good to at least address how these should be approached. – Mr.Wizard Mar 13 '12 at 13:15
I've split the question. If you plan to post an answer for problem #2, please do it under the other one, here. – István Zachar Mar 14 '12 at 1:26

If you want to create a pattern that literally matches the pattern, the answer is as simple as I can imagine it: wrap Verbatim. If you want patterns to match their meaning, don't wrap anything. If you want some of them to match the meaning and some to match literally, you have to tell MMA somehow... This seems to be the case in your example, since you want Alternatives to take a literal meaning but its arguments to be interpreted as patterns with their usual meaning...

With these mixed cases. You can wrap Verbatim (or HoldPattern, or even another layer of Alternatives in cases where the head on itself is not a pattern like in your case) in the head of the pattern you want interpreted literally, like Leonid and R.M did in their answers. Could be Alternatives, Repeated, RepeatedNull, Pattern, etc... They are transparent to the structure but aren't interpreted as patterns. Then, you can specify the arguments as normal patterns. You could also do something like

FilterRules[rules, {a | b, (Alternatives /; True)[___, a | b, ___]}]


The case I can imagine to be not easy to handle is when you have a big structure to match literally, filled with patterns with a nested subexpression that you need interpreted as a pattern. For example, you want to check if something matches literally a | _b[c_, _[{r : 9 ..}, i_[{_, "anyString"}]]], where "anyString" could be any string. Probably in those cases, instead of wrapping Verbatim everywhere one could get smarter, but probably those cases aren't common... In any case, following the above, you succeed:

MatchQ[a | _b[c_, _[{r : 9 ..}, i_[{_, "sdfg"}]]],
Verbatim[Alternatives][a,
Verbatim[_b][Verbatim[c_],
Verbatim[_][Verbatim[{r : 9 ..}],
Verbatim[i_][{Verbatim[_], _String}]]]]]

-

Here is another solution that will do it:

FilterRules[rules, {a | b, Verbatim[Alternatives][___, a | b, ___]}]

-