Clojure: How to replace an element in a nested list?

Question

I have this deeply nested list (list of lists) and I want to replace a single arbitrary element in the list. How can I do this ? (The built-in replace might replace many occurrences while I need to replace only one element.)

Answer 1

As everyone else already said, using lists is really not a good idea if you need to do this kind of thing. Random access is what vectors are made for. assoc-in does this efficiently. With lists you can't get away from recursing down into the sublists and replacing most of them with altered versions of themselves all the way back up to the top.

This code will do it though, albeit inefficiently and clumsily. Borrowing from dermatthias:

(defn replace-in-list [coll n x]
  (concat (take n coll) (list x) (nthnext coll (inc n))))

(defn replace-in-sublist [coll ns x]
  (if (seq ns)
    (let [sublist (nth coll (first ns))]
      (replace-in-list coll
                       (first ns)
                       (replace-in-sublist sublist (rest ns) x)))
    x))

Usage:

user> (def x '(0 1 2 (0 1 (0 1 2) 3 4 (0 1 2))))
#'user/x
user> (replace-in-sublist x [3 2 0] :foo) 
(0 1 2 (0 1 (:foo 1 2) 3 4 (0 1 2)))
user> (replace-in-sublist x [3 2] :foo) 
(0 1 2 (0 1 :foo 3 4 (0 1 2)))
user> (replace-in-sublist x [3 5 1] '(:foo :bar)) 
(0 1 2 (0 1 (0 1 2) 3 4 (0 (:foo :bar) 2)))

You'll get IndexOutOfBoundsException if you give any n greater than the length of a sublist. It's also not tail-recursive. It's also not idiomatic because good Clojure code shies away from using lists for everything. It's horrible. I'd probably use mutable Java arrays before I used this. I think you get the idea.

Edit

Reasons why lists are worse than vectors in this case:

user> (time
       (let [x '(0 1 2 (0 1 (0 1 2) 3 4 (0 1 2)))]               ;'
         (dotimes [_ 1e6] (replace-in-sublist x [3 2 0] :foo))))
"Elapsed time: 5201.110134 msecs"
nil
user> (time
       (let [x [0 1 2 [0 1 [0 1 2] 3 4 [0 1 2]]]]
         (dotimes [_ 1e6] (assoc-in x [3 2 0] :foo))))
"Elapsed time: 2925.318122 msecs"
nil

You also don't have to write assoc-in yourself, it already exists. Look at the implementation for assoc-in sometime; it's simple and straightforward (compared to the list version) thanks to vectors giving efficient and easy random access by index, via get.

You also don't have to quote vectors like you have to quote lists. Lists in Clojure strongly imply "I'm calling a function or macro here".

Vectors (and maps, sets etc.) can be traversed via seqs. You can transparently use vectors in list-like ways, so why not use vectors and have the best of both worlds?

Vectors also stand out visually. Clojure code is less of a huge blob of parens than other Lisps thanks to widespread use of [] and {}. Some people find this annoying, I find it makes things easier to read. (My editor syntax-highlights (), [] and {} differently which helps even more.)

Some instances I'd use a list for data:

1. If I have an ordered data structure that needs to grow from the front, that I'm never going to need random-access to
2. Building a seq "by hand", as via lazy-seq
3. Writing a macro, which needs to return code as data

Answer 2

For the simple cases a recursive substitution function will give you just what you need with out much extra complexity. when things get a little more complex its time to crack open clojure build in zipper functions: "Clojure includes purely functional, generic tree walking and editing, using a technique called a zipper (in namespace zip)."

adapted from the example in: http://clojure.org/other_libraries

(defn randomly-replace [replace-with in-tree]
    (loop [loc dz]
      (if (zip/end? loc)
      (zip/root loc)
     (recur
      (zip/next
       (if (= 0 (get-random-int 10))
         (zip/replace loc replace-with)
         loc)))))

these will work with nested anything (seq'able) even xmls

Answer 3

It sort of doesn't answer your question, but if you have vectors instead of lists:

user=> (update-in [1 [2 3] 4 5] [1 1] inc)
[1 [2 4] 4 5]
user=> (assoc-in [1 [2 3] 4 5] [1 1] 6)
[1 [2 6] 4 5]

So if possible avoid lists in favour of vectors for the better access behaviour. If you have to work with lazy-seq from various sources, this is of course not much of an advice...