14
$\begingroup$

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?

$\endgroup$
1

4 Answers 4

16
$\begingroup$

New method

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

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

True

This method's advantages are elucidated here:


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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Sep 24, 2012 at 19:40
6
$\begingroup$

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 *)
$\endgroup$
3
  • 1
    $\begingroup$ Unconventional indeed. I like the idea, +1. $\endgroup$ Sep 24, 2012 at 20:42
  • $\begingroup$ I'm assuming then that if f were in a Block then this would work? $\endgroup$
    – rcollyer
    Sep 24, 2012 at 21:02
  • 2
    $\begingroup$ @rcollyer Block might not be enough, if some other symbols involved in the expression have UpValues against f. $\endgroup$ Sep 24, 2012 at 21:27
6
$\begingroup$

@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] &)]
$\endgroup$
5
  • 1
    $\begingroup$ @Mr.Wizard I think I fixed that one while you were busy typing the comment. But there is another one - I need HoldPattern too. $\endgroup$ Sep 24, 2012 at 20:02
  • $\begingroup$ 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. $\endgroup$
    – Mr.Wizard
    Sep 24, 2012 at 20:13
  • $\begingroup$ @Mr.Wizard I like your new method, and I don't see any obvious problem with it. $\endgroup$ Sep 24, 2012 at 20:19
  • $\begingroup$ 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 :) $\endgroup$
    – rm -rf
    Sep 24, 2012 at 22:07
  • $\begingroup$ @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. $\endgroup$ Sep 24, 2012 at 22:20
4
$\begingroup$

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 *)
$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – Mr.Wizard
    Sep 24, 2012 at 23:46
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 25, 2012 at 0:04
  • $\begingroup$ @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 :) $\endgroup$
    – WReach
    Sep 25, 2012 at 0:06
  • 1
    $\begingroup$ @Leonid True. We're missing Sasha however. He still visits but doesn't post much these days; too busy with mathematics.SE I suppose. $\endgroup$
    – Mr.Wizard
    Sep 25, 2012 at 0:13
  • $\begingroup$ @Mr.Wizard Yes...Sasha betrayed us for maths. $\endgroup$ Sep 25, 2012 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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