Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

4 Answers 4

up vote 9 down vote accepted

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

share|improve this answer
    
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
add comment

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 *)
share|improve this answer
    
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
1  
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
add comment

@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] &)]
share|improve this answer
1  
@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 :) –  rm -rf 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
show 1 more comment

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 *)
share|improve this answer
1  
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
2  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.