How to perform a depth-first preorder traversal of an expression?

Question

_{Due to confusion of terminology on my part I asked the wrong question before.
Since it has already received other answers I shall not edit it, but instead ask the question I meant to in the first place.}

Mathematica provides functions that perform a depth-first postorder traversal on an expression, including: Map, MapAll, and Scan, and functions that use such a traversal, including: Count, Cases, and Position.

It is quite direct to do this:

expr = {{1, {2, 3}}, {4, 5}};

Scan[Print, expr, {0, -1}]

1

2

3

{2,3}

{1,{2,3}}

4

5

{4,5}

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

It is not as obvious how to do a depth-first preorder scan. (Simply storing then reordering the output is not adequate as it doesn't change the order in which expressions are visited.)

Scan has the property that it does not build an output expression the way that e.g. Map does, and conserves memory.

How can one do a Scan-type operation in depth-first preorder?

Answer 1

I am aware of two general methods.

ReplaceAll

The only general purpose function I am aware of that visits depth-first preorder is ReplaceAll. One can "scan" a given function such as Print as a side-effect by using either PatternTest or Condition, both of which only match if the return is explicitly True.

{{1, {2, 3}}, {4, 5}} /. _?Print -> Null;

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

List is printed because ReplaceAll includes Heads whereas Scan by default does not.

We cannot use the level specification of Span but we can use patterns. For example:

{{1, {2, 3}}, {4, 5}} /. {_, _} ? Print -> Null;

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

Recursive function

This can be done using a recursive function, the purest form of which is:

(Print@#; #0 ~Scan~ #)& @ {{1, {2, 3}}, {4, 5}}

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

Though not as fast as ReplaceAll this method can be extended more generally, for example to accept a level specification:

preorderScan[f_, expr_, {L1_, L2_}] :=
 Module[{rec},
  rec[n_][ex_] := (If[n >= L1, f@ex]; rec[n + 1] ~Scan~ ex);
  rec[n_ /; n > L2][_] = Null;
  rec[0][expr]
 ]

preorderScan[Print, {{1, {2, 3}}, {4, 5}}, {1, 2}]

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

(The function above is an illustration and not intended for reuse. It does not accept all forms of the standard levelspec and it makes no attempt to hold expressions unevaluated. If requested I can post a more lengthy version that does both.)

Answer 2

Here is a version that uses an explicit stack to avoid recursion.

depthFirstPreorder[expr_] := Module[
  {stack = {expr, {}}, el = expr},
  Reap[
    While[stack =!= {},
      {el, stack} = stack;
      Sow[el];
      If[Not[AtomQ[el]],
       Do[stack = {el[[j]], stack}, {j, Length[el], 1, -1}]];
      ];
    ][[2, 1]]
  ]

The customary example:

expr = {{1, {2, 3}}, {4, 5}};

depthFirstPreorder[expr]

(* Out[16]= {{{1, {2, 3}}, {4, 5}}, {1, {2, 3}}, 1, {2, 3}, 2, 3, {4, 
  5}, 4, 5} *)

Answer 3

TreeForm lays the expression tree out in a depth-first preorder traversal fashion. So observing that using VertexLabeling -> Tooltip gives you the expression at that level, we can redefine Tooltip using the Villegas–Gayley trick to print out the expressions as TreeForm lays out the tree. Replace Print with any desired function.

Unprotect@Tooltip;
Tooltip[expr_, label_] /; ! TrueQ[$insideTooltip] :=     	
     Block[{$insideTooltip = True},
      	If[HoldPattern@label =!= 
            HoldPattern@Network`GraphPlotDump`Private`tp$_, Print[label]];
        Tooltip[expr, label]
    ]
Protect[Tooltip];
TreeForm[{{1, {2, 3}}, {4, 5}}, VertexLabeling -> Tooltip]

(*
{{1,{2,3}},{4,5}}
{1,{2,3}}
1
{2,3}
2
3
{4,5}
4
5
*)

Answer 4

Don't know where this should fit. Playing around, this could be a more general approach to the traversal problem. It's probably not best for those traversals that can be done in other ways. Specifically, it has to create the list of indices all at once so it's not memory efficient as Scan

Module[{tag}, 
 generalScan[fun_, expr_, sortingFun_: RandomSample] := 
  Extract[Unevaluated@expr, If[# === {}, fun[expr]]; #, fun] &~Scan~
   sortingFun[
    Reap[MapIndexed[tag, Hold[expr], Infinity, Heads -> True] /. 
       tag[_, {1, in___}] /; Sow[{in}, tag] :> Null, tag][[-1, 1]]]]

This takes a third argument that makes you sort the list of indices to traverse. Defaults to RandomSample (hihihi)

expr = {{{1, {2}}}, {3, {4}}};

(* Random *)
generalScan[Print, expr]

(* Breadth-first *)
generalScan[Print, expr, Sort]

(* Breadth-first right-left *)
generalScan[Print, expr, SortBy[#, Minus] &]

(* Depth-first preorder *)
generalScan[Print, expr, Part[#, Ordering[PadRight[#]]] &]

...

It could be used for other purposes such as traversing a part of a tree. This would only traverse the leftmost branch

generalScan[Print, expr, Cases[#, {1 ..}] &]

Answer 5

My answer to the breadth first scan question (convert your expression to a Graph and do a BreadthFirstScan) can also be used for the depth first scan (if you have MMA v8). You only need to replace BreadthFirstScan by DepthFirstScan. The latter is apparently (and luckily in this case) of the pre-order type.

For the code I refer to the answer referenced above. The visualization of the result is as follows: