StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h2>The suggested solution</h2> <p>There seems to be no built-in construct to pattern-test nested heads automatically. We can achieve the goal by writing a function which would, for any given (sub)expression of the form <code>f[___]...[___]</code>, efficiently determine <code>f</code> (which, with a slight abuse of terminology, we may call a symbolic head for the expression). Here is the code:</p> <pre><code>ClearAll[shead]; SetAttributes[shead, HoldAllComplete]; shead[expr_] := Scan[Return, Unevaluated[expr], {-1}, Heads -> True]; </code></pre> <p>Here is how it can be used (I will use the same set of tests as @Sasha):</p> <pre><code>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]} </code></pre> <hr> <h2>The pattern syntax</h2> <p>If you prefer to use the syntax suggested by @Sasha, that version would look like </p> <pre><code>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]} </code></pre> <hr> <h2>Further explanations and comments</h2> <h3>How it works</h3> <p>Here are some hints for the logic that lead to this solution, and how it works. The solution will be most concise and efficient if we manage to leverage some of the built-in expression-traversal functions. Some that come to mind are <code>Map</code>, <code>Scan</code>,<code>Cases</code>,<code>MapIndexed</code>,<code>Position</code>. Given that we need the heads, we'd need to pass the <code>Heads->True</code> option. I used <code>Scan</code>, since this one is easy to stop at any point (unlike other mentioned constructs, for which you'd typically need to throw an exception to stop them "in the middle", which is rather inelegant and induces some overhead as well) as soon as we find what we want. Our result will be the very first thing <code>Scan</code> finds on its depth-first expression traversal, so it is expected to be very efficient (it does not traverse the entire expression). </p> <h3>Avoiding the evaluation leaks</h3> <p>Another comment is on evaluation. You can see that <code>HoldAllComplete</code> attribute is used in <code>shead</code>, and <code>Unevaluated</code> is used in its body. These are very important - they serve to prevent possible evaluation of expressions passed to the function. It may matter in cases like this:</p> <pre><code>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}} </code></pre> <p>Here, we see what we'd expect - even though <code>Cases</code> has been traversing the entire expression and feeding its (sub)parts to <code>shead</code>, no evaluation of sub-parts was triggered by <code>shead</code>. Now we define a naive version of <code>shead</code> which "leaks evaluation":</p> <pre><code>sheadEval[expr_] := Scan[Return, expr, {-1}, Heads -> True] </code></pre> <p>And now,</p> <pre><code>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}} </code></pre> <p>The latter behavior is unsatisfactory generally. The whole code-is-data paradigm, so useful in meta - programming, is very powerful in Mathematica because you can use rules to destructure code. Possible (unwanted) evaluation during the pattern- matching would greatly impair it. The whole problem is in the sub-parts. Wrapping <code>Hold</code> only prevents the whole expression from evaluation. Functions like <code>Cases</code> and other similar functions for code destructuring are so great because they don't evaluate sub-parts when doing the structural (syntactic) matching.</p> <h3>Comment on symbolic heads</h3> <p>The last comment here (mostly about definitions) is that the <code>shead</code> function returns not exactly what is normally called <em>symbolic head</em> in Mathematica. The difference is for atomic expressions. For example, <code>shead[f]</code> returns <code>f</code>, while for atomic expressions, the true symbolic head should coincide with the head of an expression (<code>Symbol</code> in this case). I have developed the <code>symbolicHead</code> function with this behavior <a href="https://stackoverflow.com/questions/4599241/checking-if-a-symbol-is-defined/4621562#4621562">here</a>, and that one can also be successfully used in place of <code>shead</code> in the above, although <code>shead</code> is more efficient.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload