[ACCEPTED]-What is the idiomatic way to prepend to a vector in Clojure?-prepend

Accepted answer
Score: 80

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

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

What you want is 1 most likely a finger tree.

Score: 18

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

Here are the functions in 29 this tiny library:

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

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

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

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

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

And now, here's 10 that tiny library -- 5 one-line functions 9 that give you a O(1) append/prepend data 8 structure. Not bad, eh? Ah, the beauty 7 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 6 with this:

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

which returns:

(1 2 3 4 5 6)

This also returns 5 the same thing:

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

Have fun with difference 4 lists!

Update

Here are some definitions that may 3 be more difficult to understand but I think 2 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 1 this:

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

Which would return

(1 2 3 4)
Score: 4

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

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

[:foo :bar :baz]

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

Score: 3

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

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

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

Score: 1

I would suggest using the convenience features 2 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 1 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

More Related questions