rlm@10
|
1 ; Copyright (c) Rich Hickey. All rights reserved.
|
rlm@10
|
2 ; The use and distribution terms for this software are covered by the
|
rlm@10
|
3 ; Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
|
rlm@10
|
4 ; which can be found in the file epl-v10.html at the root of this distribution.
|
rlm@10
|
5 ; By using this software in any fashion, you are agreeing to be bound by
|
rlm@10
|
6 ; the terms of this license.
|
rlm@10
|
7 ; You must not remove this notice, or any other, from this software.
|
rlm@10
|
8
|
rlm@10
|
9 ;;; walk.clj - generic tree walker with replacement
|
rlm@10
|
10
|
rlm@10
|
11 ;; by Stuart Sierra
|
rlm@10
|
12 ;; December 15, 2008
|
rlm@10
|
13
|
rlm@10
|
14 ;; CHANGE LOG:
|
rlm@10
|
15 ;;
|
rlm@10
|
16 ;; * December 15, 2008: replaced 'walk' with 'prewalk' & 'postwalk'
|
rlm@10
|
17 ;;
|
rlm@10
|
18 ;; * December 9, 2008: first version
|
rlm@10
|
19
|
rlm@10
|
20
|
rlm@10
|
21 (ns
|
rlm@10
|
22 ^{:author "Stuart Sierra",
|
rlm@10
|
23 :doc "This file defines a generic tree walker for Clojure data
|
rlm@10
|
24 structures. It takes any data structure (list, vector, map, set,
|
rlm@10
|
25 seq), calls a function on every element, and uses the return value
|
rlm@10
|
26 of the function in place of the original. This makes it fairly
|
rlm@10
|
27 easy to write recursive search-and-replace functions, as shown in
|
rlm@10
|
28 the examples.
|
rlm@10
|
29
|
rlm@10
|
30 Note: \"walk\" supports all Clojure data structures EXCEPT maps
|
rlm@10
|
31 created with sorted-map-by. There is no (obvious) way to retrieve
|
rlm@10
|
32 the sorting function."}
|
rlm@10
|
33 clojure.walk)
|
rlm@10
|
34
|
rlm@10
|
35 (defn walk
|
rlm@10
|
36 "Traverses form, an arbitrary data structure. inner and outer are
|
rlm@10
|
37 functions. Applies inner to each element of form, building up a
|
rlm@10
|
38 data structure of the same type, then applies outer to the result.
|
rlm@10
|
39 Recognizes all Clojure data structures except sorted-map-by.
|
rlm@10
|
40 Consumes seqs as with doall."
|
rlm@10
|
41 {:added "1.1"}
|
rlm@10
|
42 [inner outer form]
|
rlm@10
|
43 (cond
|
rlm@10
|
44 (list? form) (outer (apply list (map inner form)))
|
rlm@10
|
45 (seq? form) (outer (doall (map inner form)))
|
rlm@10
|
46 (vector? form) (outer (vec (map inner form)))
|
rlm@10
|
47 (map? form) (outer (into (if (sorted? form) (sorted-map) {})
|
rlm@10
|
48 (map inner form)))
|
rlm@10
|
49 (set? form) (outer (into (if (sorted? form) (sorted-set) #{})
|
rlm@10
|
50 (map inner form)))
|
rlm@10
|
51 :else (outer form)))
|
rlm@10
|
52
|
rlm@10
|
53 (defn postwalk
|
rlm@10
|
54 "Performs a depth-first, post-order traversal of form. Calls f on
|
rlm@10
|
55 each sub-form, uses f's return value in place of the original.
|
rlm@10
|
56 Recognizes all Clojure data structures except sorted-map-by.
|
rlm@10
|
57 Consumes seqs as with doall."
|
rlm@10
|
58 {:added "1.1"}
|
rlm@10
|
59 [f form]
|
rlm@10
|
60 (walk (partial postwalk f) f form))
|
rlm@10
|
61
|
rlm@10
|
62 (defn prewalk
|
rlm@10
|
63 "Like postwalk, but does pre-order traversal."
|
rlm@10
|
64 {:added "1.1"}
|
rlm@10
|
65 [f form]
|
rlm@10
|
66 (walk (partial prewalk f) identity (f form)))
|
rlm@10
|
67
|
rlm@10
|
68
|
rlm@10
|
69 ;; Note: I wanted to write:
|
rlm@10
|
70 ;;
|
rlm@10
|
71 ;; (defn walk
|
rlm@10
|
72 ;; [f form]
|
rlm@10
|
73 ;; (let [pf (partial walk f)]
|
rlm@10
|
74 ;; (if (coll? form)
|
rlm@10
|
75 ;; (f (into (empty form) (map pf form)))
|
rlm@10
|
76 ;; (f form))))
|
rlm@10
|
77 ;;
|
rlm@10
|
78 ;; but this throws a ClassCastException when applied to a map.
|
rlm@10
|
79
|
rlm@10
|
80
|
rlm@10
|
81 (defn postwalk-demo
|
rlm@10
|
82 "Demonstrates the behavior of postwalk by printing each form as it is
|
rlm@10
|
83 walked. Returns form."
|
rlm@10
|
84 {:added "1.1"}
|
rlm@10
|
85 [form]
|
rlm@10
|
86 (postwalk (fn [x] (print "Walked: ") (prn x) x) form))
|
rlm@10
|
87
|
rlm@10
|
88 (defn prewalk-demo
|
rlm@10
|
89 "Demonstrates the behavior of prewalk by printing each form as it is
|
rlm@10
|
90 walked. Returns form."
|
rlm@10
|
91 {:added "1.1"}
|
rlm@10
|
92 [form]
|
rlm@10
|
93 (prewalk (fn [x] (print "Walked: ") (prn x) x) form))
|
rlm@10
|
94
|
rlm@10
|
95 (defn keywordize-keys
|
rlm@10
|
96 "Recursively transforms all map keys from strings to keywords."
|
rlm@10
|
97 {:added "1.1"}
|
rlm@10
|
98 [m]
|
rlm@10
|
99 (let [f (fn [[k v]] (if (string? k) [(keyword k) v] [k v]))]
|
rlm@10
|
100 ;; only apply to maps
|
rlm@10
|
101 (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))
|
rlm@10
|
102
|
rlm@10
|
103 (defn stringify-keys
|
rlm@10
|
104 "Recursively transforms all map keys from keywords to strings."
|
rlm@10
|
105 {:added "1.1"}
|
rlm@10
|
106 [m]
|
rlm@10
|
107 (let [f (fn [[k v]] (if (keyword? k) [(name k) v] [k v]))]
|
rlm@10
|
108 ;; only apply to maps
|
rlm@10
|
109 (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))
|
rlm@10
|
110
|
rlm@10
|
111 (defn prewalk-replace
|
rlm@10
|
112 "Recursively transforms form by replacing keys in smap with their
|
rlm@10
|
113 values. Like clojure/replace but works on any data structure. Does
|
rlm@10
|
114 replacement at the root of the tree first."
|
rlm@10
|
115 {:added "1.1"}
|
rlm@10
|
116 [smap form]
|
rlm@10
|
117 (prewalk (fn [x] (if (contains? smap x) (smap x) x)) form))
|
rlm@10
|
118
|
rlm@10
|
119 (defn postwalk-replace
|
rlm@10
|
120 "Recursively transforms form by replacing keys in smap with their
|
rlm@10
|
121 values. Like clojure/replace but works on any data structure. Does
|
rlm@10
|
122 replacement at the leaves of the tree first."
|
rlm@10
|
123 {:added "1.1"}
|
rlm@10
|
124 [smap form]
|
rlm@10
|
125 (postwalk (fn [x] (if (contains? smap x) (smap x) x)) form))
|
rlm@10
|
126
|
rlm@10
|
127 (defn macroexpand-all
|
rlm@10
|
128 "Recursively performs all possible macroexpansions in form."
|
rlm@10
|
129 {:added "1.1"}
|
rlm@10
|
130 [form]
|
rlm@10
|
131 (prewalk (fn [x] (if (seq? x) (macroexpand x) x)) form))
|
rlm@10
|
132
|