# Position of a pattern-matched part of an expression

What you have

1. A pattern, with certain part of it labeled

As an example — Label: wally

pattern = h : HoldPattern@f[x, __, 3[5], wally_, y]

2. An expression that matches a pattern such as:

expr = f[x, 9, v, h[v], 3[5], v, y]


What I want

The position of the part of the expression expr that matched the label wally.

In the above example, that would be

gimmeWhattaWanna[expr, pattern, wally]
(* {{6}} *)


Note

If the labeled pattern is a sequence such as wally__, either finding the position of the first, or the first and last, are acceptable. If the labeled pattern is repeated such as in f[wally_, 2, wally_], then a list of the positions seems the most natural solution. However, a solution that limits itself to non-repeated labels, or even non-sequence ones is useful.

-
Probably not possible in all generality. For your example you could just do pattern = h : HoldPattern@f[x, a__, 3[5], wally_, y]; expr /. pattern :> {Length[{a}] + 3} – Rolf Mertig Feb 4 '13 at 19:47
@RolfMertig I understood the question to be: 1) You have an unknown pattern that is known to match the expression. 2) You have a named label in the pattern that matches a part in the expression. How do you find the position of the part matching the label in the expression. I didn't think modifying the pattern was allowed... – R. M. Feb 4 '13 at 19:52
@rm-rf sure. but I claim that with __ you won't get a handle on the position of the match. – Rolf Mertig Feb 4 '13 at 19:54
also, this why I put it as a comment. this is no answer obviously. – Rolf Mertig Feb 4 '13 at 19:54
Duplicate stackoverflow.com/q/8479058/353410 – Dr. belisarius Feb 4 '13 at 20:23

You really hit the weak spot of the pattern-matcher, it seems - there are no pointers in Mathematica and so expressions don't "know" their parent expressions. I will offer something pretty ugly and also inefficient, which seems to work however. Here is the implementation:

ClearAll[unique];
unique[tag_] := Sow[Unique[], tag];

