在Clojure中添加矢量的习惯用法是什么?

预先列表很容易:

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

追加矢量很简单:

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

我如何(习惯性地)在获取矢量的同时加入矢量? 这不起作用,因为它返回一个seq,而不是一个矢量:

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

这很丑陋(IMVHO):

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

注意:我基本上只是想要一个数据结构,我可以附加并预先加入。 追加到大列表应该会有很大的性能损失,所以我想到了矢量..


矢量不是为预先设计的。 你只有O(n)前置:

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

你想要的是最有可能的一个手指树。


我知道这个问题很老,但没有人对差异列表发表任何评论,既然你说你真的只想要一些你可以追加和附加的东西,这听起来像差异列表可能会帮助你。 它们在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)

正如用户在手指树答案下的评论中所述,可以使用实现RRB树的clojure / core.rrb-vector库:

RRB-Trees基于Clojure的PersistentVectors,增加对数时间连接和切片。 ClojureScript支持相同的API,除了没有vector-of函数。

我决定将其作为一个单独的答案发布,因为我认为这个图书馆应该得到这个答案。 它支持ClojureScript,它由MichałMarczyk维护,MichałMarczyk在Clojure社区中为实现各种数据结构而着称。

链接地址: http://www.djcxy.com/p/66871.html

上一篇: What is the idiomatic way to prepend to a vector in Clojure?

下一篇: Clojure: working with a java.util.HashMap in an idiomatic Clojure fashion