3
$\begingroup$

Consider this example:

Level[a + f[x, y^n], {0, Infinity}]

(*{a, x, y, n, y^n, f[x, y^n], a + f[x, y^n]}*)

Why the output is sorted in this way. why not following their levels? I was expecting to get:

(*{a + f[x, y^n], a, f[x, y^n], x, y^n, y, n}*)
$\endgroup$
  • 7
    $\begingroup$ Details&Options: "Level traverses expressions in depth-first order, so that the subexpressions in the final list are ordered lexicographically by their indices.". So in your case use: Flatten[Table[Level[#, {i}], {i, 0, Depth[#]}]] & $\endgroup$ – Kuba Jul 28 '14 at 8:54
  • $\begingroup$ @Kuba can you let me know how to get the indices of all Level output so that I can understand waht you mean by ordered lexicographically by their indices. $\endgroup$ – Algohi Jul 28 '14 at 10:18
9
$\begingroup$

As Kuba comments Level follows the standard expression traversal order:

Level traverses expressions in depth-first order, so that the subexpressions in the final list are ordered lexicographically by their indices.

This is actually a depth-first postorder traversal.
It is the normal order in which expressions are evaluated in Mathematica:

echo[x_] := (Print@x; x)

expr = a + f[x, y^n];

Map[echo, HoldForm @@ {expr}, {1, -1}]

ReleaseHold[%];
echo[echo[a] + echo[f[echo[x], echo[echo[y]^echo[n]]]]]

a
x
y
n
y^n
f[x,y^n]
a+f[x,y^n]

It is used by nearly all System traversal functions, e.g.:

Scan[Print, expr, {0, -1}]  (* same output as above; omitted *)

Cases[expr, _, {0, -1}]

expr ~Extract~ Position[expr, _, {0, -1}, Heads -> False]
{a, x, y, n, y^n, f[x, y^n], a + f[x, y^n]}

{a, x, y, n, y^n, f[x, y^n], a + f[x, y^n]}

A notable exception is ReplaceAll which uses a depth-first preorder traversal. See:

You are interested in a breadth-first traversal; see:

For an understanding of levels as used by Mathematica see the excellent illustrations in answer to:


Solution to implied problem

Although I hope the information above including the linked Q&A's will give you the knowledge to solve the implied problem yourself here is my take on Kuba's code:

expr = a + f[x, y^n];

Array[expr ~Level~ {#} &, Depth @ expr, 0, Join]
{a + f[x, y^n], a, f[x, y^n], x, y^n, y, n}

And a solution using WReach's bf function from the link above:

Reap[Sow ~bf~ expr][[2, 1]]
{a + f[x, y^n], a, f[x, y^n], x, y^n, y, n}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.