How to generally match, unify and merge patterns?

Question

This question was split from this one. While that question is now about how to match two particular patterns (mostly using Verbatim or HoldPattern), this question is about how to match any pattern with another one, in other words: "How can I test if a given pattern intersects with, or is a subset of another pattern?" (borrowed from Mr.Wizard). Consider the following examples where one can see that the left pattern should "match" the right one, but which all return False:

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

Of course one trivial way to deal with Alternatives would be to simply Sort its arguments:

MatchQ[a | b | c, Verbatim[Sort[b | c | a]]]  --->  True

but things get complicated if the pattern involves more than Alternatives.

Problem specification:

Therefore I am looking for a predicate function that compares any pattern with another pattern and decides whether the first one matches the second one. For this, one needs a general way of matching two expressions that may contain any of these operators: {|, .., ..., _, __, ___} and possibly anything else that is specific for patterns. The predicate should have the following behaviour:

PatternMatchQ::usage="PatternMatchQ[e1, e2] returns True
if the set of expressions matched by pattern e1 is the same
or is a subset of the expressions matched by pattern e2, False otherwise."

i.e. the first pattern should cover the same (or smaller) domain as the second does. Now of course if any of the arguments is a non-pattern, PatternMatchQ can fall back to MatchQ.

Examples:

• a|b agrees with b|a
• a|b agrees with c|b|a (as a|b covers a domain that is covered by a|b|c as well)
• a|b|c does not agree with b|a (as a|b|c covers a domain that is larger than the domain covered by b|a unless c == a or c == b, in which case the pattern simplifies to a|b)
• {a..} agrees with {a..}
• {a..} agrees with {a...}
• {a...} does not agree with {a..}

Extension:

Now the concept of matching can be extended in the following way. So far we were only concerned about whether it is true that $domain(e_1) \subseteq domain(e_2)$, and if not, return False. But even if the test gives false, it is possible to define the smallest (most simple) domain that both patterns cover. Also, a full pattern-set-algebra emerges, if one thinks it further. Accordingly, for example PatternUnion could work on any number of arguments, and should return the most general unifier of all the argument patterns. The union of patterns would be equivalent to the merging of patterns.

Now, of course, "The thing that hath been, it is that which shall be; and that which is done is that which shall be done: and there is no new thing under the sun"... in certain fields (e.g. in logic or in linguistics and especially in construction grammar), this method is called unification:

Two expressions $e_1$ and $e_2$ are said to unify iff there exists a substitution $s$ such that $s(e_1) = s(e_2)$

where a substitution is a binding of variables (i.e. implicit, hidden variables introduced by Mathematica to deal with e.g. _, __) in patterns $e_1$ and $e_2$ with actual fitting values. Note that the substituted value of a pattern-variable can be any atom, even symbols, it does not matter. Thus what the code should look for is the equality of variables (i.e. implicit pattern variables). If such an $s$ exists, it is called a unifier. It is known that if two expressions $e_1$ and $e_2$ unify, then there always is only one most general unifier (up to a renaming of variables). Now this general unifier of two pattern expressions can be called (or used to describe) the intersection of $e_1$ and $e_2$.

Answer 1

In my opinion, this is a very good and worthwhile question, but certainly not easy to answer. I don't have a full solution by any means, but as far as the comparison/matching part is concerned, the undocumented function Internal`ComparePatterns may be of substantial assistance. What follows is a short summary of what I know about this function, which exists in Mathematica 7 and 8, but not version 5.2. I would guess that it is new-in-6 and used in the implementation of OptionsPattern and related functions.

