walk weaknesses

[Kodiologist]

You'd think from the name, or from the word "traverse" in its docstring, that walk does some kind of recursive descent into its argument. It doesn't.

It looks like the function was inspired by Clojure, and by "inspired" I mean "literally copies part of the docstring", which could be a licensing issue (even if the Eclipse Public License is compatible with our license, we would need to keep track of the chain of copyright). Here's the Clojure implementation:

(defn walk
  "Traverses form, an arbitrary data structure.  inner and outer are
  functions.  Applies inner to each element of form, building up a
  data structure of the same type, then applies outer to the result.
  Recognizes all Clojure data structures. Consumes seqs as with doall."

  {:added "1.1"}
  [inner outer form]
  (cond
   (list? form)
     (outer (apply list (map inner form)))
   (instance? clojure.lang.IMapEntry form)
     (outer (clojure.lang.MapEntry/create (inner (key form)) (inner (val form))))
   (seq? form)
     (outer (doall (map inner form)))
   (instance? clojure.lang.IRecord form)
     (outer (reduce (fn [r x] (conj r (inner x))) form form))
   (coll? form)
     (outer (into (empty form) (map inner form)))
   :else
     (outer form)))

The Clojure implementation makes it clearer what walk is supposed to do: (walk inner outer x) should work like (outer (map inner x)), except x can be of several types that aren't supported by Clojure's map, and the return value of the map is reboxed in whatever collection type x started out as.

The Clojure implementation also makes it clear that the outer parameter is totally superfluous, because (walk inner outer x) is equivalent to (outer (walk inner identity x)). Why does it exist? Why did the programmer write outer in every branch instead of just wrapping the whole (cond ...) in outer? Why would a programming language that enthusiastically promotes side-effect–free programming be named after closures? There are some questions that man is not meant to know the answer to.

Here's the current Hy implementation:

(defn walk [inner outer form]
  "Traverses form, an arbitrary data structure. Applies inner to each
  element of form, building up a data structure of the same type.
  Applies outer to the result."
  (cond
   [(instance? HyExpression form)
    (outer (HyExpression (map inner form)))]
   [(or (instance? HySequence form) (list? form))
    ((type form) (outer (HyExpression (map inner form))))]
   [(coll? form)
    (walk inner outer (list form))]
   [True (outer form)]))

Two bugs are now obvious: in the first and third branches of the cond, the return value is not reboxed, and in the second branch, outer is called on a HyExpression instead of the reboxed collection.

So here are the changes to walk that appear necessary:

• Give it a better name.
• Remove the outer parameter.
• Rename the last argument. form suggests it is an unevaluated expression of some kind, which it might be, but it doesn't have to be.
• Fix the bugs.
• Improve the docstring.
• Ensure that it supports a wide variety of data structures.