Mercurial > lasercutter

     1 ;   Copyright (c) Rich Hickey. All rights reserved.

     2 ;   The use and distribution terms for this software are covered by the

     3 ;   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)

     4 ;   which can be found in the file epl-v10.html at the root of this distribution.

     5 ;   By using this software in any fashion, you are agreeing to be bound by

     6 ;   the terms of this license.

     7 ;   You must not remove this notice, or any other, from this software.

     8 

     9 ;;; walk.clj - generic tree walker with replacement

    10 

    11 ;; by Stuart Sierra

    12 ;; December 15, 2008

    13 

    14 ;; CHANGE LOG:

    15 ;;

    16 ;; * December 15, 2008: replaced 'walk' with 'prewalk' & 'postwalk'

    17 ;;

    18 ;; * December 9, 2008: first version

    19 

    20 

    21 (ns 

    22   ^{:author "Stuart Sierra",

    23      :doc "This file defines a generic tree walker for Clojure data

    24 structures.  It takes any data structure (list, vector, map, set,

    25 seq), calls a function on every element, and uses the return value

    26 of the function in place of the original.  This makes it fairly

    27 easy to write recursive search-and-replace functions, as shown in

    28 the examples.

    29 

    30 Note: \"walk\" supports all Clojure data structures EXCEPT maps

    31 created with sorted-map-by.  There is no (obvious) way to retrieve

    32 the sorting function."}

    33   clojure.walk)

    34 

    35 (defn walk

    36   "Traverses form, an arbitrary data structure.  inner and outer are

    37   functions.  Applies inner to each element of form, building up a

    38   data structure of the same type, then applies outer to the result.

    39   Recognizes all Clojure data structures except sorted-map-by.

    40   Consumes seqs as with doall."

    41   {:added "1.1"}

    42   [inner outer form]

    43   (cond

    44    (list? form) (outer (apply list (map inner form)))

    45    (seq? form) (outer (doall (map inner form)))

    46    (vector? form) (outer (vec (map inner form)))

    47    (map? form) (outer (into (if (sorted? form) (sorted-map) {})

    48                             (map inner form)))

    49    (set? form) (outer (into (if (sorted? form) (sorted-set) #{})

    50                             (map inner form)))

    51    :else (outer form)))

    52 

    53 (defn postwalk

    54   "Performs a depth-first, post-order traversal of form.  Calls f on

    55   each sub-form, uses f's return value in place of the original.

    56   Recognizes all Clojure data structures except sorted-map-by.

    57   Consumes seqs as with doall."

    58   {:added "1.1"}

    59   [f form]

    60   (walk (partial postwalk f) f form))

    61 

    62 (defn prewalk

    63   "Like postwalk, but does pre-order traversal."

    64   {:added "1.1"}

    65   [f form]

    66   (walk (partial prewalk f) identity (f form)))

    67 

    68 

    69 ;; Note: I wanted to write:

    70 ;;

    71 ;; (defn walk

    72 ;;   [f form]

    73 ;;   (let [pf (partial walk f)]

    74 ;;     (if (coll? form)

    75 ;;       (f (into (empty form) (map pf form)))

    76 ;;       (f form))))

    77 ;;

    78 ;; but this throws a ClassCastException when applied to a map.

    79 

    80 

    81 (defn postwalk-demo

    82   "Demonstrates the behavior of postwalk by printing each form as it is

    83   walked.  Returns form."

    84   {:added "1.1"}

    85   [form]

    86   (postwalk (fn [x] (print "Walked: ") (prn x) x) form))

    87 

    88 (defn prewalk-demo

    89   "Demonstrates the behavior of prewalk by printing each form as it is

    90   walked.  Returns form."

    91   {:added "1.1"}

    92   [form]

    93   (prewalk (fn [x] (print "Walked: ") (prn x) x) form))

    94 

    95 (defn keywordize-keys

    96   "Recursively transforms all map keys from strings to keywords."

    97   {:added "1.1"}

    98   [m]

    99   (let [f (fn [[k v]] (if (string? k) [(keyword k) v] [k v]))]

   100     ;; only apply to maps

   101     (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))

   102 

   103 (defn stringify-keys

   104   "Recursively transforms all map keys from keywords to strings."

   105   {:added "1.1"}

   106   [m]

   107   (let [f (fn [[k v]] (if (keyword? k) [(name k) v] [k v]))]

   108     ;; only apply to maps

   109     (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))

   110 

   111 (defn prewalk-replace

   112   "Recursively transforms form by replacing keys in smap with their

   113   values.  Like clojure/replace but works on any data structure.  Does

   114   replacement at the root of the tree first."

   115   {:added "1.1"}

   116   [smap form]

   117   (prewalk (fn [x] (if (contains? smap x) (smap x) x)) form))

   118 

   119 (defn postwalk-replace

   120   "Recursively transforms form by replacing keys in smap with their

   121   values.  Like clojure/replace but works on any data structure.  Does

   122   replacement at the leaves of the tree first."

   123   {:added "1.1"}

   124   [smap form]

   125   (postwalk (fn [x] (if (contains? smap x) (smap x) x)) form))

   126 

   127 (defn macroexpand-all

   128   "Recursively performs all possible macroexpansions in form."

   129   {:added "1.1"}

   130   [form]

   131   (prewalk (fn [x] (if (seq? x) (macroexpand x) x)) form))

   132
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 21 Aug 2010 06:25:44 -0400
parents
children