ClearAll[constructPattern];
constructPattern[pattern_, name_, tag_, sowTag_] :=
Alternatives @@
Map[
ReplacePart[pattern, # -> tag] &,
Position[pattern, Verbatim[Pattern][name, _]]
] /. Verbatim[Pattern][name, _] -> name /.
Verbatim[Pattern][s_Symbol, rest__] :>
Pattern[Evaluate[unique[sowTag]], rest];


and the main function:

ClearAll[getPositions];
getPositions[expr_, pattern_, name_] :=
Module[{tag, positions, parts, sowTag, positionsInMatched, syms, lp = pattern},
positions = Position[expr, pattern];
parts = Extract[expr, positions];
{positionsInMatched, syms} =
Reap[
With[{tagged = constructPattern[pattern, name, tag, sowTag]},
Cases[parts,
p : lp :>
Cases[
Position[p, name],
pos_ /; MatchQ[ReplacePart[p, pos -> tag], tagged]
]
]
], _, #2 &];
If[syms =!= {}, Remove @@ First[syms]];
Flatten[Outer[Join, {#1}, #2, 1, 1] & @@@
Transpose[{positions, positionsInMatched}], 2]
];


Now, with

pattern = h : HoldPattern@f[x, __, 3[5], wally_, y]
expr = f[x, 9, v, h[v], 3[5], v, y]


one gets

getPositions[expr,pattern,wally]

(* {{6}}  *)

-
I was working on something ugly and slow that, I'll tell you as soon as I read your answer if its similar. I was hoping you would answer :) – Rojo Feb 4 '13 at 20:56
1:30hs trip starting. I'll look at it when I get home. Thanks again – Rojo Feb 4 '13 at 21:02
@Rojo No problem. I am sure there are better solutions which just did not occur to me. – Leonid Shifrin Feb 4 '13 at 21:03
Back, and tested it. +1. Care to take a look at my solution and tell me if it's totally similar? It doesn't handle repeated patterns or sequences yet. I'll need that so I'll have to work on it later. If that is the case I'll delete and add the fixes to your answer – Rojo Feb 4 '13 at 23:34
To fix something, my code now ended up longer, uglier, and with Sow and Reap. In other words, looking more similar to yours (I know, the devil is in the details) – Rojo Feb 5 '13 at 13:45

This handles repeated patterns but not sequences yet

SetAttributes[{getMatchedPosition, getCandidatePositions,
matchedPositionQ}, HoldFirst];

getMatchedPositions[label_, expr_, pattern_] /; MatchQ[expr, pattern] :=
Select[
getCandidatePositions[label, Unevaluated@expr, Unevaluated@pattern],
matchedPositionQ[label, expr, pattern]]
_getMatchedPositions := \$Failed

getCandidatePositions[label_, expr_, pattern_] :=
Unevaluated[expr] /. pattern :> Hold[label] /.
Hold[lab_] :> Position[Unevaluated@expr, Unevaluated@lab]

Off[RuleDelayed::rhs];
matchedPositionQ[label_, expr_, pattern_][pos_] := Module[{tag, hold},
SetAttributes[hold, HoldAllComplete];
! FreeQ[
Reap[
MatchQ[
ReplacePart[hold@expr, pos~Prepend~1 -> tag],
hold@pattern /. {
i_Verbatim :> i,
HoldPattern@Verbatim[Pattern][label, _] :> tag} //.
{(Condition | PatternTest)[tag, cond_] :> tag} /.
tag :> (_?((Sow[HoldComplete[#], tag]; True) &))], tag],
tag]];
On[RuleDelayed::rhs];


So

pattern = h : HoldPattern@f[x, __, h[wally_ /; wally === v], 3[5], wally_, y];
expr = f[x, 9, v, h[v], 3[5], v, y];

getMatchedPositions[wally, expr, pattern]
(* {{4, 1}, {6}} *)

-
Have to really go to get some sleep now, will come back to it tomorrow. Looks somewhat similar to mine, as you mentioned, but the devil is in the details. Also, your code is more compact than mine. So,+1 for now, and more on this later. – Leonid Shifrin Feb 5 '13 at 0:10
It seems tht our solutions have similar idea behind them, but yours takes care to not evaluate the code (I didn't care since you didn't list it as a prerequisit), and also takes care of conditional patterns etc. Mine however does not assume that expr matches the pattern, but that expr might have subexpressions matching it, so is a bit more general in that respect. In any case, it looks like it's hard to come up with something much better than some variant of tagging / labeling. – Leonid Shifrin Feb 5 '13 at 14:38
Oh, so your code would work when there's a subexpression matching the pattern? The non-leakage wasn't really a prerrequisite. I'm just at a non-leaky stage, which I'll probably abandon as soon as I realise it's too much work – Rojo Feb 5 '13 at 14:44
Yes, it should work, for example with the following expression: expr = {h[g[f[x, 9, v, h[v], 3[5], v, y]], f[x, 9, v, h[v], 3[5], v, y]], f[x, 9, v, h[v], 3[5], v, y]}, and the pattern: pattern = h : HoldPattern@f[x, _, wally_, __, 3[5], wally_, y]. – Leonid Shifrin Feb 5 '13 at 14:50
@Leonid. Nice. I'll try to follow your code when I have time, since I'm not a fluent code reader but it seems interesting. It would be 100% more general (and therefore better) if it only matched the outermost pattern (or n nesting levels) and not all of them. So, getPositions[f[f[3]], f[w_], w] would only find {1}. – Rojo Feb 5 '13 at 15:02

Can't say if my logic is completely sound here, but this might just work. The method is to search for the label and find the positions of its matches:

possibleMatchPositions[expr_, pattern_, locate_] :=
Position[expr,
First@Cases[expr, pattern :> locate, {0,Infinity}, Heads -> True]


Then to find the correct one, a label is inserted at the matched position and the pattern is tested again to see if it returns the label:

validPositionQ[position_, expr_, pattern_, locate_] :=
Module[{tagX},
tagX === First@Cases[ReplacePart[expr, position -> tagX]
,pattern :> locate, {0, Infinity}, Heads -> True]]


The entire process is then:

matchPosition[expr_, pattern_, locate_] :=
Cases[
possibleMatchPositions[expr, pattern, locate],
position_ /; validPositionQ[position, expr, pattern, locate]
]


The method definitely fails if the pattern you are searching for appears multiple places and in cases where it has some specifier (for instance wally_Integer or wally_?somethingQ etc.) that means it won't match the tag. You could avoid this by making a substitution on the desired pattern to be general in the verification step. Also it doesn't fail nicely when no matches are present, but I though it better to concisely show the method rather then include checks on lengths.

-
It seems like we thought alike. What do you mean with @it has some specifier"? – Rojo Feb 5 '13 at 11:40
@Rojo I meant to say that if you use for instance Wally_Integer it will fail because the inserted tag will not match. – jVincent Feb 5 '13 at 11:59
I see. I just tried to fix a related bug that thanks to you I realised I had in my solution. Hopefully it works for repeated patterns now – Rojo Feb 5 '13 at 13:45