Levels: how do they work?

Question

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.

Answer 1

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.

Answer 2

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}

Answer 3

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]).

Answer 4

Flatten/@list1

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

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

Answer 5

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} *)

Answer 6

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}}

Answer 7

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}}

Answer 8

Excellent discussion and great explanations.

The following will retrieve all expressions of a list at all levels sorting by Position. Might help when looking to extract specific elements from an expression. Useful with ragged lists.

So if

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

rfli[x] will be:

rfli[list_] := (coltitles = {"Expression", "Position"}; 
     Grid[
          Prepend[
               SortBy[
                    Union[
                         MapThread[List, {Level[list, {0, Depth[list]}],
                              Map[Position[list, #] &, Level[list, {0, Depth[list]}]]}
                         ]
                    ],
               Last],
          coltitles],
     Frame -> All, Background -> {None, {Lighter[Yellow, .9],
          {White, Lighter[Blend[{Blue, Green}], .8]}}},
     Alignment -> {Left}]);

Further, for the same list x we find that

If interested I can post more code.

Answer 9

An alternative

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