What is the idiomatic way to prepend to a vector i

问题:

Prepending to a list is easy:

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

Appending to a vector is easy:

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

How do I (idiomatically) prepend to a vector, while getting back a vector? This does not work as it returns a seq, not a vector:

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

This is ugly (IMVHO):

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

Note: I basically just want a datastructure that I can append and prepend to. Appending to large lists should have a large performance penalty, so I thought of vectors..

回答1:

Vectors are not designed for prepending. You have only O(n) prepend:

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

What you want is most likely a finger tree.

回答2:

I know this question is old, but no one said anything about difference lists and since you say you really just want something you can append and prepend with, it sounds like difference lists might help you. They don't seem popular in Clojure, but they are VERY easy to implement and a lot less complex than finger trees, so I made a tiny difference list library, just now (and even tested it). These concatenate in O(1) time (prepend or append). Converting a difference list back to a list should cost you O(n), which is a nice trade-off if you're doing a lot of concatenation. If you're not doing a lot of concatenation, then just stick to lists, right? :)

Here are the functions in this tiny library:

dl: A difference list is actually a function which concats its own contents with the argument and returns the resulting list. Every time you produce a difference list, you're creating a little function that acts like a data structure.

dlempty: Since a difference list just concats its contents to the argument, an empty difference list is the same thing as the identity function.

undl: Because of what difference lists do, you can convert a difference list to a normal list just by calling it with nil, so this function isn't really needed; it's just for convenience.

dlcons: conses an item to the front of the list -- not totally necessary, but consing is a common enough operation and it's just a one-liner (like all of the functions, here).

dlappend: concats two difference lists. I think its definition is the most fun -- check it out! :)

And now, here's that tiny library -- 5 one-line functions that give you a O(1) append/prepend data structure. Not bad, eh? Ah, the beauty of Lambda Calculus...

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

You can see it in action with this:

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

which returns:

(1 2 3 4 5 6)

This also returns the same thing:

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

Have fun with difference lists!

Update

Here are some definitions that may be more difficult to understand but I think are better:

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

This lets you say something like this:

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

Which would return

(1 2 3 4)

回答3:

As the user optevo said in the comments under the finger trees answer, you can use the clojure/core.rrb-vector lib, which implements RRB-trees:

RRB-Trees build upon Clojure's PersistentVectors, adding logarithmic time concatenation and slicing. ClojureScript is supported with the same API except for the absence of the vector-of function.

I decided to post this as a separate answer, because I think this library deserves that. It supports ClojureScript and it's maintained by Michał Marczyk, who is fairly known within the Clojure community for his work on implementing various data structures.

回答4:

I would suggest using the convenience features built into the Tupelo Library. For example:

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

by comparison, with raw Clojure it is easy to make a mistake:

; 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

回答5:

If you don't fear quasiquoting, this solution is actually pretty elegant (for some definitions of 'elegant'):

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

[:foo :bar :baz]

I actually use this on occasion in real code, since the declarative syntax makes it pretty readable IMHO.