Most embedded list in a Clojure form

clojure

69 观看

2回复

64 作者的声誉

I am rather new to Clojure and I need to write a function which, given some Clojure form, replaces the most nested list with some value. For example:

(my-fn '(+ [* a b] (* c d) (* e (/ f g))) 'foo)
=> (+ (* a b) (* c d) (* e foo)) 
(my-fn '(+ [* a b] (* c d) (* e foo)) 'bar)
=> (+ [* a b] bar (* e foo))

I'm not asking for a full implementation but if somebody could give me a few pointers I'd be very grateful.

Thanks.

作者: OParry 的来源 发布者: 2017 年 12 月 27 日

回应 (2)


0

4938 作者的声誉

As far as knowing what the 'greatest depth' is, you would need to first of all parse through all the forms just to find this answer, then do a second parse already knowing this. You might want a recursive function for each parse (so two recursive functions).

You could map/mapv (depending on whether the input is a vector or a list) over all the forms, recursing for any that satisfy coll?, otherwise keeping the form as it is if it is not 'some value', or changing it if it is, and is at the 'most deep' level.

You would also need to keep in the 'state' whether replacement has already been done at the deepest level, so that repeat replacements do not happen. State can be kept as parameters to the second parse recursive function. You might want an initial function that calls the recursive functions for the first time.

Note that coll? returns true for a map data structure, so you might want to use something more granular, such as (some-fn list? vector?) or (every-pred coll? (complement map?)). seq? won't work for vectors.

That was a few pointers and not a full implementation, suitable for a relative newcomer to Clojure. You will get a lot more out of doing it yourself based on some hints rather than following a zipper based solution.

作者: Chris Murphy 发布者: 28.12.2017 12:19

2

11359 作者的声誉

决定

there is a way to perform this operation in one pass in clojure's core library: zippers

the key is that you can traverse and modify the tree in context. It could look like this:

(require '[clojure.zip :as z])

(defn replace-deepest [data replacer]
  (->> data
       z/seq-zip
       (iterate z/next)
       (take-while (complement z/end?))
       (apply max-key #(if (seq? (z/node %))
                         (count (z/path %))
                         -1))
       (#(z/replace % replacer))
       z/root))

user> (replace-deepest '(+ [* a b] (* c d) (* e (/ f g))) :asd)
;;=> (+ [* a b] (* c d) (* e :asd))

user> (replace-deepest '(+ [* a b] (* c (+ x (* y z)) d) (* e (/ f g))) :asd)
;;=> (+ [* a b] (* c (+ x :asd) d) (* e (/ f g)))

this approach traverses the collection depth-first collecting data, and then compares the z/path values count (the path is the part of aforementioned context). Then you can replace the node (in fact rebuild the tree with replaced value)

作者: leetwinski 发布者: 28.12.2017 06:38
32x32