Internal`ComparePatterns[p, q] (where p and q are patterns) operates somewhat like MatchQ, except that rather than simply True or False to signify agreement or disagreement, multiple (namely, five) possibilities exist to describe the relationship p has to q:

1. Identity

   Two patterns are considered identical if they match verbatim up to, but not including, naming. This relation should obviously be transitive and commutative, and I haven't observed any counterexamples so far. An example could be:

   Internal`ComparePatterns[a_, b_]
   (* -> "Identical" *)
   

   It is also aware of attributes that affect pattern matching. Here we attempt to mask the Orderless attribute of Plus (and thus possibly confuse Internal`ComparePatterns) by wrapping it in HoldComplete:

   Internal`ComparePatterns[
    HoldComplete[x_Real + y_Integer],
    HoldComplete[y_Integer + x_Real]
   ]
   (* -> "Identical" *)
   

   Pattern names are not completely ignored, however, and seem to be taken into account where appropriate:

   Internal`ComparePatterns[x_Real + y_Integer, x_Integer + y_Real]
   (* -> "Incomparable" *)
   

2. Equivalence

   If p has the same meaning as q but is not structurally identical, the patterns are considered equivalent:

   Internal`ComparePatterns[a | b, b | a] (* Alternatives is not Orderless *)
   (* -> "Equivalent" *)
   
   Internal`ComparePatterns[a : y_ + x_, b : (f : Plus)[x_, y_]]
   (* -> "Equivalent" *)
   

   However, determination of this relationship is not completely robust. Patterns that are sufficiently structurally different sometimes will not be considered equivalent even if they manifestly are:

   Internal`ComparePatterns[a : y_ + x_, b : (f : Plus | Plus)[x_, y_]]
   (* -> "Specific" *)
   

   Here are two more examples of patterns that are equivalent, but where the relationship is misstated. The second of these is particularly interesting:

   Internal`ComparePatterns[Repeated[_, Infinity], Repeated[_]]
   (* -> "Specific" *)
   
   Internal`ComparePatterns[Repeated[_, {1, Infinity}], Repeated[_, Infinity]]
   (* -> "Identical" *)
   

3. Specificity

   In some circumstances, Internal`ComparePatterns is able to determine when one pattern is a special case of another:

   Internal`ComparePatterns[_h, _]
   (* -> "Specific" *)
   

   However, this situation is often misdiagnosed with equivalent patterns, which will instead be identified as special cases of each other:

   Internal`ComparePatterns[__, (_) ..]
   (* -> "Specific" *)
   
   Internal`ComparePatterns[(_) .., __]
   (* -> "Specific" *)
   

4. Disjointness

   What is more reliably stated is when one pattern is exclusive of another, i.e. there are no expressions that could be matched by both:

   Internal`ComparePatterns[_a, _b]
   (* -> "Disjoint" *)
   

5. Incomparability

   Finally, we have the situation whereby the patterns are either unrelated, or Internal`ComparePatterns simply does not know how to interpret their relationship:

   Internal`ComparePatterns[a | b, b | c]
   (* -> "Incomparable" *)
   

   Notably, it seems to be the case that Internal`ComparePatterns works entirely inside the pattern matcher, so that conditional patterns (which need to invoke the main evaluation loop), if not identical, are generally incomparable (by this mechanism):

   Internal`ComparePatterns[_ /; True, _ /; Sequence[True]]
   (* -> "Incomparable" *)
   
   Internal`ComparePatterns[_?(True &), _ /; True]
   (* -> "Incomparable" *)
   

Now let's try it on the examples:

Internal`ComparePatterns[a | b, b | a]           (* -> "Equivalent" -- correct *)
Internal`ComparePatterns[a | b, c | b | a]       (* -> "Specific" -- correct *)
Internal`ComparePatterns[a | b | c, b | a]       (* -> "Incomparable" -- correct *)
Internal`ComparePatterns[a | b | (c : b), b | a] (* -> "Incomparable" -- incorrect, but: *)
Internal`ComparePatterns[a | (c : b), b | a]     (* -> "Equivalent" -- correct *)
Internal`ComparePatterns[{a ..}, {a ..}]         (* -> "Identical" -- correct *)
Internal`ComparePatterns[{a ..}, {a ...}]        (* -> "Specific" -- correct *)
Internal`ComparePatterns[{a ...}, {a ..}]        (* -> "Incomparable" -- correct *)

So, Internal`ComparePatterns fails only in one case, and its answer is still technically correct as it is the result of the inability of the function to see the relationship between these patterns (Internal`ComparePatterns[a | b | b, b | a] gives "Specific" rather than "Equivalent") and not a statement about the expressions they will match.

I should finish by saying that I wasn't able to find any concrete examples of where Internal`ComparePatterns is actually used in Mathematica, which should give one pause considering its occasional mistakes. However, it may be that I didn't find it because I wasn't trying hard enough, rather than because it isn't used anywhere. Here is code for a hook that can be installed (using $Pre = withHookedComparePatterns) during normal usage. If you're lucky enough to stumble on a function that uses Internal`ComparePatterns, the call stack and the call itself will be printed out at that point, which will help to identify what its use case is, if any. Anyone finding any examples is welcome to edit this answer to include them below (marking as Community Wiki at the same time, if desired).

ClearAll[withHookedComparePatterns];
SetAttributes[withHookedComparePatterns, HoldAll];
Begin["System`Private`"];
withHookedComparePatterns[expr_] :=
  Internal`InheritedBlock[{Internal`ComparePatterns},
   Unprotect[Internal`ComparePatterns];
   cp : Internal`ComparePatterns[___] /;
     StackInhibit[Print[{Stack[], HoldForm[cp]}]; True] := cp;
   Protect[Internal`ComparePatterns];
   StackBegin[expr]
  ];
End[];