Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
1  
Related topic: I have implemented a special version of Cases which performs the depth-first preorder traversal (perhaps not optimally). In that case, this was important to avoid unpacking during the traversal performed by Cases. –  Leonid Shifrin Aug 8 '12 at 20:52
add comment

5 Answers

up vote 12 down vote accepted

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

share|improve this answer
add comment

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} *)
share|improve this answer
    
Daniel, I see that this is Reaping expressions; unlike Scan this is building an output expression, right? Is Sow simply an example function to "scan" over the expression? What are the tradeoffs of this method compared to recursion? –  Mr.Wizard Aug 9 '12 at 4:39
1  
Yes, it builds an output expression. Sow is not an example function but rather is used in a necessary way. One could easily provide for a function to apply to subexpressions, though I did not. Main advantage is for deeply nested expressions because it will not blow up the program's subroutine stack. –  Daniel Lichtblau Aug 9 '12 at 4:42
add comment

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
*)
share|improve this answer
    
While clever, I wouldn't expect this to maintain the memory conserving performance of Scan, which is a fairly significant component of my question. –  Mr.Wizard Aug 9 '12 at 3:22
add comment

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:

enter image description here

share|improve this answer
add comment

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 ..}] &]
share|improve this answer
    
Looks interesting. I'll take a look at this tonight if I'm not watching Olympics. –  Mr.Wizard Aug 9 '12 at 3:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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