rlm@10: ;   Copyright (c) Rich Hickey. All rights reserved.
rlm@10: ;   The use and distribution terms for this software are covered by the
rlm@10: ;   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
rlm@10: ;   which can be found in the file epl-v10.html at the root of this distribution.
rlm@10: ;   By using this software in any fashion, you are agreeing to be bound by
rlm@10: ;   the terms of this license.
rlm@10: ;   You must not remove this notice, or any other, from this software.
rlm@10: 
rlm@10: ;;; walk.clj - generic tree walker with replacement
rlm@10: 
rlm@10: ;; by Stuart Sierra
rlm@10: ;; December 15, 2008
rlm@10: 
rlm@10: ;; CHANGE LOG:
rlm@10: ;;
rlm@10: ;; * December 15, 2008: replaced 'walk' with 'prewalk' & 'postwalk'
rlm@10: ;;
rlm@10: ;; * December 9, 2008: first version
rlm@10: 
rlm@10: 
rlm@10: (ns 
rlm@10:   ^{:author "Stuart Sierra",
rlm@10:      :doc "This file defines a generic tree walker for Clojure data
rlm@10: structures.  It takes any data structure (list, vector, map, set,
rlm@10: seq), calls a function on every element, and uses the return value
rlm@10: of the function in place of the original.  This makes it fairly
rlm@10: easy to write recursive search-and-replace functions, as shown in
rlm@10: the examples.
rlm@10: 
rlm@10: Note: \"walk\" supports all Clojure data structures EXCEPT maps
rlm@10: created with sorted-map-by.  There is no (obvious) way to retrieve
rlm@10: the sorting function."}
rlm@10:   clojure.walk)
rlm@10: 
rlm@10: (defn walk
rlm@10:   "Traverses form, an arbitrary data structure.  inner and outer are
rlm@10:   functions.  Applies inner to each element of form, building up a
rlm@10:   data structure of the same type, then applies outer to the result.
rlm@10:   Recognizes all Clojure data structures except sorted-map-by.
rlm@10:   Consumes seqs as with doall."
rlm@10:   {:added "1.1"}
rlm@10:   [inner outer form]
rlm@10:   (cond
rlm@10:    (list? form) (outer (apply list (map inner form)))
rlm@10:    (seq? form) (outer (doall (map inner form)))
rlm@10:    (vector? form) (outer (vec (map inner form)))
rlm@10:    (map? form) (outer (into (if (sorted? form) (sorted-map) {})
rlm@10:                             (map inner form)))
rlm@10:    (set? form) (outer (into (if (sorted? form) (sorted-set) #{})
rlm@10:                             (map inner form)))
rlm@10:    :else (outer form)))
rlm@10: 
rlm@10: (defn postwalk
rlm@10:   "Performs a depth-first, post-order traversal of form.  Calls f on
rlm@10:   each sub-form, uses f's return value in place of the original.
rlm@10:   Recognizes all Clojure data structures except sorted-map-by.
rlm@10:   Consumes seqs as with doall."
rlm@10:   {:added "1.1"}
rlm@10:   [f form]
rlm@10:   (walk (partial postwalk f) f form))
rlm@10: 
rlm@10: (defn prewalk
rlm@10:   "Like postwalk, but does pre-order traversal."
rlm@10:   {:added "1.1"}
rlm@10:   [f form]
rlm@10:   (walk (partial prewalk f) identity (f form)))
rlm@10: 
rlm@10: 
rlm@10: ;; Note: I wanted to write:
rlm@10: ;;
rlm@10: ;; (defn walk
rlm@10: ;;   [f form]
rlm@10: ;;   (let [pf (partial walk f)]
rlm@10: ;;     (if (coll? form)
rlm@10: ;;       (f (into (empty form) (map pf form)))
rlm@10: ;;       (f form))))
rlm@10: ;;
rlm@10: ;; but this throws a ClassCastException when applied to a map.
rlm@10: 
rlm@10: 
rlm@10: (defn postwalk-demo
rlm@10:   "Demonstrates the behavior of postwalk by printing each form as it is
rlm@10:   walked.  Returns form."
rlm@10:   {:added "1.1"}
rlm@10:   [form]
rlm@10:   (postwalk (fn [x] (print "Walked: ") (prn x) x) form))
rlm@10: 
rlm@10: (defn prewalk-demo
rlm@10:   "Demonstrates the behavior of prewalk by printing each form as it is
rlm@10:   walked.  Returns form."
rlm@10:   {:added "1.1"}
rlm@10:   [form]
rlm@10:   (prewalk (fn [x] (print "Walked: ") (prn x) x) form))
rlm@10: 
rlm@10: (defn keywordize-keys
rlm@10:   "Recursively transforms all map keys from strings to keywords."
rlm@10:   {:added "1.1"}
rlm@10:   [m]
rlm@10:   (let [f (fn [[k v]] (if (string? k) [(keyword k) v] [k v]))]
rlm@10:     ;; only apply to maps
rlm@10:     (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))
rlm@10: 
rlm@10: (defn stringify-keys
rlm@10:   "Recursively transforms all map keys from keywords to strings."
rlm@10:   {:added "1.1"}
rlm@10:   [m]
rlm@10:   (let [f (fn [[k v]] (if (keyword? k) [(name k) v] [k v]))]
rlm@10:     ;; only apply to maps
rlm@10:     (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))
rlm@10: 
rlm@10: (defn prewalk-replace
rlm@10:   "Recursively transforms form by replacing keys in smap with their
rlm@10:   values.  Like clojure/replace but works on any data structure.  Does
rlm@10:   replacement at the root of the tree first."
rlm@10:   {:added "1.1"}
rlm@10:   [smap form]
rlm@10:   (prewalk (fn [x] (if (contains? smap x) (smap x) x)) form))
rlm@10: 
rlm@10: (defn postwalk-replace
rlm@10:   "Recursively transforms form by replacing keys in smap with their
rlm@10:   values.  Like clojure/replace but works on any data structure.  Does
rlm@10:   replacement at the leaves of the tree first."
rlm@10:   {:added "1.1"}
rlm@10:   [smap form]
rlm@10:   (postwalk (fn [x] (if (contains? smap x) (smap x) x)) form))
rlm@10: 
rlm@10: (defn macroexpand-all
rlm@10:   "Recursively performs all possible macroexpansions in form."
rlm@10:   {:added "1.1"}
rlm@10:   [form]
rlm@10:   (prewalk (fn [x] (if (seq? x) (macroexpand x) x)) form))
rlm@10: