# How to match expressions with a repeating pattern

The expression I want to match obey a simple pattern that repeats it self a number of times.

f[a]@f[b]@f[c]@...@f[X]


How would you match all expressions of this form?

-
Strongly related: stackoverflow.com/q/5958128/618728 – Mr.Wizard Sep 24 '12 at 19:23
Thanks for the Accept. – Mr.Wizard Sep 27 '12 at 6:12

### New method

SetAttributes[test, HoldAll]
test[f[_] | f[_]@_?test] = True;
test[_] = False;

f[a]@f[b]@f[c] // test


True

### Old methods for reference

If subexpression evaluation is not a concern:

test = MatchQ[#, f[_] | f[_]@_?#0] &;

f[a]@f[b]@f[c] // test


True

To address Leonid's critique that this has evaluation leaks one might instead write:

p1 = HoldPattern @ f[_];
test = Function[, MatchQ[Unevaluated@#, p1 | p1@_?#0], HoldFirst];


Now it works here too:

f[b] = "FAIL!";

f[a]@f[b]@f[c] // test


True

-
Well, I guess it works:). +1, I wanted to write something like this but you were first here. We should assume however that the expression won't evaluate, since your test function contains evaluation leaks. – Leonid Shifrin Sep 24 '12 at 19:40

Function[Null,
Switch[Unevaluated@#,
HoldPattern[f[_]], True,
HoldPattern[f[_][_]], #0 @@ Unevaluated[#],
_, False],
HoldAll]


which is basically the same idea, but may be easier (or harder) to comprehend than his solution, depending on how you think. The pattern-matching is done as

MatchQ[f[a]@ f[b]@f[c],
_?(Function[Null,
Switch[Unevaluated@#,
HoldPattern[f[_]], True,
HoldPattern[f[_][_]], #0 @@ Unevaluated[#],
_, False],
HoldAll])]

(* True *)


Note that, if evaluation is not an issue, the above code can be simplified:

MatchQ[f[a]@f[b]@f[c], _?(Switch[#, f[_], True, f[_][_], #0 @@ #, _, False] &)]

-
@Mr.Wizard I think I fixed that one while you were busy typing the comment. But there is another one - I need HoldPattern too. – Leonid Shifrin Sep 24 '12 at 20:02
Leonid, I added a new method to my answer that I think is cleaner; please tell me if it works or if I'm fooling myself. – Mr.Wizard Sep 24 '12 at 20:13
@Mr.Wizard I like your new method, and I don't see any obvious problem with it. – Leonid Shifrin Sep 24 '12 at 20:19
btw Leonid, I remember bugging you a while ago re: converting an answer of yours to a blogpost (was it a java related one? I don't remember...). Would you happen to have some time to finish it so that we can push one out? If not, no worries :) – R. M. Sep 24 '12 at 22:07
@R.M I do keep that in mind. Alas, this week is out of the question, I have tons of stuff to do. And so was the last one. I only get short breaks enough to answer questions such as this, but not enough for a blog post. This should be different in a week or something, then I'll try to finish and post it. It won't be Java-related though, I was thinking about the Bessel functions. B.t.w., a few days ago I have finally got a chance to reproduce the bug in the Java reloader that you and a few other folks reported. I fixed it and will soon update the code in my answer where I posted the reloader. – Leonid Shifrin Sep 24 '12 at 22:20

Leonid and Mr.Wizard have given you good answers. Here's a highly unconventional solution that works when f has no *Values (i.e., it is undefined):

test[expr_, patt_] := NestWhile[First, expr, MatchQ[Head[#], patt] &] ~MatchQ~ patt


Some examples:

test[f[a]@f[b]@f[c], f[_]]
(* True *)

test[f[a]@g[b]@f[c], f[_]]
(* False *)

test[f[a]@f[b]@f[c, d], f[_]]
(* False *)

-
Unconventional indeed. I like the idea, +1. – Leonid Shifrin Sep 24 '12 at 20:42
I'm assuming then that if f were in a Block then this would work? – rcollyer Sep 24 '12 at 21:02
@rcollyer Block might not be enough, if some other symbols involved in the expression have UpValues against f. – Leonid Shifrin Sep 24 '12 at 21:27

We can match expressions of the desired form thus:

$expr = f[a]@f[b]@f[c]@f[d]; MatchQ[$expr //. f[_]@r_ :> r, _f]

(* True *)

$expr2 = f[a]@f[b]@g[f[c]@f[z]]@f[d]; MatchQ[$expr2 //. f[_]@r_ :> r, _f]

(* False *)


This assumes that the transformation rule f[_]@r_ :> r does not change an inert expression into one that evaluates. Given that "hold" attributes cannot be given to compound heads, this is a pretty safe bet. However, the astute reader will note that the use of ReplaceRepeated will operate on subexpressions, not just the surface structure (e.g. f[c]@f[z] in $expr2). This opens up more theoretical possibilities for unexpected evaluation. And it also means that our CPU will heat up more than strictly necessary. I offer this more complex variant for the ecologically sensitive: MatchQ[$expr //. {x : _f :> x, Except[f[_]@_] -> Null, _@r_ :> r}, _f]

(* True *)


This variation ensures that each iteration operates only upon the surface structure of the expression. And should some perverse clever situation arise where evaluation manages to leak from this set-up, we can elaborate even further by sprinkling Hold liberally throughout:

MatchQ[
Hold@# &@ \$expr //.
{ x : Hold[_f] :> x
, Except[Hold[f[_]@_]] -> Null
, Hold[_@r_] :> Hold[r]
}
, Hold[_f]
]

(* True *)

-
I initially wasn't going to vote for this answer because I rejected a //. method myself (for the reasons you describe) while formulating mine, but your detailed analysis is surely of interest. +1 – Mr.Wizard Sep 24 '12 at 23:46
All the same people gathered around this question as the previous one. If someone would need to gather us for something, it is not hard to come up with a bait question like this. +1. – Leonid Shifrin Sep 25 '12 at 0:04
@Mr.Wizard Thanks for the +1. I thought twice about writing this response for those reasons. But I finally decided that //. was a legitimate strategy -- even without all of the elaborations as I suspect that neither extra replacements nor evaluation leakage are likely to cause problems in practice. I suppose it depends whether the requirement arises in library code or in a specific application with inputs of known form. I'd say I'm fond of YAGNI, but I guess this post testifies against me :) – WReach Sep 25 '12 at 0:06
@Leonid True. We're missing Sasha however. He still visits but doesn't post much these days; too busy with mathematics.SE I suppose. – Mr.Wizard Sep 25 '12 at 0:13
@Mr.Wizard Yes...Sasha betrayed us for maths. – Leonid Shifrin Sep 25 '12 at 0:22