wolfram mathematica - Arbitrarily Deep Nested Pattern Matching -

is there way create mathematica pattern matches expressions heads may arbitrarily deep, i.e. f[___][___][___]...?

the suggested solution

there seems no built-in construct pattern-test nested heads automatically. can achieve goal writing function would, given (sub)expression of form f[___]...[___], efficiently determine f (which, slight abuse of terminology, may call symbolic head expression). here code:

clearall[shead]; setattributes[shead, holdallcomplete]; shead[expr_] := scan[return, unevaluated[expr], {-1}, heads -> true]; 

here how can used (i use same set of tests @sasha):

in[105]:= cases[{f[1], g[f[1]], f[1, 2, 3][1], f[1][2][3][4]}, x_ /; shead[x] === f]  out[105]= {f[1], f[1, 2, 3][1], f[1][2][3][4]} 

---

the pattern syntax

if prefer use syntax suggested @sasha, version

clear[headpattern]; headpattern[head_] := _?(function[null, shead[#] === head, holdfirst]);  in[108]:= cases[{f[1], g[f[1]], f[1, 2, 3][1], f[1][2][3][4]}, headpattern[f]]  out[108]= {f[1], f[1, 2, 3][1], f[1][2][3][4]} 

---

further explanations , comments

how works

here hints logic lead solution, , how works. solution concise , efficient if manage leverage of built-in expression-traversal functions. come mind map, scan,cases,mapindexed,position. given need heads, we'd need pass heads->true option. used scan, since 1 easy stop @ point (unlike other mentioned constructs, you'd typically need throw exception stop them "in middle", rather inelegant , induces overhead well) find want. our result first thing scan finds on depth-first expression traversal, expected efficient (it not traverse entire expression).

avoiding evaluation leaks

another comment on evaluation. can see holdallcomplete attribute used in shead, , unevaluated used in body. these important - serve prevent possible evaluation of expressions passed function. may matter in cases this:

in[110]:= m = n = 0; g[x_] := n++; h[x_] := m++; {cases[hold[f[g[1]][h[2]]], x_ /; shead[x] === f :> hold[x], infinity], {m, n}}  out[113]= {{hold[f[g[1]][h[2]]]}, {0, 0}} 

here, see we'd expect - though cases has been traversing entire expression , feeding (sub)parts shead, no evaluation of sub-parts triggered shead. define naive version of shead "leaks evaluation":

sheadeval[expr_] := scan[return, expr, {-1}, heads -> true] 

and now,

in[114]:= {cases[hold[f[g[1]][h[2]]], x_ /; sheadeval[x] === f :> hold[x], infinity], {m, n}}  out[114]= {{hold[f[g[1]][h[2]]]}, {2, 1}} 

the latter behavior unsatisfactory generally. whole code-is-data paradigm, useful in meta - programming, powerful in mathematica because can use rules destructure code. possible (unwanted) evaluation during pattern- matching impair it. whole problem in sub-parts. wrapping hold prevents whole expression evaluation. functions cases , other similar functions code destructuring great because don't evaluate sub-parts when doing structural (syntactic) matching.

comment on symbolic heads

the last comment here (mostly definitions) shead function returns not called symbolic head in mathematica. difference atomic expressions. example, shead[f] returns f, while atomic expressions, true symbolic head should coincide head of expression (symbol in case). have developed symbolichead function behavior here, , 1 can used in place of shead in above, although shead more efficient.