# replacement rules from a pattern and a matching expression

(This seems to be a very basic necessity in a language having pattern-matching capabilities such as Mathematica, yet I struggled for many hours to find a common solution to this problem.)

Suppose there is a pattern with some of its sub-elements named, and there is an expression that matches it. How do I generate a list of replacement rules that maps sub-element names into their values in the matching expression? E.g.,

patt=f_[_, s_, x___];
expr=ab[c, d, e, f];
mkMatchRules[expr,patt]
>> {f -> ab, s -> d, x -> Sequence[e, f]}


I have written a solution to this,

collectAllPattVars[patt_] := Union[Map[Part[#, 1] &,
Cases[patt, _Pattern, {0, Infinity}, Heads -> True]]];
mkMatchRules[expr_, patt_] := Module[
{pattVars = collectAllPattVars[patt], mkRhs},
mkRhs = Block[{$}, ReleaseHold[Hold[patt :>$] /. $-> With[{$ = Map[List, pattVars]}, $]]]; If[MatchQ[expr, patt], MapThread[Rule[#1, If[Length[#2] == 1, #2[[1]], Sequence @@ #2]] &, {pattVars, Replace[expr, mkRhs]}],$Failed]];


which produces the result in the example above However, I hope somebody knows a more elegant way to do this.

-
Interesting question. +1 :-) –  Mr.Wizard Jan 12 '13 at 7:23
Also, welcome to Mathematica.SE, and thank you for properly formatting your question. –  Mr.Wizard Jan 12 '13 at 7:42

I like this question. If you can be assured that none of the pattern names will have values assigned I believe this can be done rather simply. If however any of (f, s, x) in the example have assignments additional guards will be required.

## The simple case

patt = f_[_, s_, x___];
expr = ab[c, d, e, f];

f1 = # -> (expr /. patt -> #) &;

Cases[patt, Verbatim[Pattern][name_, _] :> f1[name], -1, Heads -> True]

{f -> ab, s -> d, x -> Sequence[e, f]}


Or more concisely, if further assuming that the subexpressions will be evaluated:

Reap[patt /. Pattern -> (Sow @ f1 @ # &)][[2, 1]]

{f -> ab, s -> d, x -> Sequence[e, f]}


## More robustly

Now as a complete function and with proper holding of pattern names:

x = "Failed!"; (* This should not appear in the result! *)

mkMatchRules[expr_, patt_] /; MatchQ[expr, patt] :=
Module[{p = patt},
Cases[patt,
Verbatim[Pattern][name_, _] :>
(HoldForm[name] -> (expr /. p :> name)),
]
]

mkMatchRules[ ab[c, d, e, f], f_[_, s_, x___] ]

{f -> ab, s -> d, x -> Sequence[e, f]}


Note that in the output the LHS sybols are wrapped in HoldForm. Other options are Defer or converting to strings.

I originally used a rather convoluted method featuring Function to avoid a certain problem wherein pattern names are automatically changed within scoping constructs. This is done to avoid collisions but it prevents exactly the behavior I need. I revised the code to use another method that is hopefully more transparent and also cleaner. It works by preventing the direct substitution (by SetDelayed) of the pattern into the inner replacement using a localized proxy symbol p.

-
Great! Thank you so much! Is there a reason you use Function[Null,<body>,...] construction? to force the parameter variable to be temporary? –  Sergey Jan 12 '13 at 8:38
@Sergey Yes, there is. I needed it to avoid automatic renaming within nested scoping constructs that breaks this otherwise. I shall see if I can find a prior question that addresses this. –  Mr.Wizard Jan 12 '13 at 8:42
@Sergey I couldn't find the particular question I was looking for (I may need to ask Leonid or Rojo) but here is an example: Function[name, ab[c, d, e, f] /. f_[_, s_, x___] :> name, HoldAll][x] // Trace -- look at the output of the Trace and you will see ab[c, d, e, f] /. f$_[_, s$_, x$___] :> x where x has become x$ etc. This is Mathematica trying to respect/protect the nested scoping constructs (both Function and RuleDelayed are scoping constructs, along with the more known With, Block, Module). Sometimes however this is exactly what you don't want. (continued) –  Mr.Wizard Jan 12 '13 at 8:58
Function as used with Slot rather than named parameters does not cause this automatic renaming. In this case I needed a Hold attribute as well and I had to use an undocumented form: Function[Null, (* body with #, #2 *), attribute] which I learned from Leonid Shifrin. –  Mr.Wizard Jan 12 '13 at 9:01
@Sergey I updated my answer to eliminate this rather baroque and undocumented construct. I believe it is now both cleaner and easier to understand. –  Mr.Wizard Jan 12 '13 at 14:34