Mathematica provides functions that perform a depth-first postorder traversal, or which use such a traversal, including: Scan
, Count
, Cases
, Replace
, and Position
. It is also the standard evaluation order therefore functions Mapped (Map
, MapAll
) will evaluate in a depth-first-postorder.
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?
Related:
Cases
which performs the depth-first preorder traversal (perhaps not optimally). In that case, this was important to avoid unpacking during the traversal performed byCases
. $\endgroup$