Clojure：如何替换嵌套列表中的元素？

Question

我有一个深度嵌套的列表（列表的列表），我想替换列表中的单个任意元素。我该怎么做？（内置的replace可能会替换多个出现，而我只需要替换一个元素。）

- GabiMe

---

你能给我们展示一下你的列表结构和你想要进行的替换类型的例子吗？ - clartaq

（replace-rand some-list new-node）将在列表l中随机替换一个节点为给定的new-node。该列表可能是一个嵌套深度列表，被替换的元素可能是一个“深层”节点。 - GabiMe

Answer 1

正如其他人已经说过的那样，如果需要进行此类操作，则使用列表并不是一个好主意。随机访问是向量的用途。`assoc-in` 可以有效地完成此操作。使用列表时，您无法避免递归进入子列表并将大多数子列表替换为其自身的修改版本，一直到顶部。

尽管效率低下且笨拙，但以下代码可以完成此操作。借鉴 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))

使用方法：

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)))

如果您给出任何大于子列表长度的n，将会得到IndexOutOfBoundsException。这也不是尾递归的。它也不是惯用的写法，因为好的Clojure代码避免使用列表来处理所有事情。这很糟糕。在使用此代码之前，我可能会使用可变的Java数组。我想您已经明白了。

编辑

在这种情况下，列表比向量更差的原因：

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

你无需亲自编写assoc-in，因为它已经存在了。有空的时候看看assoc-in的实现；由于向量使用索引提供高效和易于随机访问，因此它的实现很简单直接（与列表版本相比）。

你也无需像引用列表一样引用向量。在Clojure中，列表强烈暗示“我正在调用一个函数或宏”。

向量（以及映射、集等）可以通过seq进行遍历。你可以以类似列表的方式透明地使用向量，那么为什么不使用向量，获得两者最好的优点呢？

向量在视觉上也很突出。由于广泛使用[]和{}，Clojure代码不像其他Lisp那样是一个巨大的括号块。有些人发现这很烦人，我却认为这使阅读变得更容易。（我的编辑器对()、[]和{}使用不同的语法高亮，这更有助于阅读。）

以下是我会使用列表作为数据的一些情况：

1. 如果我有一个有序数据结构，需要从前面增长，并且永远不需要随机访问
2. 手动构建一个seq，例如通过lazy-seq
3. 编写需要将代码作为数据返回的宏

- Brian Carper

---

为什么列表这么可怕？实际上我经常使用它们。 但无论如何，这是一个很好的解决方案。正是我所需要的。谢谢！ - GabiMe

因为列表具有O(N)的访问特性，而向量具有O(log32(N))的访问特性。列表在头部访问方面表现良好，但对于随机访问来说不太适用，因为您总是需要遍历整个列表才能到达深层索引。 - kotarak

我在我的回答中稍微阐述了一下列表与向量的区别。 - Brian Carper

Answer 2

对于简单的情况，递归替换函数可以给你所需的内容，而不会增加太多复杂性。当事情变得更加复杂时，就该打开Clojure内置的zipper函数了：“Clojure包括纯函数、通用树遍历和编辑，使用一种叫做zipper的技术（在命名空间zip中）。” 摘自：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)))))

这些内容适用于任何嵌套的可序列化对象，甚至包括XML文件。

- Arthur Ulfeldt

---

在这个例子中，如果你想要替换“树中的第X个元素”而不仅仅是“随机替换元素”，你也可以在循环中添加一个计数器。 - Arthur Ulfeldt

Zipper看起来是一个合适的解决方案，但我想知道使用Zipper的性能成本是多少。将列表转换为压缩树并在压缩/替换后再转换回列表的性能惩罚是多少？ - GabiMe

zip宏生成一个函数，该函数迭代嵌套的任何内容，嵌套列表，数组等，并在进行迭代时生成一个新的内容。 zip函数使用元数据来跟踪更改。 访问速度将与底层数据结构一样快。 - Arthur Ulfeldt

Answer 3

虽然这与你的问题不完全相关，但如果你有向量而非列表：

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]

如果可能的话，请使用向量而不是列表，以获得更好的访问行为。如果您必须使用来自各种来源的lazy-seq，则当然不是一个好建议...

- kotarak

Answer 4

你可以使用这个函数并根据自己的需求进行调整（嵌套列表）：

(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)))

- dermatthias

---

难点怎么样？让它支持嵌套列表呢？ - GabiMe

Answer 5

来自普通观众的一个简单建议：

• 将内部列表复制到向量中；
• 使用assoc随意随机调整该向量的元素；
• 将向量复制回列表；
• 替换外部列表中的嵌套列表。

这可能会浪费一些性能；但如果这是一个性能敏感的操作，你本来就应该使用向量。

- Carl Smotricz