Preorder traversal visits a node before descending into its children. This depth-first ordering is useful when a transformation must inspect or change a branch before nested values are processed. section 8.4 section 8.4.2
A preorder traversal has a simple contract:
- Visit every nested item, including collections and non-collection values. section 8.4.2
- Apply a one-argument function before entering an inner collection. section 8.4.2
- Return a structure whose type generally follows the input, depending on transformations performed by the function. section 8.4.2
- Accept any form, including nil, while recognizing that unusual collection implementations can raise UnsupportedOperationException. section 8.4.2
Observe the visitation order
(require '[clojure.walk :refer [prewalk]]) (prewalk #(do (println %) %) [1 [2 [3]]]) ;; [1 [2 [3]]] ;; 1 ;; [2 [3]] ;; 2 ;; [3] ;; 3 ;; [1 [2 [3]]] The outer collection is visited first, followed by each nested item in depth-first order. The final value remains structurally unchanged because the function returns each item unchanged. section 8.4.1 section 8.4.2
Alter traversal before descending
Preorder processing can prevent work in a nested branch. For example, a function can recognize a node of type "pipeline" and change its contents before nested actions are reached. This differs from postorder traversal, which processes children before their parent and is better suited to combining already-processed results. section 8.4.2 section 8.4.1
Figure 8.11. Depth-first, pre-order traversal of a simple tree. The continuous line shows the traversal path, while the little cameras represent the call to the visiting function.
The traversal diagram makes the depth-first, parent-before-children order visible. section 8.4.1
