# The most external subexpression with given pattern

Suppose there is a deep expression with several instances of some _f. I want to get the most external case of _f from it (I also want to get the first instance of one, in a traditional Mathematica's sense of “the first”).

Initially I tried Cases[expr, _f, Infinity, 1] but it actually turned out to be the internal subexpression. I probably should have expected that but was nevertheless a bit surprised. (Not that I'm saying the principle of the least astonishment was broken, though.)

What is the proper way to get the external _f? (Sure, it could be more general than Blank@something but it probably doesn't matter.)

An example:

In[1]:= deepExpression =
"Just a filler"@"Just a filler, too",
"This should be the first part of the result",
"Head of interest"@"But it is too deep"],
"Head of interest"@"But it is too late"];


The first naive attempt:

In[2]:= First@Cases[deepExpression, Blank@"Head of interest", Infinity, 1]
Out[2]= "Head of interest"["But it is too deep"]


Another unsuccessfull one:

In[3]:= Last@Cases[deepExpression, Blank@"Head of interest", Infinity]
Out[3]= "Head of interest"["But it is too late"]


Then I tried coordinate approach (minimizing sum of indices in Position):

In[4]:= minimumWRTTotal =
allPositions \[Function]
Select[allPositions
, And @@ ((arbitraryPosition \[Function]
Total@# <= Total@arbitraryPosition) /@ allPositions) &];

In[5]:= findExternalByPosition[expr_, pattern_] :=
Part[expr
, ## & @@
First @ minimumWRTTotal @
Position[expr, pattern, Infinity]]

In[6]:= findExternalByPosition[deepExpression, Blank@"Head of interest"]
Out[6]= "Head of interest"["This should be the first part of the result",
"Head of interest"["But it is too deep"]]


And I'm still not sure if it actually does what I need (a usual case for everything that is coordinate-based).

Yet another approach:

In[7]:= FirstOrSkip = Quiet[First@# /. _First -> (## &[])] &;

In[8]:= parseForExternal[a_?AtomQ, pattern_] :=
Switch[a, pattern, a, _, ## &[]]

In[9]:= parseForExternal[notAnAtom_, pattern_] :=
Switch[notAnAtom
, pattern , notAnAtom
,    _    , FirstOrSkip[parseForExternal[#, pattern] & /@ notAnAtom]]

In[10]:= parseForExternal[deepExpression, Blank@"Head of interest"]
Out[10]= "Head of interest"["This should be the first part of the result",
"Head of interest"["But it is too deep"]]


I'll probably use the last one but is there any better way? I feel there must be a very simple built-in way to do it that I overlook. parseForExternal in its present form probably does some unnecessary job with long expressions that have positives in the beginning, and I'd prefer to avoid that. In case it's true, and there's also no built-in algorithm, how do I make parseForExternal more efficient?

Also, if anybody can clearly see if minimizing elements from Position w.r.t. to Total actually does the job, please comment on that.

-
Using 1 or {1} for the levelspec instead of Infinity (i.e., Cases[deepExpression, Blank@"Head of interest", {1}, 1]) gives the expected result? – kglr May 14 '14 at 22:53
@kguler No! Counterexample: Cases["Even more external head"@deepExpression, Blank@"Head of interest", {1}, 1] – Akater May 14 '14 at 23:00

I think you just need this:

firstExternal[head_, expr_] := Module[{tag}, expr /. p_head :> Return[p, Module]]


or perhaps, even much more elegantly:

firstExternal[head_, expr_] := expr /. p_head :> Return[p, ReplaceAll]


For example:

firstExternal["Head of interest", deepExpression]

(* "Head of interest"["This should be the first part of the result", "Head of interest"["But it is too deep"]] *)


The reason why Cases doesn't cut it is that it is depth-first, unlike RelaceAll.

-
@Kuba For reasons I won't elaborate on, but related to the fact that I work on development version now. In principle, you shouldn't have to use it. – Leonid Shifrin May 14 '14 at 23:15
Yes, that's wonderful. :-) The impact of second subexpression for Return is not documented, yet your solution doesn't work without it. A guess: Return[x, f] ties this Return to the innermost f construct? – Akater May 14 '14 at 23:25
@Akater Why guessing if someone very smart already did all the guessing for us :) ? – Leonid Shifrin May 14 '14 at 23:26
@Akater But Return is not irreplaceable here - you could use Catch and Throw instead - which would work too, just less elegantly. – Leonid Shifrin May 14 '14 at 23:29
@Akater Have a look at my edit, for the ultimate solution :). – Leonid Shifrin May 14 '14 at 23:31

Not very neat but it seems it works:

f[x : Blank@"Head of interest"] := Throw[x];

Catch @ Do[Scan[f, #, i], {i, Depth@#}] & @ deepExpression

"Head of interest"["This should be the first part of the result",
"Head of interest"["But it is too deep"]]

-