How to match expressions with a repeating pattern

Question

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?

Answer 1

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

Answer 2

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 *)

Answer 3

@Mr.Wizard already picked the sweetest answer, but here is my version:

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] &)]

Answer 4

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 *)