# How does levelspec work inside Position?

Please, can you explain the following feature of levelspec inside Position ?

This code

test=Range;
Position[test,x_/;x>2]


as expected, gives

{{3},{4},{5}}


Similarly, this other one

test={"a","b","c"};
Position[test,x_/;StringFreeQ[x,"a"]]


should return

{{2},{3}}


and it does, but, further, prints a message:

StringFreeQ::strse: "String or list of strings expected at position 1 in StringFreeQ[List,"a"]


My first conjecture was: "Well, Position firstly checks test as whole (and here comes the message, because the head is List) then, in turn, each subexpression" .

But it seems that the explanation fails: the following instructions behave exactly as described above:

Position[test,x_/;StringFreeQ[x,"a"],1]
Position[test,x_/;StringFreeQ[x,"a"],{1}]
Position[test,x_/;StringFreeQ[x,"a"],2]


moreover

Position[test,x_/;StringFreeQ[x,"a"],{2}]


returns

{} .

I will be greatly grateful for any hints about all that.

• test = {"a", "b", "c"}; Position[test, x_ /; StringFreeQ[x, "a"], Heads -> False] – Dr. belisarius Oct 5 '15 at 20:26
• "With the default option setting Heads->True, Position includes heads of expressions and their parts. " – Sjoerd C. de Vries Oct 5 '15 at 21:06
• Thanks for your replies ! I feel like I'm still missing the main point : at a foundamental level, 'Heads->False' makes Position "skips" the heads taking into account their position ( as seen using TreeForm ) or a by means of subtler algorithm ? In the first case, why 'Position[test, x_ /; StringFreeQ[x, "a"], {2}]' gives' {}' ? – mitochondrial Oct 6 '15 at 18:39
• @mitochondrial because there is nothing at level 2, your expression only has elements at level 0 and 1. – LLlAMnYP Nov 3 '15 at 8:11

## Depth-first searching

Let's test stuff out with a more complex example:

t = {"a", "b", "c", {"d", {"deep"}}, "e"};
Position[t, x_ /; (Print[x]; StringFreeQ[x, "a"])]


List
a
b
c
List
d
List
deep
{deep}
{d,{deep}}
e
{a,b,c,{d,{deep}},e}

{{2}, {3}, {4, 1}, {4, 2, 1}, {5}}


I omit the error messages, but they occur after each List. As per the docs, Position does a depth-first search. Thus, it checks from left to right, and as soon as it encounters an element in the list with "depth" it stalls on it and checks it down to the bottom. The sequence of positions checked is thus:

{{0}, {1}, {2}, {3}, {4, 0}, {4, 1}, {4, 2, 0}, {4, 2, 1}, {4, 2}, {4}, {5}, {}}


In other words, first the sub-parts of an expression are checked, then the expression as a whole is checked, as can be seen by the sequence {4, 0}, {4, 1}, {4, 2, 0}, {4, 2, 1}, {4, 2}, {4} where {4} comes last. The very last one to be checked is the entire expression t, which is designated by {} (again, see docs).

Now your first conjecture was that Position checks test (or t in my example) as a whole first, but that's not true. And it also wouldn't yield an error, as your test was indeed a list of strings, as the error message asks for. Indeed, as the output above shows, it checks the head of the expression first, which is also located at level 1, specifically at position 0. Because {"a", "b", "c"} is nothing more than List["a", "b", "c"], Position simply goes through List, "a", "b", "c", and then finally List["a", "b", "c"]. For example:

Position[a[b, c, d], x_ /; (Print[x]; True)]


a
b
c
d
a[b,c,d]

{{0}, {1}, {2}, {3}, {}}


## Level specification

Now that the order of traversing through the list is cleared up, the levelspec behavior should be easy enough. In your case

Position[test,x_/;StringFreeQ[x,"a"],1]
Position[test,x_/;StringFreeQ[x,"a"],2]


are equivalent, because you only have one level in the expression. It is not equivalent to

Position[test,x_/;StringFreeQ[x,"a"]]


because this checks also level 0, while the above two expression do not. So compare the output at the top to the output of

Position[t, x_ /; (Print[x]; True), 1]


List
a
b
c
{d,{deep}}
e

{{0}, {1}, {2}, {3}, {4}, {5}}


The entire expression is now absent, and so are the deeper levels of the 4th element.

Position[t, x_ /; (Print[x]; True), 2]


List
a
b
c
List
d
{deep}
{d,{deep}}
e

{{0}, {1}, {2}, {3}, {4, 0}, {4, 1}, {4, 2}, {4}, {5}}


Now only "deep" is absent (as is the entire expression), but note the {"deep"} is present.

Finally, these three commands give:

Position[t, x_ /; (Print[x]; True), {2}]
Position[t, x_ /; (Print[x]; True), {3}]
Position[t, x_ /; (Print[x]; True), {4}]


List
d
{deep}

{{4, 0}, {4, 1}, {4, 2}}


List
deep

{{4, 2, 0}, {4, 2, 1}}


'

 {}


Note how nothing is printed for the last command: no elements at level 4 means nothing is checked at all.

• Excellent answer! – Thies Heidecke Jul 18 '17 at 18:14