62

预先添加到列表很容易：

user=> (conj '(:bar :baz) :foo)
(:foo :bar :baz)

附加到向量很容易：

user=> (conj [:bar :baz] :foo) 
[:bar :baz :foo]

我如何（惯用地）添加到向量，同时取回向量？这不起作用，因为它返回一个序列，而不是一个向量：

user=> (cons :foo [:bar :baz])     
(:foo :bar :baz)

这很难看（IMVHO）：

user=> (apply vector (cons :foo [:bar :baz])) 
[:foo :bar :baz]

注意：我基本上只想要一个可以附加和前置的数据结构。附加到大列表应该会有很大的性能损失，所以我想到了向量..

4

5 回答 5

80

向量不是为前置而设计的。您只有 O(n) 前置：

user=> (into [:foo] [:bar :baz])
[:foo :bar :baz]

你想要的很可能是一棵手指树。

于 2010-11-04T10:40:11.817 回答
18

我知道这个问题很老，但是没有人说任何关于差异列表的事情，因为你说你真的只是想要一些你可以附加和前置的东西，听起来差异列表可能会对你有所帮助。它们在 Clojure 中似乎并不流行，但它们很容易实现，并且比手指树复杂得多，所以我刚刚做了一个微小的差异列表库（甚至测试了它）。这些在 O(1) 时间内连接（前置或附加）。将差异列表转换回列表应该花费您 O(n)，如果您要进行大量连接，这是一个很好的权衡。如果你没有做很多连接，那么就坚持使用列表，对吧？:)

以下是这个小型库中的函数：

dl：差异列表实际上是一个函数，它将自己的内容与参数连接起来并返回结果列表。每次生成差异列表时，您都在创建一个类似于数据结构的小函数。

dlempty：由于差异列表只是将其内容连接到参数，因此空差异列表与恒等函数相同。

undl：由于差异列表的作用，您可以将差异列表转换为普通列表，只需使用 nil 调用它，因此实际上不需要此函数；这只是为了方便。

dlcons：将一个项目放在列表的前面——不是完全必要的，但 consing 是一个足够常见的操作，它只是一个单行（就像所有的函数一样，这里）。

dlappend：连接两个差异列表。我认为它的定义是最有趣的——看看吧！:)

现在，这是一个微型库—— 5 个单行函数，为您提供 O(1) 附加/前置数据结构。还不错吧？啊，Lambda微积分的美...

(defn dl
  "Return a difference list for a list"
  [l]
  (fn [x] (concat l x)))

; Return an empty difference list
(def dlempty identity)

(defn undl
  "Return a list for a difference list (just call the difference list with nil)"
  [aDl]
  (aDl nil))

(defn dlcons
  "Cons an item onto a difference list"
  [item aDl]
  (fn [x] (cons item (aDl x))))

(defn dlappend
  "Append two difference lists"
  [dl1 dl2]
  (fn [x] (dl1 (dl2 x))))

您可以通过以下方式看到它的实际效果：

(undl (dlappend (dl '(1 2 3)) (dl '(4 5 6))))

返回：

(1 2 3 4 5 6)

这也返回相同的东西：

((dl '(1 2 3)) '(4 5 6))

享受差异列表的乐趣！

更新

以下是一些可能更难理解但我认为更好的定义：

(defn dl [& elements] (fn [x] (concat elements x)))
(defn dl-un [l] (l nil))
(defn dl-concat [& lists] (fn [x] ((apply comp lists) x)))

这让你可以这样说：

(dl-un (dl-concat (dl 1) (dl 2 3) (dl) (dl 4)))

哪个会返回

(1 2 3 4)
于 2012-11-12T22:53:15.683 回答
3

正如用户 optevo 在手指树答案下的评论中所说，您可以使用实现 RRB 树的clojure/core.rrb-vector库：

RRB-Trees 建立在 Clojure 的 PersistentVectors 之上，添加了对数时间连接和切片。ClojureScript 支持相同的 API，但缺少该vector-of函数。

我决定将此作为单独的答案发布，因为我认为这个库值得。它支持 ClojureScript，由Michał Marczyk维护，他在 Clojure 社区中因在实现各种数据结构方面的工作而广为人知。

于 2015-10-14T19:05:58.350 回答
2

如果您不害怕 quasiquoting，那么这个解决方案实际上非常优雅（对于“优雅”的某些定义）：

> `[~:foo ~@[:bar :baz]]

[:foo :bar :baz]

实际上，我有时会在实际代码中使用它，因为声明性语法使它非常易读，恕我直言。

于 2018-12-21T19:53:41.880 回答
1

我建议使用Tupelo Library 内置的便利功能。例如：

(append [1 2] 3  )   ;=> [1 2 3  ]
(append [1 2] 3 4)   ;=> [1 2 3 4]

(prepend   3 [2 1])  ;=> [  3 2 1]
(prepend 4 3 [2 1])  ;=> [4 3 2 1]

相比之下，使用原始 Clojure 很容易出错：

; Add to the end
(concat [1 2] 3)    ;=> IllegalArgumentException
(cons   [1 2] 3)    ;=> IllegalArgumentException
(conj   [1 2] 3)    ;=> [1 2 3]
(conj   [1 2] 3 4)  ;=> [1 2 3 4]

; Add to the beginning
(conj     1 [2 3] ) ;=> ClassCastException
(concat   1 [2 3] ) ;=> IllegalArgumentException
(cons     1 [2 3] ) ;=> (1 2 3)
(cons   1 2 [3 4] ) ;=> ArityException
于 2016-07-07T19:42:16.573 回答