# Levels: how do they work?

I cannot understand how Mathematica manages levels, and so it's always a painful try-and-fail to use Flatten. Can someone please give me a very clear definition?

If you feel like giving an example, please tell me how to turn this list

{{a, {a1}}, {b, {b1}}, {c, {c1}}, ...}

into

{{a, a1}, {b, b1}, {c, c1}, ...}

with Flatten, if possible.

-
I discussed levels briefly on my book, here - this might be helpful. –  Leonid Shifrin Dec 2 '12 at 15:07
possible duplicate of Flatten command: matrix as second argument –  rcollyer Dec 2 '12 at 15:09
@rcollyer May be this is not a dupe given the wider context of the initial question. It might be a little open-ended though. –  Leonid Shifrin Dec 2 '12 at 15:10
well, there are lots of questions on stack exchange whose answer is a sort of handbook/definition. Since I couldn't find anything on the Internet, this could be very well a place to put something clear. About the example, I see that it's not possible to do with a simple argument to Flatten, like n or {n} –  Lorenzo Pistone Dec 2 '12 at 15:12

This is by no means a complete analysis of levels. (See Leonid's book for a more thorough presentation.)

You can visualize levels with TreeForm:

x = F[G[a, K[d]], H[b, L[e]], J[c, M[P[f, g]]]];
TreeForm[x]


I avoided nested lists for clarity; also, because the output of Level is itself put into a list.

One must resist the temptation to think of levels as the vertical height of vertices on a TreeForm display. A single Level will often cut a vertical swath out of the TreeForm, as the following shows.

Positive Levels

Here's a diagram of levels corresponding to non-negative integers. When the parameter in braces is positive, the results will always begin at the same depth in the tree; however, the end depth (where a leaf terminates a branch) depends on the depth of the branch, not the (greatest) depth of the tree.

Notice that level 0 contains the head, F as well as all of the arguments inside it. Level 5 contains nothing; there is no level 5.

Grid@Table[{"level ", k, "  ", Level[x, {k}], "\n"}, {k, 0, 5}]


Negative Levels

Here counting begins from the bottom of the tree. The "bottom" lies at various depths, as the following example shows. Level -1 holds the leaves of the tree.

Grid@Table[{"level ", k, "  ", Level[x, {-k}], "\n"}, {k, 1, 5}]


Raul Nahrain suggested drawing the tree itself "from the bottom of the pane to the top". Mathematica will not display TreeForm this way; you'll need to hand edit it. But what you get is clearer, provided that you realize that we are using a non-standard display of TreeForm.

-
Great visuals! Like it. –  Lou Dec 2 '12 at 19:03
Great answer, David! Big +1. –  Leonid Shifrin Dec 2 '12 at 20:01

To me, the easiest way of thinking about (positive) levels is to ask the question "how many indices are required to specify the location of an object?".

For example, two indices are required to specify the elements in a matrix. For the following two examples,

example1 = {{a, {a1}}, {b, {b1}}, {c, {c1}}};
example2 = {{a, {a1, a2}}, {b, {b1, b2}}, {c, {c1, c2}}};


three indices are required to specify the (positive) location of a1.

example1[[1,2,1]]


a1

Map acts at a specified level and Apply replaces the head at a specified level. One trick to working out what function to apply at which level is to use an arbitrary function, e.g.

Map[g,example1]


{g[{a, {a1}}], g[{b, {b1}}], g[{c, {c1}}]}

Apply[g,example2,{2}]


{{a, g[a1, a2]}, {b, g[b1, b2]}, {c, g[c1, c2]}}

to see where the function will be applied, and what it needs to do.

So, for these examples, with uniform structure, we can use Map and Flatten or Apply and Sequence:

Flatten /@ example1


{{a, a1}, {b, b1}, {c, c1}}

Apply[Sequence,example2,{2}]


{{a, a1, a2}, {b, b1, b2}, {c, c1, c2}}

-

An alternative

list = {{a, {a1}}, {b, {b1}}, {c, {c1}}};
{#[[All, 1]], #[[All, 2, 1]]} &@list // Transpose
Map[{#[[1]], #[[2, 1]]} &, list]

-
...two alternatives? –  geordie Dec 4 '12 at 23:33
Er, my English is poor. –  chyaong Dec 5 '12 at 3:58

David Carraher's answer is quite nice, but I think to really make sense of negative levels you have to draw the tree in a slightly different way, starting from the leaves upwards.

To be clear, the $i$th level consists not just of the heads here (e.g. K, L, and P at level -2) but of the entire subexpressions that they are the heads of (K[d], L[e], and P[f,g]).

-
This is the analysis I cautioned about. G is not at level 1, as I understand it. However, G[a, K[d]] is at level 1. –  David Carraher Dec 3 '12 at 3:15
@David: Well, I haven't mentioned how to interpret the diagram yet. :) It's safe to say that level $i$ consists of all the subtrees which are rooted at the heads labeled $i$ in this diagram, isn't it? –  Rahul Narain Dec 3 '12 at 6:22
I find your display of negative levels useful. Your interpretation can become even clearer if you place frames around the numbers, showing which levels are embedded in which. –  David Carraher Jan 1 at 15:32
I drew another picture of negative levels according to your suggestion. Thanks. –  David Carraher Jan 1 at 16:43

As an alternative, I always felt that replacement rules were quite clear in what they are doing. For your problem:

{{a, {a1}}, {b, {b1}}, {c, {c1}}} /. {a_, {a1_}} -> {a, a1}

-
very interesting. –  Lorenzo Pistone Dec 3 '12 at 0:24

For situations simular to those illustrated in your example, I wouldn't use Flatten. Rather, I would use Position and FlattenAt. This pair of functions will not only handle your example but also much more complicated ones. It is easy to use because Position finds the right level expresion for you.

Let's look at two examples:

example1 = {{a, {a1}}, {b, {b1}}, {c, {c1}}};

Position[example1, {_}]

(* ==>{{1, 2}, {2, 2}, {3, 2}} *)


Now we know where to apply FlattenAt

FlattenAt[example1, {{1, 2}, {2, 2}, {3, 2}}]

(* ==> {{a, a1}, {b, b1}, {c, c1}} *)


Of course, in everyday situations, we would compose Position and FlattenAt:

example2 = {{a, {a1, a2}}, {b, {b1, b2}}, {c, {c1, c2}}};
FlattenAt[example2, Position[example2, {_, _}]]

(* ==>{a, a1, a2, b, b1, b2, c, c1, c2} *)

-
+1. The documentation does not connect Position and FlattenAt at all. And the documentation page for FlattenAt is very scanty. –  Alexey Popkov Aug 3 '13 at 13:39
Flatten/@list1


{{a, a1}, {b, b1}, {c, c1}}

Will also work by flattening each element of your list at the top level.

-

The most straight forward way I can think of at the moment is to use Flatten together with Partition.

list1 = {{a, {a1}}, {b, {b1}}, {c, {c1}}};


First remove all inner braces with Flatten

Flatten@list1


gives you

 {a, a1, b, b1, c, c1}


and now you can rearrange the list in any way you want using Partition

Partition[Flatten@list1, 2]


which yields:

{{a, a1}, {b, b1}, {c, c1}}

-