1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/clojure/walk.clj	Sat Aug 21 06:25:44 2010 -0400
     1.3 @@ -0,0 +1,132 @@
     1.4 +;   Copyright (c) Rich Hickey. All rights reserved.
     1.5 +;   The use and distribution terms for this software are covered by the
     1.6 +;   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
     1.7 +;   which can be found in the file epl-v10.html at the root of this distribution.
     1.8 +;   By using this software in any fashion, you are agreeing to be bound by
     1.9 +;   the terms of this license.
    1.10 +;   You must not remove this notice, or any other, from this software.
    1.11 +
    1.12 +;;; walk.clj - generic tree walker with replacement
    1.13 +
    1.14 +;; by Stuart Sierra
    1.15 +;; December 15, 2008
    1.16 +
    1.17 +;; CHANGE LOG:
    1.18 +;;
    1.19 +;; * December 15, 2008: replaced 'walk' with 'prewalk' & 'postwalk'
    1.20 +;;
    1.21 +;; * December 9, 2008: first version
    1.22 +
    1.23 +
    1.24 +(ns 
    1.25 +  ^{:author "Stuart Sierra",
    1.26 +     :doc "This file defines a generic tree walker for Clojure data
    1.27 +structures.  It takes any data structure (list, vector, map, set,
    1.28 +seq), calls a function on every element, and uses the return value
    1.29 +of the function in place of the original.  This makes it fairly
    1.30 +easy to write recursive search-and-replace functions, as shown in
    1.31 +the examples.
    1.32 +
    1.33 +Note: \"walk\" supports all Clojure data structures EXCEPT maps
    1.34 +created with sorted-map-by.  There is no (obvious) way to retrieve
    1.35 +the sorting function."}
    1.36 +  clojure.walk)
    1.37 +
    1.38 +(defn walk
    1.39 +  "Traverses form, an arbitrary data structure.  inner and outer are
    1.40 +  functions.  Applies inner to each element of form, building up a
    1.41 +  data structure of the same type, then applies outer to the result.
    1.42 +  Recognizes all Clojure data structures except sorted-map-by.
    1.43 +  Consumes seqs as with doall."
    1.44 +  {:added "1.1"}
    1.45 +  [inner outer form]
    1.46 +  (cond
    1.47 +   (list? form) (outer (apply list (map inner form)))
    1.48 +   (seq? form) (outer (doall (map inner form)))
    1.49 +   (vector? form) (outer (vec (map inner form)))
    1.50 +   (map? form) (outer (into (if (sorted? form) (sorted-map) {})
    1.51 +                            (map inner form)))
    1.52 +   (set? form) (outer (into (if (sorted? form) (sorted-set) #{})
    1.53 +                            (map inner form)))
    1.54 +   :else (outer form)))
    1.55 +
    1.56 +(defn postwalk
    1.57 +  "Performs a depth-first, post-order traversal of form.  Calls f on
    1.58 +  each sub-form, uses f's return value in place of the original.
    1.59 +  Recognizes all Clojure data structures except sorted-map-by.
    1.60 +  Consumes seqs as with doall."
    1.61 +  {:added "1.1"}
    1.62 +  [f form]
    1.63 +  (walk (partial postwalk f) f form))
    1.64 +
    1.65 +(defn prewalk
    1.66 +  "Like postwalk, but does pre-order traversal."
    1.67 +  {:added "1.1"}
    1.68 +  [f form]
    1.69 +  (walk (partial prewalk f) identity (f form)))
    1.70 +
    1.71 +
    1.72 +;; Note: I wanted to write:
    1.73 +;;
    1.74 +;; (defn walk
    1.75 +;;   [f form]
    1.76 +;;   (let [pf (partial walk f)]
    1.77 +;;     (if (coll? form)
    1.78 +;;       (f (into (empty form) (map pf form)))
    1.79 +;;       (f form))))
    1.80 +;;
    1.81 +;; but this throws a ClassCastException when applied to a map.
    1.82 +
    1.83 +
    1.84 +(defn postwalk-demo
    1.85 +  "Demonstrates the behavior of postwalk by printing each form as it is
    1.86 +  walked.  Returns form."
    1.87 +  {:added "1.1"}
    1.88 +  [form]
    1.89 +  (postwalk (fn [x] (print "Walked: ") (prn x) x) form))
    1.90 +
    1.91 +(defn prewalk-demo
    1.92 +  "Demonstrates the behavior of prewalk by printing each form as it is
    1.93 +  walked.  Returns form."
    1.94 +  {:added "1.1"}
    1.95 +  [form]
    1.96 +  (prewalk (fn [x] (print "Walked: ") (prn x) x) form))
    1.97 +
    1.98 +(defn keywordize-keys
    1.99 +  "Recursively transforms all map keys from strings to keywords."
   1.100 +  {:added "1.1"}
   1.101 +  [m]
   1.102 +  (let [f (fn [[k v]] (if (string? k) [(keyword k) v] [k v]))]
   1.103 +    ;; only apply to maps
   1.104 +    (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))
   1.105 +
   1.106 +(defn stringify-keys
   1.107 +  "Recursively transforms all map keys from keywords to strings."
   1.108 +  {:added "1.1"}
   1.109 +  [m]
   1.110 +  (let [f (fn [[k v]] (if (keyword? k) [(name k) v] [k v]))]
   1.111 +    ;; only apply to maps
   1.112 +    (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))
   1.113 +
   1.114 +(defn prewalk-replace
   1.115 +  "Recursively transforms form by replacing keys in smap with their
   1.116 +  values.  Like clojure/replace but works on any data structure.  Does
   1.117 +  replacement at the root of the tree first."
   1.118 +  {:added "1.1"}
   1.119 +  [smap form]
   1.120 +  (prewalk (fn [x] (if (contains? smap x) (smap x) x)) form))
   1.121 +
   1.122 +(defn postwalk-replace
   1.123 +  "Recursively transforms form by replacing keys in smap with their
   1.124 +  values.  Like clojure/replace but works on any data structure.  Does
   1.125 +  replacement at the leaves of the tree first."
   1.126 +  {:added "1.1"}
   1.127 +  [smap form]
   1.128 +  (postwalk (fn [x] (if (contains? smap x) (smap x) x)) form))
   1.129 +
   1.130 +(defn macroexpand-all
   1.131 +  "Recursively performs all possible macroexpansions in form."
   1.132 +  {:added "1.1"}
   1.133 +  [form]
   1.134 +  (prewalk (fn [x] (if (seq? x) (macroexpand x) x)) form))
   1.135 +