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.)
2
-
Could you show us an example of the structure of your list and the type of substitution you want to do?clartaq– clartaq2009-12-07 14:18:04 +00:00Commented Dec 7, 2009 at 14:18
-
Example: (replace-rand some-list new-node) would replace a random node in l with the given new-node. The list might be a nested deep list, and the replaced element might be a "deep" node.GabiMe– GabiMe2009-12-07 14:31:49 +00:00Commented Dec 7, 2009 at 14:31
Add a comment
|
5 Answers
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:
- If I have an ordered data structure that needs to grow from the front, that I'm never going to need random-access to
- Building a seq "by hand", as via
lazy-seq - Writing a macro, which needs to return code as data
3 Comments
GabiMe
Why are lists so horrible? Actually I use them a lot. But anyway, this is a great solution. Exactly what I needed. Thanks !
kotarak
Because lists have access characteristics of O(N) vs. O(log32(N)) of vectors. Lists are good at access at the head, but bad for random access since you always have to walk the list to reach an index deep in the list.
Brian Carper
I've expounded on lists vs. vectors a bit in my answer.
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
3 Comments
Arthur Ulfeldt
in the example you could also add a counter to the loop if you wanted to replace "the Xth element in the tree" instead of just "randomly replace elements"
GabiMe
Zipper seems like a suitable solution, but I wonder what is the performance cost of using zipper. What is the performance penalty of transforming (zipping) a list to a zipped tree, and back to list after the zip/replace.
Arthur Ulfeldt
The zip macros produce a function that iterate a nested anything, nested lists, arrays whatever. and produce a new one as they go. the zip functions use metadata to keep track of changes. the access will be as fast as the underlying data structure.
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...
Comments
You could use this function and adapt it for your needs (nested lists):
(defn replace-item
"Returns a list with the n-th item of l replaced by v."
[l n v]
(concat (take n l) (list v) (drop (inc n) l)))
1 Comment
GabiMe
How about the hard part? Making this support nested lists ?
A simple-minded suggestion from the peanut gallery:
- copy the inner list to a vector;
- fiddle that vector's elements randomly and to your heart's content using
assoc; - copy the vector back to a list;
- replace the nested list in the outer list.
This might waste some performance; but if this was a performance sensitive operation you'd be working with vectors in the first place.
